首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
admin
2015-12-30
67
问题
二叉树的带权路径长度(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://kaotiyun.com/show/3BRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中,不是由晁错提出的是()
1901—1939年间美国历届政府在国内经济活动中职能作用的演变。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
某图像显示器的分辨率为1024×768,共可显示256种灰度,则显示存储器的容量为()。
使用操作系统提供的()接口,能在用户程序中将一个字符送到显示器上显示。
随机试题
测定时,将气样从左到右依次驱入吸收瓶和爆炸瓶进行吸收和燃烧。()
IncomparingallofEarth’sgeologicalevolutiontoonecalendaryear,theauthorshows______.Intheone-year-longfilmdinos
有关肩关节脱位的不正确描述是
感染伤口的处理最佳方法是
请从所给的四个选项中,选出最符合左边四个图形一致性规律的选项。()
人寿保险保单转让时,为了产生法律效力必须()。
下列选项中,说法有误的是()。
下列语句中有语病的一句为:
日本工厂的工人有终生工作的保证,有在生产率和共同利润的基础上发给的奖金,并且工资金额并不与具体工作相连。与此相矛盾的是,这些保证并没有抑制工厂主引进劳动节约型的机器设备。这样的革新对工厂主是有利的,尽管事实上工厂主必须保护工人的工资。下面哪一项,如果是正确
邓小平指出,毛主席最伟大的功绩是把马列主义的普遍原理同中国革命实际相结合,指出了中国夺取革命胜利的新道路。请阐述毛泽东新民主主义理论主要内容及其在马克思主义中国化进程中的历史地位。
最新回复
(
0
)