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

admin2015-12-30 44

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

以下不属于考据学家的是()。

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

周王室的两大官僚系统是()。

清朝，各地督抚将重大问题径寄军机处交皇帝审批，称为()。

曹操恢复和发展农业生产所采取的主要措施是()。

导致俄国革命去和平发展可能的事件是()。

以下不是巴黎和会的主要议题的是()

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

金融控股公司被称为金融百货公司制。()

银行业从业人员应当遵守法律法规及所在机构关于电子信息技术设备使用的规定以及有关安全规定，并做到()。

关于国内生产总值的说法，正确的是()。

“三农”问题一直是我国的工作重心，“三农”指的是农业、农村、()。

下列各句中没有语病的一项是()。

简答企业使用品牌策略的优势。

蔡元培对大学精神的解释是()。

WhattoDoWhenthePatientSays,’PleaseDon’tTellMom’Someyearsago,inthecandor(坦白)oftheexamroom,aseventh-gra