求二叉树的宽度(Find the width of binary tree)

 1 /*******************************************
 2  *思路:以二叉树的层次遍历为基础
 3  *****************************************/
 4 #define MAX_DEEP    100 //假设二叉树的最大深度
 5 int Width(BiTree t)
 6 {
 7     BiTree p;
 8     int width = 0;//最大宽度
 9     int level;//层次
10     int withTable[MAX_DEEP];//每层的宽度表
11     memset(withTable, 0, MAX_DEEP);
12     InitQueue(Q);
13     if (T != NULL) {
14         EnQueue(Q,T);
15         level = 1;//初始层次
16         withTable[level]++;
17         width = withTable[level];//初始宽度
18     }
19     while(!QueueEmpty(Q)) {
20         DeQueue(Q,p);
21         if (p->lchild != NULL) {
22             EnQueue(Q,p->lchild);
23             withTable[level+1]++;//当前结点的下一个层次节点数加一
24         }
25         if (p->rchild != NULL) {
26             EnQueue(Q,p->rchild);
27             withTable[level+1]++;//当前结点的下一个层次节点数加一
28         }
29         width = width > withTable[level+1] ? width : withTable[level+1];//获取最大层次
30         if (--withTable[level] == 0) level++;//核心步骤:当前层所有节点都已出队时,层次加一
31     }
32     return width;
33 }

!!!请勿转载到CSDN

————————
 1 /*******************************************
 2  *思路:以二叉树的层次遍历为基础
 3  *****************************************/
 4 #define MAX_DEEP    100 //假设二叉树的最大深度
 5 int Width(BiTree t)
 6 {
 7     BiTree p;
 8     int width = 0;//最大宽度
 9     int level;//层次
10     int withTable[MAX_DEEP];//每层的宽度表
11     memset(withTable, 0, MAX_DEEP);
12     InitQueue(Q);
13     if (T != NULL) {
14         EnQueue(Q,T);
15         level = 1;//初始层次
16         withTable[level]++;
17         width = withTable[level];//初始宽度
18     }
19     while(!QueueEmpty(Q)) {
20         DeQueue(Q,p);
21         if (p->lchild != NULL) {
22             EnQueue(Q,p->lchild);
23             withTable[level+1]++;//当前结点的下一个层次节点数加一
24         }
25         if (p->rchild != NULL) {
26             EnQueue(Q,p->rchild);
27             withTable[level+1]++;//当前结点的下一个层次节点数加一
28         }
29         width = width > withTable[level+1] ? width : withTable[level+1];//获取最大层次
30         if (--withTable[level] == 0) level++;//核心步骤:当前层所有节点都已出队时,层次加一
31     }
32     return width;
33 }

!!! Do not reprint to CSDN