2. 考研
  3. 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为： 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求： 根据设计思想，采

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为： 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求： 根据设计思想，采

admin2015-12-30  52
问题 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：

其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：
根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
选项
答案算法代码如下： ①基于先序遍历的算法： int WPL(BiTree root){ return wpl_PreOrder(root，0)， } int wpl PreOrder(BiTree root，int deep){ static int wpl=0；／／定义一个static变量存储wpl if(root-＞ichild==NULL ＆＆ root-＞ichild==NULL)／／若为叶子结点，累积wpl wpl+=deep*root-＞weight； if(root-＞ichild!=NULL)／／若左子树不空，对左子树递归遍历 wpl_PreOrder(root-＞ichild，deep+1)； if(root-＞rchild!=NULL)／／若有子树不空，对右子树递归遍历 wpl_PreOrder(root-＞rchild，deep+1)； return wpl， } ②基于层次遍历的算法： #define MaxSize 100／／设置队列的最大容量 int wpl_Leveiorder(BiTree root){ BiTree q[MaxSize]；／／声明队列，end1为头指针，end2为尾指针 int end1，end2；／／队列最多容纳MaxSize-1个元素 end1=end2=0，／／头指针指向队头元素，尾指针指向队尾的后一个元素 int wpl=0，deep=0；／／初始化wpl和深度 BiTree lastNode；／／lastNode用来记录当前层的最后一个结点 BiTree newlastNode；／／newlastNode用来记录下一层的最后一个结点 lastNode=root；／／lastNode初始化为根结点 newlastNode=NULL；／／newlastN0de初始化为空 q[end2++]=root；／／根结点入队 while(end1！=end2){／／层次遍历，若队列不空则循环 BiTree t=q[end1++]；／／拿出队列中的头一个元素 if(t-＞ichiid==NULL & t-＞ichild==NULL){ } wpl+=deep*t-＞weight； }／／若为叶子结点，统计wpl if(t-＞lchild ！=NULL){／／若非叶了结点把左结点入队 q[end2++]=t-＞lchild； newlastNode=t-＞lchild； }／／并设下一层的最后一个结点为该结点的左结点 if(t-＞rchild！=NULL){／／处理叶结点 q[end2++]=t-＞rchild； newlastNode=t-＞rchild； } if(t==lastNode)f／／若该结点为本层最后一个结点，更新lastNode lastNode=newlastNode； deep+=1；／／层数加1 } } return wpl；／／返回wpl }
解析
转载请注明原文地址:https://kaotiyun.com/show/FbRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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