数据结构

三、算法设计题 以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。

int LeafNodeCount(BiTree T)

{

if(T==NULL)

return 0;                                //如果是空树，则叶子结点个数为0

else if(T->lchild==NULL&&T->rchild==NULL)

return 1;                                //判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1

else

return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);

}

（3）交换二叉树每个结点的左孩子和右孩子。

void ChangeLR(BiTree &T)

{

BiTree temp;

if(T->lchild==NULL&&T->rchild==NULL)

return;

else

{

temp = T->lchild;

T->lchild = T->rchild;

T->rchild = temp;

}

ChangeLR(T->lchild);

ChangeLR(T->rchild);

}

void DoubleTraverse(BiTree T)

{

if(T == NULL)

return;

else if(T->lchild==NULL&&T->rchild==NULL)

cout<data;

else

{

cout<data;

DoubleTraverse(T->lchild);

cout<data;

DoubleTraverse(T->rchild);

}

}

[题目分析] 求二叉树高度的算法见上题。

求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。

int Width(BiTree bt)//求二叉树bt的最大宽度

{if (bt==null) return (0);  //空二叉树宽度为0

else 

{BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大

  front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置

  temp=0; maxw=0;       //temp记局部宽度, maxw记最大宽度

  Q[rear]=bt;           //根结点入队列

  while(front<=last)

  {p=Q[front++]; temp++; //同层元素数加1

   if (p->lchild!=null)  Q[++rear]=p->lchild;   //左子女入队

if (p->rchild!=null)  Q[++rear]=p->rchild;   //右子女入队

   if (front>last)      //一层结束，

    {last=rear;

if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度

     temp=0;

 }//if    

}//while

  return (maxw);

}//结束width

int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数

{int num=0; //num统计度为1的结点的个数

     if(bt){QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列

     while(!QueueEmpty(Q))

{p=QueueOut(Q); printf(p->data);     //出队,访问结点

if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为1的结点

if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队

if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队

}  }//if(bt)         

return(num); }//返回度为1的结点的个数

[题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点

  int i，top=0,tag[],longest=0;

  while(p || top>0)

   { while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下

 if(tag[top]==1)    //当前结点的右分枝已遍历

  {if(!s[top]->Lc && !s[top]->Rc)  //只有到叶子结点时，才查看路径长度

if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈，记住最高栈顶指针，退栈

}

     else if(top>0) {tag[top]=1; p=s[top].Rc;}   //沿右子分枝向下

   }//while(p!=null||top>0)

}//结束LongestPath

[题目分析]采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。

对应的递归算法如下：

void AllPath(BTNode *b,ElemType path[],int pathlen)

{

    int i;

    if (b!=NULL)

    {

        if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点

        {

            cout << " " << b->data << "到根结点路径:" << b->data;

            for (i=pathlen-1;i>=0;i--)

        cout << endl;

    }

    else

    {

        path[pathlen]=b->data;           //将当前结点放入路径中

        pathlen++;                       //路径长度增1

        AllPath(b->lchild,path,pathlen); //递归扫描左子树

        AllPath(b->rchild,path,pathlen); //递归扫描右子树

        pathlen--;                       //恢复环境

    }

  }

}