首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
81
问题
已知深度为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
学硕统考专业
相关试题推荐
下列对1918年德国十一月革命说法不正确的是()。
北宋时期,对市场商品价格管理主要采取()。
雅尔塔体系、两极格局、“冷战”三者的区别与联系是什么?
两汉时期,下列没有通过丝绸之路传入西方的技术是()。
《关于建国以来党的若干历史问题的决议》指出:“我们现在赖以进行现代化建设的物质技术基础,很大一部分是这个期间建设起来的,全国经济文化建设等方面的骨干力量和他们的工作经验,大部分也是在这个期间培养和积累起来的,这是这个期间党的T作的主导方面。”“这个期间”是
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
随机试题
PDCA管理循环中,P指的是
与釉柱排列相关的结构是
哪种二维切面观察动脉导管未闭比较好
Horner综合征的表现,不含
可乐定的不良反应为米诺地尔的不良反应为
引起气性坏疽的致病菌是()。
甲公司2015年至2016年与无形资产和投资性房地产有关的业务资料如下:(1)2015年1月1日,甲公司开始自行研究开发一项专利技术用于产品生产,2015年1月至3月为研究阶段,共发生相关支出300万元,从2015年4月份开始进入开发阶段,开发阶段共发生
运用任务驱动教学法进行教学时,任务的设计是关键。教师在设计任务时应该注意哪些方面?
波臣画派的开派画家是()。
人民币(RenminbiorRMB)是中国大陆地区的法定货币。中国人民银行(thePeople’sBankofChina)是国家管理人民币的主要机构,负责人民币的设计、印制和发行。从1948年开始,人民币一共发行了五套。目前市场上流通的主要是第
最新回复
(
0
)