首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h-1]中,请写一非递归算法,产生该二叉树的二又链表结构。设二又链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h-1]中,请写一非递归算法,产生该二叉树的二又链表结构。设二又链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-01
17
问题
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2
h
-1]中,请写一非递归算法,产生该二叉树的二又链表结构。设二又链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
选项
答案
二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的,不是完全二叉树的二叉树顺序存储时,要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct{ BiTree bt: //-叉树结点指针 int num; }tnode: //aura是结点在一维数组中的编号 tnode Q[maxsize]; //循环队列,容量足够大 void creat(BiTree T,ElemType BT[]){ //深度h m-Y-树存于一维数组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.hum; //出队,取出结点及编号 if(BT[2*i]==’#’.||2*i>len) p一>lehild=null; //左子树为空,’#’表示虚结点 else{ //建立左子女结点并入队列 p一>lchild=(BiTree)malloc(sizeof(BiNode)); //申请结点空间 P一>lchild一>data=BT[2*i]; //左子女数据 tq.bt=p一>lehild:tq.hum=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.num=2*i+l; rear=(rear+1)%maxsize;Q[rear]=tq;//计算队尾位置,右子女及其编号入队 } }//while }
解析
转载请注明原文地址:https://kaotiyun.com/show/s3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述1919—1945年美英法德日五国外交政策的变化及其原因。
下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约
公元843年,查理曼的三个孙子签订《凡尔登条约》三分查理曼帝国,奠定的三个国家的形是()。①德意志②法兰西③西班牙④意大利
列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。
1962,中共中央调整计划目标,工业生产值原定950亿元调为880亿元,钢产量755万吨调为600万吨,并按“经济合理,保留骨干的原则,对企业关停并转。这举措目标
两极格局结束后,世界形势发展的总态势的基本特点()
下列各种情况中,应采用异步通信方式的是()。
计算机系统中,判断是否有中断事件发生的时机是()。
随机试题
小儿急性肾小球肾炎(阳水)变证水毒内闭的首选方是
在某工程网络计划中,如果发现工作L的总时差和自由时差分别为4天和2天,监理工程师检查实际进度时发现该工作的持续时间延长了1天,则说明工作L的实际进度( )。
在资产评估中,委托方的准备工作内容包括()。
某运输企业位于市区。系增值税一般纳税人,2013年10月发生如下业务:(1)为某企业运输一批原材料,取得货运收入20万元,另外向对方收取包装费2.2万元,给对方开具增值税普通发票。(2)与甲运输企业共同承接一项联运业务,收取全程不含税货运收入75万元.
真正高明的伪造家制造的钞票从不会被发现,所以,一旦他的作品被认出是伪造的,则伪造者不是位高明的伪造者,真正的伪造家从不会被抓到。下列理解方式与这段话类似的是()。
可以预警的自然灾害、事故灾难和公共卫生事件的预警级别,按照突发事件发生的紧急程度、发展势态和可能造成的危害程度分为一级、二级、三级和四级,分别用不同颜色标示,用橙色表表示的是()预警。
《中华人民共和国婚姻法》第二条第三款规定:“实行计划生育。”按照法律原则分类的相关理论,该条文属于()。
A.Studythefollowingchartcarefullyandwriteanessayof160-200words.B.Youressayshouldcoverthesethreepoints:1)
下列数据结构中,不能采用顺序存储结构的是
一间宿舍可住多个学生,则实体宿舍和学生之间的联系是()。
最新回复
(
0
)