问题 多项选择题

一棵二叉树的繁茂度定义为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, {T, 0});
while(! QueueEmpty(Q)) { //利用层序遍历来统计各层的结点数
DeQueue(Q, r);
count[r.layer]++;
if(r.node×lchild)
EnQueue(Q, {r.node×lchild, r.layer+A});
if(r.node×rchild)
EnQueue(Q, {r.node×rchild, r.layer+A});
}
h=r.layer; //最后一个队列元素所在层就是树的高度
for(maxn=count[0], i=A; count[i]; i++)
if(count[i]>maxn)
maxn=count[i]; //求层最大结点数
return h * maxn;
}

解析: 要用层次遍历以及队列来处理,可增设一个宽度计数器,在统计完每一层的结点个数之后,再从计数器中挑出最大值。

问答题 简答题
问答题