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

admin2015-12-30 62

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

其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：
给出算法的基本设计思想；

选项

答案算法的基本设计思想： ①基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1；最后返回计算出的wpl即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl；当遍历到非叶子结点时对该结点的把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增1；队列空时遍历结束，返回wpl。

解析

转载请注明原文地址:https://kaotiyun.com/show/TbRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

对巴黎公社的评述，正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器，建立新的国家机器③其实践和经验，丰富了马克思主义理论④由于无产阶级的不成熟，其失败是不可避免的

第一次鸦片战争过程中，清政府在()时对英国侵略者的态度发生了转变。

下列战争与马拉松长跑运动项目起源有关的是()

洪武十三年，朱元璋设置春官、夏官等四辅官，命其详看奏章、协赞政务。次年，又仿宋制设立华盖殿、武英殿、文渊阁、东阁等殿阁大学士。这些是后来()的雏形。

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

以下不是巴黎和会的主要议题的是()

“二战”期间，美国研制了原子弹并用于实践；1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的；德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。

列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

能力的发展水平在人群中的分布大概是

人源化抗体的最主要优点是A．亲和力强B．纯度高C．异源性低而有利于应用于人体D．稳定性好E．特异性强

上题所述病例的最佳治疗方剂是

计划编制时，()按分类规定属于竣工验收与备案文件。

下列关于负债和所有者权益区别的说法中，正确的是()。

吕剧是山东主要地方剧种，由民间说唱艺术“坐唱扬琴”演变而来。()

读某发达国家四城市人口的年龄、性别结构示意图，回答下列问题。根据人口年龄、性别结构判断，文化教育在城市服务功能中占主要地位的是()

英国革命诗人弥尔顿在《失乐园》中塑造的反抗者形象是_______。

设f"(x)＞0，f(0)=0，证明：2f(1)＜f(2)．