首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
admin
2015-12-30
66
问题
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
选项
答案
算法的代码如下: ①基于先序遍历的算法: int WPL(BiTree root){ return wpl_PreOrder(root,0); } int wpl PreOrder(BiTree root,int deep){ static int wpl=0;//定义一个static变量存储wpl if(root->lchild==NuLL&&root->lchild==NULL)//若为叶结点,累积wpl wpl+=deep*root->weight, if(root->ichiid!;NuLL)//若左子树不空,对左子树递归遍历 wpl_PreOrder(root->ichild,deep+1), if(root->rchiidI=NULL)//若右子树不空,对右于树递归遍历 wpl_PreOrder(root->rchild,deep+1); return wpl; } ②基于层次遍历的算法: #define MaxSize 100//设置队列的最大容量 int wpl LevelOrder(BiTree root){ BiTree q[MaxSize];//声明队列,end1为头指针,end2为尾指针 int end1,end2,//队列最多容纳MaxSize-1个元素 end1=end2=0;//头指针指向队头元素,尾指针指向队尾的后一个元素 int wpl=deep=0;//初始化wpl和深度 BiTree lastNode;//lastNode用来记录当前层的最后一个结点 BiTree newlastNode;//newlastNode用来记录下一层的最后一个结点 lastNode=root;//lastNode初始化为根结点 newlastNode=NULL;//newlastNode初始化为空 q[end2++]=root;//根结点入队 while(end1!=end2)f//层次遍历,若队列不空则循环 BiTree t=q[end1++];//拿出队列中的头一个元素 if(t->ichild==NULL&&t->lchild==NULL){ wpl+=deep*t->weight; }//若为叶结点,统计wpl if(t->ichild!=NULL){//若非叶结点把左结点入队 q[end2++]=t->ichild; newlastNode=t->ichiid; }//并设下一层的最后一个结点为该结点的左结点 if(t->rchild!=NULL){//处理叶结点 q[end2++]=t->rchild; newlastNode=t->rchild; } if(t==lastNode){//若该结点为本层最后一个结点,更新lastNode lastNode=newlastNode; deep+=1;//层数加1 } } return wpl;//返回wpl }
解析
考查二叉树的带权路径长度,二叉树的带权路径长度为每个叶结点的深度与权值之积的总和,可以使用先序遍历或层次遍历解决问题。
转载请注明原文地址:https://kaotiyun.com/show/3BRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国共产党七届三中全会以后进行的工商业合理调整,核心内容是调整()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
下列不是苏俄实行战时共产主义政策原因的是()。
洋务派创办军事工业的方式是()。
布雷顿森林体系
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024.字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为1ms。设I/O系统的性能只与磁盘和控制器有关,单磁
某计算机处理器主频为50MHz,采用定时查询方式控制设备A的I/O,查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间,为保证数据不丢失,每秒需对其查询至少200次,则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是____。
随机试题
中国共产党的思想路线的核心内容是:
如图3-9(所示偏心套,装夹在90°V形块夹具上车削偏心孔(图3-9b),试计算其定位误差。
我国结核病的流行特点是
当某企业的产量为4个单位时,其总固定成本、总可变成本分别是1400元和800元,则该企业的平均总成本是()元。
()不属于配送中心的功能。
第三方数据处理模式表现为:服务商通过软件即服务或平台即服务的云服务形式为用户提供自己的数据上传到服务商的平台上,由平台进行分析处理,用户可以在线查看相应的结果。()
杨贤江对青年人的指导只是对其学习方面的指导。
TakingaNapduringtheDayMedicalexpertssaymostAmericansdonotgetenoughsleep.TheysaymoreAmericansneedto【51】
Whatdoesthespeakermean?
SportBalloonsTherearetwokindsofsportballoons:gasandhotair./Hotairballoonsaresaferthangasballoons,/whi
最新回复
(
0
)