首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
admin
2015-12-30
39
问题
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
给出算法的基本设计思想;
选项
答案
算法的基本设计思想: ①基于先序递归遍历的算法思想是用一个static变量记录wpl,把每个结点的深度作为递归函数的一个参数传递,算法步骤如下: 若该结点是叶子结点,那么变量wpl加上该结点的深度与权值之积; 若该结点非叶子结点,那么若左子树不为空,对左子树调用递归算法,若右子树不为空,对右子树调用递归算法,深度参数均为本结点的深度参数加1; 最后返回计算出的wpl即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数, 当遍历到叶子结点时,累计wpl; 当遍历到非叶子结点时对该结点的把该结点的子树加入队列; 当某结点为该层的最后一个结点时,层数自增1; 队列空时遍历结束,返回wpl。
解析
转载请注明原文地址:https://kaotiyun.com/show/TbRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
对明代政治产生重大影响的“大礼议”之争发生于()年间。
周王室的两大官僚系统是()。
清朝,各地督抚将重大问题径寄军机处交皇帝审批,称为()。
()自幼随父在西域成长,深悉西域道里、风土和政治情况。他编著的《西域记》一书,是范晔撰《后汉书.西域传》的重要根据。
评析郑和下西洋的历史条件和意义。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
下列选项中,()不属于日本在东北推行的殖民统治。
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
随机试题
女性,45岁,3小时前车祸头部受伤,伤后立即昏迷,做CT后入院,入院检查中度昏迷,右瞳孔散大,光反射消失,左上下肢肌张力增高,病理征(+),左顶枕有直径4.0cm头皮下血肿,CT示右额颞部高密度新月影像。诊断是()
引起呼吸浅快的疾病不包括
患儿,8岁。头皮剧烈瘙痒1个月。查体:发根部发现红色丘疹,干后形成黄痂,边缘翘起,中心微凹,上有毛发贯穿,去痂后为浅表溃疡,有特殊的鼠尿臭味。其诊断是
抽样方案中,N为批量,n为批量中随机抽取的样本数,d为抽出样本中不合格的品数,c为不合格判定数,若d≥c则认为该批产品不合格,应拒绝接受。()
300MW,600MW汽轮发电机及其他高压电机绝缘材料一般采用()。
下列关于跨期套利的说法,不正确的是()。
二进制数111110000111转换成十六进制数是
假设某台式计算机的内存储器容量为128MB,硬盘容量为10GB。硬盘的容量是内存容量的()。
Mostoftheemployeesenjoy(talk)______withthemanagerasheiskindandfriendly.
A、Theyneedtobefurtherimproved.B、Theycaneasilyswitchtonaturalgas.C、Theyaremorecost-effectivethanvehiclespowere
最新回复
(
0
)