首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2K一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2K一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-15
69
问题
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2
K
一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
选项
答案
二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的,不是完全二叉树的二叉树顺序存储时,要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typeclef struct { BiTree bt: //二叉树结点指针 int num; }tnode: //num是结点在一维数组中的编号 tnode Q[maxsize]; //循环队列,容量足够大 void creat(BiTree T,ElemType BT[]){ //深度h的二叉树存于一维数组BT[1..2
k
一1]中 //本算法生成该二叉树的二叉链表存储结构 tnode tq; //tq是队列元素 int len.i: //数组长度 len=strlen(BT); T=(BiTree)malloc(sizeof(BiNode)): //申请结点 T一>data=BT[1]; //根结点数据 tq.bt=T;tq.num=1; Q[1]=tq; //根入队列 front=0;rear=1; //循环队列头、尾指针 while(front!=rear){ //当队列不空时循环 front=(front+1)%maxsize: tq=Q[front];P=tq.bt;i=tq.num; //出队,取出结点及编号 if(BT[2*i]=='#'∣∣112*i>len)p->lchild=null; //左子树为空,'#'表示虚结点 else{ //建立左子女结点并入队列 p一>lchild=(BiTree)malloc(sizeof(BiNode)); //申请结点空间 P一>lchild一>data=BT[2*i]; //左子女数据 tq.bt=p一>lchild;tq.num=2*i;real=(rear+1)%maxsize; //计算队尾位置 Q[rear]=tq; //左子女结点及其编号入队 } if(BT[2*i+1]=:'#'∣∣ 2*i+l>len)p->rchild=null; //右子树为空 else{//建立右子女结点并入队列 P一>rchild=(BiTree)malloc(sizeof(BiNode); //申请结点空间 P一>rchild一>data=BT[2*i+1];tq.bt=p一>rchild;tq.Bum=2*i+1: real=(real+1)%maxsize;Q[rear]=tq; //计算队尾位置,右子女及其编号入队 } }//while } 提示:本题中的虚结点用'#'表示,应根据二叉树的结点数据的类型而定。
解析
转载请注明原文地址:https://kaotiyun.com/show/BcCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
清朝的()划定了中俄两国中段边界,是继续谈判确立两国相互关系的全面条约的基础
【供应学派】北京大学2000年欧美现代史真题
下列哪一项不是毛泽东在抗日战争期间的著作?()
晚清时期下列武装力量出现的先后顺序是
中国共产党明确提出构建社会主义和谐社会战略任务的重要会议是()。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是____。
并发使得处理机的利用率得到提高,其主要原因是处理机与10可以同时为多个进程服务,也即处理机与IO设备真正地并行。但是处理机的利用率提高并不是简单地将二个进程的处理机利用率相加,而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发,调度算法采用
随机试题
患者,男,52岁,慢性乙型肝炎病史6年,1个月前出现皮肤金黄色。查体:肝掌、蜘蛛痣。下列各项化验检查结果不正确的是
A.DNAB.RNAC.DNA引物D.RNA引物E.蛋白质Northern杂交被检测的对象
下列选项中,属于隧道监控量测必测项目的有()。
矿产、地质资源属于()。
如果不同交割月份合约价格间关系不正常,只有当价差过大时,交易者才可以采取行动进行跨期套利。( )
绿茶的主要成为是茶多酚。近来大量动物实验发现,茶多酚具有抑制肿瘤细胞增殖、促进肿瘤细胞消亡的作用。但是,有些专家通过对大量人群的研究,并未发现饮茶越多癌症发病率就越低这一现象。据此,他们并不认为经常饮茶能够防癌。以下哪项如果为真。则是上述专家作出结论最合理
根据我国《宪法》的规定,下列有关公民基本权利的宪法保护的表述,正确的是()。
[2011年1月]某年级共有8个班,在一次年级考试中,共有21名学生不及格,每班不及格的学生最多有3名,则(一)班至少有1名学生不及格。(1)(二)班不及格人数多于(三)班;(2)(四)班不及格的学生有2名。
在面向对象的语言中,______是程序设计的基本实体。
阅读以下程序:#includevoidmain(){staticinta[][2]={5,3,1,2};imti,j,sl=0;for(i=0;i<2i++)
最新回复
(
0
)