首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
admin
2015-12-30
62
问题
二叉树的带权路径长度(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->ichild==NULL && root->ichild==NULL)//若为叶子结点,累积wpl wpl+=deep*root->weight; if(root->ichild!=NULL)//若左子树不空,对左子树递归遍历 wpl_PreOrder(root->ichild,deep+1); if(root->rchild!=NULL)//若有子树不空,对右子树递归遍历 wpl_PreOrder(root->rchild,deep+1); return wpl, } ②基于层次遍历的算法: #define MaxSize 100//设置队列的最大容量 int wpl_Leveiorder(BiTree root){ BiTree q[MaxSize];//声明队列,end1为头指针,end2为尾指针 int end1,end2;//队列最多容纳MaxSize-1个元素 end1=end2=0,//头指针指向队头元素,尾指针指向队尾的后一个元素 int wpl=0,deep=0;//初始化wpl和深度 BiTree lastNode;//lastNode用来记录当前层的最后一个结点 BiTree newlastNode;//newlastNode用来记录下一层的最后一个结点 lastNode=root;//lastNode初始化为根结点 newlastNode=NULL;//newlastN0de初始化为空 q[end2++]=root;//根结点入队 while(end1!=end2){//层次遍历,若队列不空则循环 BiTree t=q[end1++];//拿出队列中的头一个元素 if(t->ichiid==NULL & t->ichild==NULL){ } wpl+=deep*t->weight; }//若为叶子结点,统计wpl if(t->lchild !=NULL){//若非叶了结点把左结点入队 q[end2++]=t->lchild; newlastNode=t->lchild; }//并设下一层的最后一个结点为该结点的左结点 if(t->rchild!=NULL){//处理叶结点 q[end2++]=t->rchild; newlastNode=t->rchild; } if(t==lastNode)f//若该结点为本层最后一个结点,更新lastNode lastNode=newlastNode; deep+=1;//层数加1 } } return wpl;//返回wpl }
解析
转载请注明原文地址:https://kaotiyun.com/show/FbRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
文艺复兴运动兴起的时间是()。
论述斯巴达的阶级结构、政治制度和社会风尚
民族资本主义的发展为其后到来的变法维新和民主革命做的准备有()①充足的物质条件②思想基础③阶级力量④指导方针
明清两朝已经是中国封建社会的晚期,同时也出现了许多新的社会现象,最明显的是()。
德川庆喜采取以退为进的策略。在1867年10月提出()。
中书省取代尚书省参与决策的部分职权,使尚书台成为主要行政中枢,这一历史现象出现在()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
交通标志产品各项试验的判定规则为()。
第一部正式的教会法是()
男,56岁。1个月颈肩痛,并向右手放射,右手拇指痛觉减弱,肱二头肌肌力弱。初步诊断是
下述描述三叉神经正确的是A.眼神经为混合性神经B.运动纤维支配舌肌及颊肌C.上颌神经为混合性神经D.下颌神经为混合性神经E.眼神经管理眼球运动及泪腺分泌
慢性浅表性胃炎患者一般不会出现
甲公司与乙公司2004年8月签订买卖货物的合同,总价值20万元,约定甲公司于2004年12月前交付货物,并约定乙公司向甲公司交付3万元定金,后乙公司交付定金时实际交付了5万元。合同履行期满,甲公司拒绝交付货物,于是乙公司要求甲公司双倍返还定金。甲公司应返还
下列项目中,不属于对账内容的是()。
生产企业的内部配送,一般由高层主管统一进行采购,实行集中库存,按车间的或者分厂的生产计划组织配送。
韩红艳是太平洋公司的会计。每年年终都是她工作最忙的时候,因为这时公司会为在职员工发放年终奖,她需要计算每位员工的工资及奖金的个人所得税,还得为每位员工制作工资条。请按照下列要求完成工资和奖金的计算以及工资条的制作工作:(1)将考生文件夹下的“Excel素
Youshouldspendabout20minutesonQuestions1-13,whicharebasedonReadingPassage1below.Reducin
最新回复
(
0
)