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

admin2015-12-30 69

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述弭兵之会的背景、过程和结果。

中国第一个资产阶级革命团体兴中会建立的时间是()。

关于《荷马史诗》的叙述不正确的是()。

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

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

设备管理中，设备映射表(DMT)的作用是()。

假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。

一种数据编码的海明距是7，那么使用这种编码最多可以纠正()个错误。

Bigcompaniesswallowlittleoneseveryday.Sothe【C1】________onMarch25thbyYahoo(annualrevenue,$5billion)ofSummly,a

股静脉血栓脱落可引起(　　　)冠状动脉血栓形成引起(　　　)

急救现场对患者救治的正确处理包括()。

对格式条款的理解发生争议时(　　　)。

在我国货币供应量指标中，属于M1的是()。

培训过程中若遇到突发事件的影响，可采用的较好的处理方法是()。

兴奋在两个神经元之间传递时，以下生理活动不会发生的是()。

AccordingtotheAmericanAcademyofOrthopedicSurgeons,only25%ofthosewhosufferhip________everfullyrecover;asmanyas

Sportingactivitiesareessentiallymodifiedformsofhuntingbehavior.Viewingbiologically,themodern【S

计算机408

学硕统考专业

简述弭兵之会的背景、过程和结果。

中国第一个资产阶级革命团体兴中会建立的时间是()。

关于《荷马史诗》的叙述不正确的是()。

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

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

设备管理中，设备映射表(DMT)的作用是()。

假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。

一种数据编码的海明距是7，那么使用这种编码最多可以纠正()个错误。

Bigcompaniesswallowlittleoneseveryday.Sothe【C1】________onMarch25thbyYahoo(annualrevenue,$5billion)ofSummly,a

股静脉血栓脱落可引起( )冠状动脉血栓形成引起( )

急救现场对患者救治的正确处理包括()。

对格式条款的理解发生争议时( )。

在我国货币供应量指标中，属于M1的是()。

培训过程中若遇到突发事件的影响，可采用的较好的处理方法是()。

兴奋在两个神经元之间传递时，以下生理活动不会发生的是()。

AccordingtotheAmericanAcademyofOrthopedicSurgeons,only25%ofthosewhosufferhip________everfullyrecover;asmanyas

Sportingactivitiesareessentiallymodifiedformsofhuntingbehavior.Viewingbiologically,themodern【S

股静脉血栓脱落可引起(　　　)冠状动脉血栓形成引起(　　　)

对格式条款的理解发生争议时(　　　)。