首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
29
问题
已知深度为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
学硕统考专业
相关试题推荐
唐太宗、武则天、唐玄宗(前期)都共同注意的问题是()
下列关于第二三次科技革命的说法,不正确的是()。
中华人民共和国恢复在联合国合法席位的时间是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
下列说法中,全部符合历史事实的是()。①阿拉伯阿拔斯王朝的首都是麦地那②穆罕默德死后,他的继承人改称为哈里发,第三任哈里发奥斯曼时期,部分下层莫斯林组建了军事民主派,称为哈瓦立及派③阿拉伯人灭亡了具有1200年历史的波斯帝国的战役是雅穆克
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
洪武八年,朱元璋仿照元朝的办法,印造(),命令民间通行,形成了钱、钞并用的货币制度
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
随机试题
A、scissorsB、scoreC、screenD、sculptureA画线部分读[s),其他选项的画线部分读[sk]。
关于人体实验中的知情同意,正确的是
“飞鸽”文字是D国甲公司使用在油漆、涂料等商品上的商标。该商标在中国和其他许多国家进行了商标注册,并在世界同行业中具有很高的知名度。该公司还在中国设有销售部。中国乙公司在其生产的室内装修板材上突出使用“飞鸽板材”字样。甲公司认为此种行为侵犯了其商标专用权。
我国银行可以发行以人民币计价的大额定期存单,也可以发行以外币计价的大额定期存单。()
关于维护宪法尊严,保障宪法实施,下列哪一做法是错误的?()
债权让与,是指不改变债的关系的内容,债权人将其债权移转于第三人并将债权移转行为通知债务人的法律行为。其中的债权人成为转让人,第三人成为受让人。下列情形中,构成债权让与的是()。
若对序列(tang,deng,an,wang,shi,bai,fang,liu)采用简单选择排序法按字典顺序进行排序,下面给出的四个序列中,第三趟的结果是()。
Whydon’tAmericanpeopleliketogetadvicefrompeopletheyknow?
ChildrenasyoungasfourwillstudyShakespeareinaprojectbeinglaunchedtodaybytheRoyalShakespeareCompany.TheRSC
A、Shewasinvitedonlyfortheweekend.B、Theweatherwastoohot.C、Shehadanappointment.D、Shehasschoolworktodo.D考生需要听
最新回复
(
0
)