一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

正确答案：typedef struct BiTNode{ TElemType data； struct BiTNode*lchild；*rchild； ／／左、右孩子指针 }BiTNode*BiTree； typedef struct{ BiTNode node； int layer； }BTNRecord； ／／包含结点所在层次的记录类型 int FanMao(Bitree T){ int count[MAX]； ／／count数组存放每一层的结点数 InitQueue(Q)； ／／Q的元素为BTNRecord类型 EnQueue(Q{T0})； while(!QueueEmpty(Q)){ ／／利用层序遍历来统计各层的结点数 DeQueue(Qr)； count[r．layer]++： if(r．node一>ichild) EnQueue(Q{r．node一>ichildr．layer+l})； if(r．node一>rchild) EnQueue(Q{r．node一>rchildr．layer+1))； } h=r．layer； ／／最后一个队列元素所在层就是树的高度 for(maxn=count[0]i=1；count[i]；i++) if(count[i]>maxn) maxn=count[i]； ／／求层最大结点数 return h*maxn； }
typedef struct BiTNode{ TElemType data； struct BiTNode*lchild；*rchild； ／／左、右孩子指针 }BiTNode，*BiTree； typedef struct{ BiTNode node； int layer； }BTNRecord； ／／包含结点所在层次的记录类型 int FanMao(Bitree T){ int count[MAX]； ／／count数组存放每一层的结点数 InitQueue(Q)； ／／Q的元素为BTNRecord类型 EnQueue(Q，{T，0})； while(!QueueEmpty(Q)){ ／／利用层序遍历来统计各层的结点数 DeQueue(Q，r)； count[r．layer]++： if(r．node一>ichild) EnQueue(Q，{r．node一>ichild，r．layer+l})； if(r．node一>rchild) EnQueue(Q，{r．node一>rchild，r．layer+1))； } h=r．layer； ／／最后一个队列元素所在层就是树的高度 for(maxn=count[0]，i=1；count[i]；i++) if(count[i]>maxn) maxn=count[i]； ／／求层最大结点数 return h*maxn； } 解析：要用层次遍历以及队列来处理，可增设一个宽度计数器，在统计完每一层的结点个数之后，再从计数器中挑出最大值。