首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 给出算法的基本设
admin
2015-12-30
32
问题
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
给出算法的基本设计思想;
选项
答案
算法的基本设计思想: ①基于先序递归遍历的算法思想是用一个static变量记录、wpl,把每个结点的深度作为递归函数的 一个参数传递,算法步骤如下: 若该结点是叶结点,那么变量wpl加上该结点的深度与权值之积; 若该结点是非叶结点,那么若左子树不为空,对左子树调用递归算法:若右子树不为空,对右子树 调用递归算法,深度参数均为本结点的深度参数加1; 最后返回计算出的wpl即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数, 当遍历到叶结点时,累计wpl; 当遍历到非叶结点时,把该结点的子树加入队列; 当某结点为该层的最后一个结点时,层数自增1; 队列空时遍历结束,返回wpl。
解析
转载请注明原文地址:https://kaotiyun.com/show/kBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
一战期间,中国民族资本主义迅速发展的主要作用是()。
下列关于清朝设置台湾府的叙述,不正确的是()。
元代对边疆地区的统治方式不同于其他三地的一地是()。
由“十字军东征”这一事件评述东西方关系。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为:intIsFull_Bitree(BitreeT)。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
使用操作系统提供的()接口,能在用户程序中将一个字符送到显示器上显示。
随机试题
肝细胞分泌胆汁最先进入()
制定应对风险策略的程序和方法主要包括()。
It’sinterestinghowlittlemostofUSknowaboutourancestorsoraboutthehistoryofourfamily.Ifyou【56】tobenobility(贵族
房地产市场组成要素至少包括()。
规划的环境影响报告书是一个独立的文件,它应该在()完成,针对规划进行环境影响评价,才能实现环境影响评价的目的。
根据《总会计师条例》的规定,下列各项中,属于总会计师行使的职权的有()。
长江公司为增值税一般纳税人,适用增值税税率为13%,期初无留抵增值税税额。长江公司2019年12月份发生如下经济业务:(1)1日,长江公司与A公司签订协议。向A公司销售a产品一台,成本为180万元,增值税专用发票上注明销售价格为220万元,增值税
在排序方法中,关键码比较次数与记录的初始排列无关的是()。
数据库系统中可能会发生各种各样的故障。这些故障主要有四类,即:事务故障、系统故障、介质故障和【】。
ThemergerwasexpectedtohelpthecombinedcompanytoOnereasongivenforthemerger’slackofsuccessis
最新回复
(
0
)