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

admin2015-12-30 32

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

一战期间，中国民族资本主义迅速发展的主要作用是()。

下列关于清朝设置台湾府的叙述，不正确的是()。

元代对边疆地区的统治方式不同于其他三地的一地是()。

由“十字军东征”这一事件评述东西方关系。

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为：intIsFull_Bitree(BitreeT)。

使用操作系统提供的()接口，能在用户程序中将一个字符送到显示器上显示。

肝细胞分泌胆汁最先进入()

制定应对风险策略的程序和方法主要包括()。

It’sinterestinghowlittlemostofUSknowaboutourancestorsoraboutthehistoryofourfamily.Ifyou【56】tobenobility(贵族

房地产市场组成要素至少包括()。

规划的环境影响报告书是一个独立的文件，它应该在()完成，针对规划进行环境影响评价，才能实现环境影响评价的目的。

根据《总会计师条例》的规定，下列各项中，属于总会计师行使的职权的有()。

在排序方法中，关键码比较次数与记录的初始排列无关的是()。

数据库系统中可能会发生各种各样的故障。这些故障主要有四类，即：事务故障、系统故障、介质故障和【】。

ThemergerwasexpectedtohelpthecombinedcompanytoOnereasongivenforthemerger’slackofsuccessis