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

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

admin2012-06-26  92
问题 一棵二叉树的繁茂度定义为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一>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； }
解析 要用层次遍历以及队列来处理，可增设一个宽度计数器，在统计完每一层的结点个数之后，再从计数器中挑出最大值。
转载请注明原文地址:https://www.kaotiyun.com/show/mfxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)