首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
admin
2015-12-30
84
问题
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
给出算法的基本设计思想;
选项
答案
算法的基本设计思想: ①基于先序递归遍历的算法思想是用一个static变量记录、wpl,把每个结点的深度作为递归函数的 一个参数传递,算法步骤如下: 若该结点是叶结点,那么变量wpl加上该结点的深度与权值之积; 若该结点是非叶结点,那么若左子树不为空,对左子树调用递归算法:若右子树不为空,对右子树 调用递归算法,深度参数均为本结点的深度参数加1; 最后返回计算出的wpl即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数, 当遍历到叶结点时,累计wpl; 当遍历到非叶结点时,把该结点的子树加入队列; 当某结点为该层的最后一个结点时,层数自增1; 队列空时遍历结束,返回wpl。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/kBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
《汉谟拉比法典》中规定:如果奴隶胆敢对主人说:“你不是我的主人。”他的耳朵就要被割掉。这部法典诞生于()。
关于法兰西第三共和国宪法的叙述,不正确的是()。
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
简述西欧城市兴起的原因、方式及其影响。
二月革命后,俄国为什么会出现两个政权并存的局面?
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
虚拟存储器技术是基于程序的()特性。
某计算机处理器主频为50MHz,采用定时查询方式控制设备A的I/O,查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间,为保证数据不丢失,每秒需对其查询至少200次,则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是____。
随机试题
关于儿童能量代谢,以下哪种说法是错误的
A.空腹血糖B.糖化血红蛋白C.尿糖D.葡萄糖耐量试验糖尿病控制程度的评估指标是
肉豆蔻
2006一2014年,住宅地价增长率高于2015年的年份有()个。
下列关于景区门票价格的说法错误的一项是()。
根据一定的题目,将所保存的档案材料的有关内容进行综合加工编写的材料是()
张某驾驶一辆电动车在街上穿行。行驶至路边一胡同口时,电动车不慎倾倒,连续撞翻多个垃圾桶。如此一来,路口道路交通受到阻碍。请问,面对下列哪种情况,公安机关可以代替张某清理道路障碍物?()
据调查,滨州市有24%的家庭拥有电脑,但拥有电脑的家庭中的12%每周编写程序2小时以上,23%的在1~2小时之间,其余的都不到1小时。可见,滨州市大部分购买电脑的家庭并没有充分利用他们的家庭电脑。以下哪种说法如果为真,最能构成对上述结论的质疑?
(2012)曲线的渐近线的条数为()
论网络安全体系设计随着社会信息化的普及,计算机网络已经在各行各业得到了广泛的应用。目前,绝大多数业务处理几乎完全依赖计算机和网络执行,各种重要数据如政府文件、工资档案、财务账目和人事档案等均依赖计算机和网络进行存储与传输。另一方面,针对计算机和网
最新回复
(
0
)