首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
79
问题
已知深度为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://www.kaotiyun.com/show/YYRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读以下史料,并回答问题:“为政以德,譬如北辰,居其所而众星共之。”“富与贵,是人之所欲也。不以其道得之,不处也。贫与贱,是人之所恶也。不以其道得之,不去也。君子去仁,恶乎成名?君子无终食之间违仁,造次必于是,颠沛必于是。”问题:对这一思想家的思
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
分析论述斯大林社会主义工业化。
典型的西欧封建庄园对农民采用的剥削方式是()。
下列改革措施中,不属于北魏孝文帝时期的是
中国第一条自行设计修建的铁路是在()。
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
编写判定给定的二叉树是否是二叉排序树的函数。
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
随机试题
工件装夹方法不正确,会造成工件变形。()
由若干宽度相等、高度不一的直方条紧密排列在同一基线上构成的图形是()
口唇疱疹常由哪种病毒引起
诊断脾破裂最有意义的检查结果是诊断胃穿孔最有价值的检查结果是
患者,女性,63岁,因支气管扩张合并肺部感染、左心衰竭入院治疗,入院时体温39℃,呼吸急促,端坐呼吸。患者以往有骨质疏松,自行长期口服活性钙,护士应嘱咐患者()。
出现()情况,设备供货方应承担违约责任。
国内外研究成果和实践经验表明,建筑消防性能化设计方法是一种()的防火设计方法。
某公司出售专用设备一台,取得价款30万元(不考虑增值税),发生清理费用5万元(不考虑增值税),该设备的账面价值为22万元,不考虑其他因素,下列各项中,关于此项交易净损益会计处理结果表述正确的是()。
下列各项中,()是基线质量,是最基本的需求满足。
“书圣”王羲之的代表作是________。
最新回复
(
0
)