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

admin2015-12-30 36

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

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/xrfjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

发明了象形文字的是()

洋务运动时期，首批赴欧海军留学生派出的时间是()。

唐代府兵的基本单位是()。

试论两税法和摊丁入亩的关系。(陕西师范大学2013年中国史真题)

简述当代科技革命发生的背景条件。

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

下列标志着周王室在春秋时代的地位一落千丈，仅存虚名的选项是()

治疗泻下滑脱不禁。应首选的方剂是

女患者，39岁，既往月经先后不定飘于停经40天后，阴道大量出血，色鲜，红质稠，心烦潮热，小便黄少，大便干结，舌红，苔薄黄，脉细数。治疗首选方剂是

以下商品所使用的商标必须注册的是()。

根据有关规定，上海证券交易所对参与回购交易进行委托买卖的数量规定为：交易数量必须是()，即10万元面值及其整数倍。

下列各项中，属于审计报告中标题为“注册会计师对财务报表审计的责任”部分的内容的有()。

“同角的补角相等”的逆命题是()．

Inrecentyears,railroadshavebeencombiningwitheachother,mergingintosupersystems,causingheightenedconcernsaboutmo

Cultureisthetotalsumofallthetraditions,customs,beliefs,andwaysoflifeofagivengroupofhumanbeings.Inthissen