首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
admin
2015-12-30
59
问题
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
给出算法的基本设计思想;
选项
答案
算法的基本设计思想: ①基于先序递归遍历的算法思想是用一个static变量记录、wpl,把每个结点的深度作为递归函数的 一个参数传递,算法步骤如下: 若该结点是叶结点,那么变量wpl加上该结点的深度与权值之积; 若该结点是非叶结点,那么若左子树不为空,对左子树调用递归算法:若右子树不为空,对右子树 调用递归算法,深度参数均为本结点的深度参数加1; 最后返回计算出的wpl即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数, 当遍历到叶结点时,累计wpl; 当遍历到非叶结点时,把该结点的子树加入队列; 当某结点为该层的最后一个结点时,层数自增1; 队列空时遍历结束,返回wpl。
解析
转载请注明原文地址:https://kaotiyun.com/show/kBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于唐代三省六部制的说法错误的一项是()。
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
以下选项不属于希腊城邦的形成方式和途径的是()。
武昌起义后,全国革命形势发展的同时也潜伏着失败的危机,这主要是由于()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
下列不属于延安整风运动的文件是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
随机试题
人参的下列配伍哪项是正确的()(1997年第142题)
源结点与目标结点之间采用交换技术实现其连接。通常有三种交换方式:电路交换、( )、包交换。
《食品卫生法》对人的效力原则是
关于革兰阳性菌
按《建筑桩基技术规范》(JGJ94—94),对于桩身周围有液化土层的低桩承台,关于液化土层对单桩极限承载力影响的分析中,()是正确的。
深基坑支护与降水工程、模板工程、脚手架工程的施工专项方案必须经下列哪些人员签字后实施?①经施工单位技术负责人;②总监理工程师;③结构设计人;④施工方法人代表。
英国的保险公估人大多属于( )。
全面准确地理解和把握“一国”与“两制”的关系,应在坚持“一国”基础上,实现“两制”之间的和谐相处、相互促进。为此,必须做到
编写函数fun,其功能是:根据以下公式计算S,并将计算结果作为函数值返回,n通过形参传入。例如,若n的值为11时,函数的值为1.833333。注意:部分源程序给出如下。请勿改动主函数main和其他函数中的任何内容,仅在函数f
DearSir/Madam,Inresponsetoyouradvertisementinyesterday’sTimeEducationalSupplement,Iwouldliketoapplyforthe
最新回复
(
0
)