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

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

admin2015-12-30  95
问题 二叉树的带权路径长度(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-＞lchild==NuLL＆＆root-＞lchild==NULL)／／若为叶结点，累积wpl wpl+=deep*root-＞weight， if(root-＞ichiid!；NuLL)／／若左子树不空，对左子树递归遍历 wpl_PreOrder(root-＞ichild，deep+1)， if(root-＞rchiidI=NULL)／／若右子树不空，对右于树递归遍历 wpl_PreOrder(root-＞rchild，deep+1)； return wpl； } ②基于层次遍历的算法： #define MaxSize 100／／设置队列的最大容量 int wpl LevelOrder(BiTree root){ BiTree q[MaxSize]；／／声明队列，end1为头指针，end2为尾指针 int end1，end2，／／队列最多容纳MaxSize-1个元素 end1=end2=0；／／头指针指向队头元素，尾指针指向队尾的后一个元素 int wpl=deep=0；／／初始化wpl和深度 BiTree lastNode；／／lastNode用来记录当前层的最后一个结点 BiTree newlastNode；／／newlastNode用来记录下一层的最后一个结点 lastNode=root；／／lastNode初始化为根结点 newlastNode=NULL；／／newlastNode初始化为空 q[end2++]=root；／／根结点入队 while(end1!=end2)f／／层次遍历，若队列不空则循环 BiTree t=q[end1++]；／／拿出队列中的头一个元素 if(t-＞ichild==NULL&&t-＞lchild==NULL){ wpl+=deep*t-＞weight； }／／若为叶结点，统计wpl if(t-＞ichild!=NULL){／／若非叶结点把左结点入队 q[end2++]=t-＞ichild； newlastNode=t-＞ichiid； }／／并设下一层的最后一个结点为该结点的左结点 if(t-＞rchild!=NULL){／／处理叶结点 q[end2++]=t-＞rchild； newlastNode=t-＞rchild； } if(t==lastNode){／／若该结点为本层最后一个结点，更新lastNode lastNode=newlastNode； deep+=1；／／层数加1 } } return wpl；／／返回wpl }
解析 考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。
转载请注明原文地址:https://www.kaotiyun.com/show/3BRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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