首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
70
问题
已知深度为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.nun=1; Q[1]=tq; //根入队列 front=0;rear=1; //循环队列头、尾指针 while(front!=rear){ //当队列不空时循环 front=(front+1)%maxsize: tq=Q[front];P=tq.bt;i=tq.nun; //出队,取出结点及编号 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+1>len)p一>rchild=null; //右子树为空 else{//建立右子女结点并入队列 P一>rchild=(BiTree)malloc(sizeof(BiNode); //申请结点空间 P一>rchild一>data=BT[2*i+1];tq.bt=p->rchild;tq.nun=2*i+1: rear=(rear+1)%maxsize;Q[rear]=tq; //计算队尾位置,右子女及其编号入队 } }//while }
解析
转载请注明原文地址:https://kaotiyun.com/show/YYRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列对1918年德国十一月革命说法不正确的是()。
论述宋初加强中央集权的主要措施。
下列选项中,属于汉武帝时期削弱地方诸侯势力的措施是()。①推恩令②左官律③附益法④酎金夺爵
论述欧洲一体化进程及其影响。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:明朝推行一条鞭法中“一”的内容是()
马克思和恩格斯之所以能创立科学社会主义理论,主要是由于()。
编写判定给定的二叉树是否是二叉排序树的函数。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijkstra算法求出从结点A到所有其他结点的最短路由。
随机试题
B公司是一家上市公司,2009年年末公司总股份为10亿股,当年实现净利润为4亿元。公司计划投资一条新生产线,总投资额为8亿元,经过论证,该项目具有可行性。为了筹集新生产线的投资资金,财务部制定了两个筹资方案供董事会选择:方案一:发行可转换公司债券
下列选项属于按劳分配的是
论述纵隔的临床解剖分区和常见的纵隔肿瘤。
A.大肠杆菌B.破伤风杆菌C.金黄色葡萄球菌D.链球菌E.铜绿假单胞菌疖常见致病菌是()
对于等渗性脱水,下列不正确的叙述是
关于井巷工程辅助费,不正确的说法是()。
《中华人民共和国教师法》规定,取得初级中学教师,初级职业学校文化、专业课教师资格,应当具备()。
公文处理的准确性原则的具体要求是()。
对于i,j两种证券,如果CAPM成立,那么下列()条件可以推出E(Ri)=E(Rj)?[中央财经大学2011研]
设循环队列的存储空间为Q(1:m),初始状态为front=rear=m。经过一系列正常的操作后,front=1,rear=m。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为
最新回复
(
0
)