首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
71
问题
已知深度为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
学硕统考专业
相关试题推荐
下列不属于“五反”运动内容的是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
典型的西欧封建庄园对农民采用的剥削方式是()。
第一次鸦片战争、第二次鸦片战争的时间,分别对应于法国的()时期和()时期。
英国革命中。平等派的领导人是()。
中国第一条自行设计修建的铁路是在()。
下列选项中,控制了西域政权的是()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
在网络中计算机接收的信号是()。
随机试题
关于妇女保健工作的意义下列说法不正确的是
根据提供的“沙尘暴简介.docx”文件,制作名为“沙尘暴”的演示文稿,具体要求如下:有演示主题,有标题页,在第一页上要有艺术字形式的“爱护环境”字样。选择一个主题应用于所有幻灯片。
某地多日暴雪,甲在公交站等车时,站台顶棚因积雪过多塌落,将甲砸伤。该公交站站台系乙公司设计、丙公交公司管理。甲的损害应由
佝偻病激期X线表现软骨营养不良X线表现
“一源而三歧”的奇经是指
建筑物对地基的要求主要有()。
()是商业银行支付给员工的业绩报酬和增收节支报酬,主要根据当年经营业绩考核结果来确定。
陕西终南山重阳宫与北京白云观、山西芮城永乐宫并称全真道三大祖庭。()
以下关于定员标准的说法,错误的是()。
党的十六大以来,以胡锦涛为总书记的党中央高举和平、发展、合作的旗帜,坚持独立自主的和平外交政策。强调
最新回复
(
0
)