首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
admin
2015-12-30
83
问题
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
给出算法的基本设计思想;
选项
答案
算法的基本设计思想: ①基于先序递归遍历的算法思想是用一个static变量记录、wpl,把每个结点的深度作为递归函数的 一个参数传递,算法步骤如下: 若该结点是叶结点,那么变量wpl加上该结点的深度与权值之积; 若该结点是非叶结点,那么若左子树不为空,对左子树调用递归算法:若右子树不为空,对右子树 调用递归算法,深度参数均为本结点的深度参数加1; 最后返回计算出的wpl即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数, 当遍历到叶结点时,累计wpl; 当遍历到非叶结点时,把该结点的子树加入队列; 当某结点为该层的最后一个结点时,层数自增1; 队列空时遍历结束,返回wpl。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/kBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
联共(布)“十五大”以后,新经济政策被逐步取消,根本上是由于()。
以下关于玛雅天文学成就的叙述,正确的是()。①玛雅人创造的“玛雅历”是一种太阳历。②玛雅人的历法,与宗教祭祀有着密切联系。③奇钦.伊查天文观象台是玛雅天文学的伟大成就。④玛雅人的历法中,采用了12进位法。
简述地理大发现对欧洲经济、政治发展的影响,及其对世界整体化启动的作用。
下列标志着周王室在春秋时代的地位一落千丈,仅存虚名的选项是()
世界天文史上最早实地测量子午线的记录是由谁进行的?()
“一战”后,协约国与奥地利签订的确认奥匈帝国解体的文件是()。
阅读材料,回答以下问题:第四章总统第二十九条临时大总统、副总统由参议院选举之。以总员四分之三以上出席,得票满投票总数三分之二以上者为当选。第三十条临时大总统代表临时政府,总揽政务,公布法律。第三十一条临时大总统为执行法律或基于法
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
计算机系统中存储器为何采用分级结构?
随机试题
《湘夫人》中因情造景的诗句有()
下列关于人类社会存在和发展的物质基础说法错误的是()
女性,56岁。气短3个月,MRI显示右上纵隔旁软组织信号,右上叶支气管狭窄,首先诊断考虑
A.端坐位B.截石位C.侧卧位D.仰卧屈膝位E.去枕平卧位E.去枕平卧位全身麻醉术后患者应取
下列关于基金托管人信息披露义务的说法,正确的有()。
请概括给定材料所反映的主要内容。字数不超过200字。(15分)以下是对上述材料中反映的问题和一些看法,其中有一些可能与材料的内容不一致,请你指出哪几个不一致,并在各自的下面说明你的理由和原因。对观点一致的说法请勿作答,否则扣分。每条说明字数在200字以
(新疆2012—30)26,50,98,194,()
根据《合同法》的有关规定,下列有关合同履行的表述,正确的有()。
MartinlerntDeutschIchhei?eMartinKrauseundbinStudent.IchstudiereMusikundlerneDeutsch.MeineElternschreibenmiro
Wherehasthewomanbeen?
最新回复
(
0
)