首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-01
46
问题
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2
h
一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
选项
答案
二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的,不是完全二叉树的二叉树顺序存储时,要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct{ BiTree bt: //二叉树结点指针 int Bum; }tnode: //Bum是结点在一维数组中的编号 tnode Q[maxsize]; //循环队列,容量足够大 void creat(BiTree T,ElemType BT[]){ //深度h的二叉树存于一维数组BT[1.2
h
一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]==‘#’||2*i>len) p->lchild=null; //左子树为空,‘#’表示虚结点 else{ //建立左子女结点并入队列 p一>lchild=(BiTree)malloc(sizeof(BiNode)); //申请结点空间 p一>lchild一>data=BT[2*i]: //左子女数据 tq.bt=p一>lchild; tq.Bum=2*i;rear=(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; rear=(Fear+1)%maxsize;Q[rear]=tq: //计算队尾位置,右子女及其编号入队 } }//while } 提示:本题中的虚结点用‘#’表示,应根据二叉树的结点数据的类型而定。
解析
转载请注明原文地址:https://kaotiyun.com/show/qCCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述西欧城市兴起的原因、方式及其影响。
()是二战后一个调整各国贸易关系的法律框架,又是一个进行多边贸易谈判、争夺市场的场所,还是一个调解和解决争议的机构。
建国以来,根据我国民族状况自身特点,民族自治地方人民代表大会依据全国人民代表大会制定的有关法律,先后制定了若干自治条例和单行条例;全国依法建立了155个民族自治地方,少数民族当家作主的权利得到充分保障。同时,国家采取一系列措施,加大支持力度,促进了民族自治
武则天时期,为了管理天山以北的广大区域而设立了()。
到1869年为止,人类已发现了多少种化学元素()。
最早以立法的形式巩固大化改新成果的法令是()。
《中国国民党改组宣言》发表的时间是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
随机试题
A.活动时不需要任何人的帮助B.完成动作时需要他人监护或体力上的帮助C.患者付出的力占完成动作所需全部用力的50%以上D.患者不能付出任何力,完成动作需要完全帮助E.患者付出的力占完成动作所需全部用力的50%以下,完成动作需要最大或完全的帮
某地面散养成年蛋鸡群中,发现鸡产蛋量下降,下痢,消瘦,食欲缺乏,部分病鸡冠、髯部发绀。调查发现鸡场地面存在蚯蚓,剖检发现盲肠肿大,肠壁发炎和增厚,有溃疡。该寄生虫还能传播下列哪种疾病
下列选项中。不是小儿腹泻的病因的是
善治血淋,尿血的药物是
中等复杂湿陷性黄土场地上拟建甲类建筑物,详细勘察时,勘探点间距宜取()m。
货币供不应求,利率上升;货币供过于求,利率下降。因而适当调节利率水平,就可以直接凋节()。
某甲出生在美国,父亲是中国人,母亲是美国人,父母定居在美国。根据中国国籍法的规定,关于某甲国籍的正确表述是()。
在数据库技术中,数据模型分为概念数据模型和结构数据模型,常用的实体-联系模型(E-R模型)属于______数据模型。
数据库系统的三级模式包括概念模式、物理模式和【】模式。
下列叙述中正确的是()。
最新回复
(
0
)