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

admin2015-12-30 60

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

1988年起，苏联民族矛盾激化，民族分离运动加剧，第一次较大规模的民族冲突是()。

七七事变爆发后，()给中国以巨大的支援，双方签订了()，在政治上给中国以重大支持。

第三次科技革命初期，苏联领先于美国的新兴科学技术成就是()。

下列有关俄国农奴制改革的表达，不正确的是()。

欧洲协调的第一次会议是指()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

《凡尔赛条约》中，战胜国以()方式处置德国的全部海外殖民地。

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数。(2)画出散列表。(

—Iwillcometoattendyourlectureat:tomorrow—I’msorry,bythenmylecturewillhaveendedandI______myguestsinmyoffi

下列药物不属于桃红四物汤组方药物的是

关于雇主的保证责任，下列说法不正确的是(　　)。

销售机构在进行市场细分时应遵循的原则中，()是指每个细分市场有明显的区分标准，让销售机构能够清楚地认识不同细分市场的客户差异，提供个性化的产品和服务，以确保营销策略具有针对性。

()是企业营销战略的核心，也是决定企业营销成败的关键。

下列关于我国文字、书法知识，正确的一项是()。

学习迁移是指一种学习对另一种学习的影响，即已获得的知识经验、知识结构、动作技能、学习态度、策略和方法等与新知识、新技能之间所发生的影响。下列选项中，没有体现学习迁移能力的是()。

AttheentrancetoabigofficeinLondon,therewasapieceofpaperwhichallmenhadtowritenamesonwhentheyarrivedeach

计算机408

学硕统考专业

1988年起，苏联民族矛盾激化，民族分离运动加剧，第一次较大规模的民族冲突是()。

七七事变爆发后，()给中国以巨大的支援，双方签订了()，在政治上给中国以重大支持。

第三次科技革命初期，苏联领先于美国的新兴科学技术成就是()。

下列有关俄国农奴制改革的表达，不正确的是()。

欧洲协调的第一次会议是指()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

《凡尔赛条约》中，战胜国以()方式处置德国的全部海外殖民地。

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数。(2)画出散列表。(

—Iwillcometoattendyourlectureat:tomorrow—I’msorry,bythenmylecturewillhaveendedandI______myguestsinmyoffi

下列药物不属于桃红四物汤组方药物的是

关于雇主的保证责任，下列说法不正确的是( )。

销售机构在进行市场细分时应遵循的原则中，()是指每个细分市场有明显的区分标准，让销售机构能够清楚地认识不同细分市场的客户差异，提供个性化的产品和服务，以确保营销策略具有针对性。

()是企业营销战略的核心，也是决定企业营销成败的关键。

下列关于我国文字、书法知识，正确的一项是()。

学习迁移是指一种学习对另一种学习的影响，即已获得的知识经验、知识结构、动作技能、学习态度、策略和方法等与新知识、新技能之间所发生的影响。下列选项中，没有体现学习迁移能力的是()。

AttheentrancetoabigofficeinLondon,therewasapieceofpaperwhichallmenhadtowritenamesonwhentheyarrivedeach

关于雇主的保证责任，下列说法不正确的是(　　)。