首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-01
58
问题
已知深度为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.num=1; Q[1]:tq; //根入队列 front=0;rear=1; //循环队列头、尾指针 while(front!=rear){ //当队列不空时循环 front=(front+1)%maxsize; tq=Q[front];p=tq.bt;i=tq.num; //出队,取出结点及编号 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+l>len)p一>rchild=null; //右子树为空 else{//建立右子女结点并入队列 p一>rchild=(BiTree)malloc(sizeof(BiNode); //申请结点空间 p一>rchild一>data=BT[2*i+1];tq.bt=p一>rchild;tq.Bum=2*i+1; rear=(Fear+1)%maxsize;Q[rear]=tq: //计算队尾位置,右子女及其编号入队 } }//while } 提示:本题中的虚结点用‘#’表示,应根据二叉树的结点数据的类型而定。
解析
转载请注明原文地址:https://kaotiyun.com/show/qCCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述西欧十字军东侵的历史原因及后果。
下列各组古代民族,其语言都属于印欧语系的是()。
下列选项中,控制了西域政权的是()。
下列哪一个不是罗马王政时代的管理机构?()
一战后,法国对外政策的特点是()。
完整地表述电磁场理论的物理学家是()。
洋务运动期间,军事企业主要采取的组织形式是()。
比较工业革命和第二次工业革命的异同。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
会计规范体系的核心是
参与构成DNA分子的单糖是
天花粉的功效是栀子的功效是
甲某因强奸丙某被公安机关逮捕,甲某之妻乙某为使甲某不受处罚,多次找到被害人丙某,要求其作证证明其与甲某是通奸而不是被强奸,并许诺给丙某2万元的精神损失费,丙某不从,乙某就叫人把丙某关在自己家的地下室里,声称丙某如果不按她说的做,就不放她出去,将丙某拘禁5天
同步能力验证计划是从材料中随机抽取子样,同时分发给参加者共同进行测试,这类计划能较快回收结果。()
保持经济持续增长的源泉包括土地、劳动、资本和技术进步,而经济增长最持久、最根本的源泉是()。
下列建筑物必须采用一级耐火等级的有()。
根据契税法律制度的规定,下列各项中,属于契税纳税人的是()。
世界贸易组织[宁波大学2015、2014国际商务硕士;厦门大学2011国际商务硕士]
针对某种溃疡,传统疗法可在6个月内将44%的患者的溃疡完全治愈。针对这种溃疡的一种新疗法在6个月的试验中使治疗的80%的患者的溃疡取得了明显改善,61%的患者的溃疡得到了痊愈。由于该试验只治疗了那些病情比较严重的患者的溃疡,因此这种新疗法显然在疗效方面比传
最新回复
(
0
)