binarytreeforthewidth.txt

求二叉树中的宽度 二叉树中具有结点数最多的那一层结点总数即是二叉树的宽度。可以采用分层遍历的方法求出所有结点的

求二叉树中的宽度
二叉树中具有结点数最多的那一层结点总数即是二叉树的宽度。可以采用分层遍历的方法求出所有结点的层编号，然后求出各层的结点总数，比较找出结点总数最多的值。

对应的算法如下：

int BTDepth(BTNode *t)

{

　struct

    {int lno;         /*结点的层次编号*/

     BTNode *p;     /*结点指针*/

    }Qu[MaxSize]; 　　/*定义顺序非循环队列*/

  int front,rear; 　　　　/*定义队首和队尾指针*/

  int lnum,max,i,n;

  front=rear=0; 　　　　/*置队列为空队*/

  if (t!=NULL)

   {rear++;

    Qu[rear].p=t;        /*根结点指针入队*/

    Qu[rear].lno=1;　　　/*根结点的层次编号为1*/

    while(rear!=front) 　 /*队列不为空，此循环通过层次遍历求出每个结点的层次*/

    {

      front++;

      t=Qu[front].p; 　　/*队头出队*/

      lnum=Qu[front].lno;

      if (t->lch!=NULL)　 /*左孩子入队*/

      { rear++;

       Qu[rear].p=t->lch;

       Qu[rear].lno=lnum+1;

      }

    if (t->rch!=NULL)　　　/*右孩子入队*/

      { rear++;

       Qu[rear].p=t->rch;

       Qu[rear].lno=lnum+1;

      }

   }

   printf(“各结点的层编号:\n”);

   for(i=1;i<=rear;i++)

      printf(“%c,%d\n”,Qu[i].p->data,Qu[i].lno);

   max=0;lnum=1;i=1;　　　　　　/*lnum从第1层开始*/

   while(i<=rear)                /*通过比较相同层次的结点数求出树的宽度*/

　｛n=0;

    while(i<=rear&&Qu[i].lno==lnum)

    {n++;                      /* n累计lnum层中的结点个数*/

     i++;

    }

    lnum=Qu[i].lno; 　　　　　　/*取一个新的结点层次*/

    if(n>max)max=n; 　　　　　 /*将最大层次结点数赋max*/

   }

   return max; 　　　　　　　　 /*返回max的值*/

  }

else

 return 0;

}