首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求: 根据设计思想,采
admin
2015-12-30
65
问题
二叉树的带权路径长度(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
学硕统考专业
相关试题推荐
印度孔雀帝国时代,就土地占有情况而言,占全国土地的绝大部分的是()。
中国古代史分期问题的焦点有哪些?简述其代表人物及思想。(兰州大学2013年中国史基础真题)
评述抗战的三个阶段。
中国第一个资产阶级革命团体兴中会建立的时间是()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
下列不是苏俄实行战时共产主义政策原因的是()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
随机试题
患者,男,36岁。患十二指肠溃疡6年,突发上腹剧痛3小时,继而全腹痛、大汗、面色苍白,四肢发凉。查体:全腹压痛,反跳痛。考虑有溃疡病穿孔的可能。问题4:胃溃疡穿孔多见于
A.消食导滞B.消痞除满C.行气解郁D.健脾祛湿E.益气补血越鞠丸的功用是
此证辨证属于()治法宜选用()
处方的意义主要表现在其()
证券市场的结构是指证券市场的构成及其各部分之间的量比关系。证券市场的结构可以有许多种,但较为重要的结构是( )。
2010年1月10日,甲公司销售一批商品给乙公司,货款为5000万元(含增值税额)。合同约定,乙公司应于2010年4月10日前支付上述货款。由于资金周转困难,乙公司到期不能偿付货款。经协商,甲公司与乙公司达成如下债务重组协议:乙公司以一批产品和一台设备偿还
根据以下资料,回答以下问题。2013年全年研究生招生61.1万人,在学研究生179.4万人,毕业生51.4万人。普通本专科招生700万人,在校生2468.1万人,毕业生638.7万人。中等职业教育招生698万人,在校生1960.2万人,毕业生67
上海市统计局发布信息显示,2010年9月上海市签订外商直接投资合同项目295项,比上年同月增长4.6%;签订外商直接投资合同金额13.19亿美元,增长19.8%;实际到位金额9.44亿美元,增长3.5%,增悟实现年内连续第9个月正增长。一个显著的特点:是第
设A,B分别为m阶,n阶正定矩阵,试判定分块矩阵是否是正定矩阵.
I’llcallyoutonightat10o’clock______Icanfindatelephonethatworks.
最新回复
(
0
)