首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
45
问题
已知深度为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
学硕统考专业
相关试题推荐
下列关于第二三次科技革命的说法,不正确的是()。
全国高校院系调整的具体时间是()。
下面关于新经济政策的说法不正确的一项是()。
典型的西欧封建庄园对农民采用的剥削方式是()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特,一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。
通过论战体现出来的革命派与改良派的共同之处有()。①都反对帝国主义的侵略,但又都替侵略者开脱罪责②都不敢正面提出反对帝国主义的口号,反而寄希望于帝国主义的支持和赞助③都反对封建专制制度,主张建立民主政体,但又都对反封建的艰巨性缺乏认识
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
用链接方式存储的队列,在进行删除运算时,下面正确的是()。
随机试题
PASSAGEFOUR(1)Thefirstintimation,apparently,waswhenthree-year-oldYvestoldhismotherthathershoesdidnotgow
A.Ⅰ度深覆盖B.Ⅱ度深覆盖C.Ⅲ度深覆盖D.Ⅰ度深覆牙合E.Ⅱ度深覆牙合下前牙切端前后距离为6mm,是指
与冲洗技术没有实际效果的管理方法是
A.印堂、攒竹、合谷B.率谷、外关、足临泣C.血海、膈俞、内关D.天柱、后溪、申脉E.太冲、内关、四神聪
下列关于发票使用的说法正确的有()。
“采购流程”是指采购方从__________(供应商)选择和购买生产、服务经营的各种原材料、零部件、设备等物料的__________。
我国政府一向关心和重视儿童的生存、保护和发展工作,制定了()等一系列相关法律以保护其合法权益。
国家正在进行“营改增”试点。为了更好地贯彻落实这一政策,要进行一次税务宣传活动,领导让你写一个宣传方案,你如何开展?
1940年前后,毛泽东发表了哪些著作,使新民主主义革命理论在多方面展开而达到成熟,形成了一个完整的理论体系()
【S1】【S10】
最新回复
(
0
)