首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2k一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2k一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
34
问题
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2
k
一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
选项
答案
二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的,不是完全二叉树的二叉树顺序存储时,要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct{ BiTree bt; //二叉树结点指针 int num; }tnode; //num是结点在一维数组中的编号 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=l; 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->lehild;tq.num=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.num=2*i+1; rear=(rear+1)%maxsize;Q[rear]=tq; //计算队尾位置,右子女及其编号入队 } }//while }
解析
转载请注明原文地址:https://kaotiyun.com/show/5lRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
党锢事件发生后,清议的浪潮更为高涨,度辽将军()没有被当做名士列入党锢,甚至自陈与党人的关系,请求连坐。
在下列各项中,不属于列宁《四月提纲》内容的是()。
下列不属于“一国两制”的基本内容的是()。
论述罗马共和国早期对外征服的过程和历史意义。
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
袁世凯在控制自己权力,实现对全国控制的过程中,主要颁布的法律不包括()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
宋代至清代我国书籍印刷的主要方式是()
下列关于塞尔维乌斯改革的叙述中,不正确的是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
综合性的文学定义是什么?共有哪几个命题?
现在西方各国议会下院议员选举的选区划分都是按()
易受超声影响的敏感人体器官组织是
根据《建设工程施工劳务分包合同(示范文本)》(GF—2003—0214),劳务分包人在施工场地内自有施工机械设备的保险手续应由()办理,并支付保险费用。
建设工程评标分为()等过程。
下面是五年级综合实践活动《城管叔叔,我也行》有了一个主题,该如何开展呢?同学们又犯愁了,一个星期过去了,学生又恢复了往日的平静,沉不住气的我盘问道:“活动怎么样了啊?”同学们:“您说过要开
粤西酒店如果既有清蒸石斑,又有白灼花螺,则一定会有盐焗花蟹;酒店在月尾从不卖盐煽花蟹;只有当粤西酒店卖白灼花螺时,老王才会与朋友到粤西酒店吃海鲜。如果上述断定为真,以下哪项一定为真?
AlthoughHenryFord’snameiscloselyassociatedwiththeconceptofmassproduction,heshouldreceiveequalcreditforintrodu
There’snofuninspendingthewholeeveningplayingcards.
(22-20-18-16)-(20-18-16-14)=
最新回复
(
0
)