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

admin2015-12-30 80

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

以下不属于“万历三大征”的是()。

蒙古军西征之后，罗斯处于()的控制之下。

埃及曾两次被波斯帝国征服，波斯第二次征服埃及的时间是()。

西汉初年，西域共有36国，其中以()人口最多。

“两个凡是”

布雷顿森林体系

用高级语言编写的源程序要转换成等价的目标程序，必须经过____________。

A．CKB．MbC．cTnD．LD1E．AST心肌缺血发生后，血中出现高峰浓度最晚的标志物是

男，7个月。不活泼，食欲差，面色苍白。血红蛋白80g/L，红细胞数3×1012/L，考虑为(　　　)

A．肿瘤中有软骨样组织B．肿瘤中有牙乳头样组织C．肿瘤中有筛孔样结构D．肿瘤中有牙体组织E．肿瘤由黏液样细胞、表皮样细胞和中间细胞组成腺样囊性癌

场内申购赎回ETF采用(　　)方式。

下列有关审计业务三方关系人的说法，恰当的有()。

在Excel2007中，下列运算符优先级最高的是(43)。

Janeisunhappybecauseeveryonewenttothedance______her.

计算机408

学硕统考专业

以下不属于“万历三大征”的是()。

蒙古军西征之后，罗斯处于()的控制之下。

埃及曾两次被波斯帝国征服，波斯第二次征服埃及的时间是()。

西汉初年，西域共有36国，其中以()人口最多。

“两个凡是”

布雷顿森林体系

用高级语言编写的源程序要转换成等价的目标程序，必须经过____________。

A．CKB．MbC．cTnD．LD1E．AST心肌缺血发生后，血中出现高峰浓度最晚的标志物是

男，7个月。不活泼，食欲差，面色苍白。血红蛋白80g/L，红细胞数3×1012/L，考虑为( )

A．肿瘤中有软骨样组织B．肿瘤中有牙乳头样组织C．肿瘤中有筛孔样结构D．肿瘤中有牙体组织E．肿瘤由黏液样细胞、表皮样细胞和中间细胞组成腺样囊性癌

场内申购赎回ETF采用( )方式。

下列有关审计业务三方关系人的说法，恰当的有()。

在Excel2007中，下列运算符优先级最高的是(43)。

Janeisunhappybecauseeveryonewenttothedance______her.

男，7个月。不活泼，食欲差，面色苍白。血红蛋白80g/L，红细胞数3×1012/L，考虑为(　　　)

场内申购赎回ETF采用(　　)方式。