首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2K一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2K一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-15
22
问题
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2
K
一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
选项
答案
二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的,不是完全二叉树的二叉树顺序存储时,要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typeclef struct { BiTree bt: //二叉树结点指针 int num; }tnode: //num是结点在一维数组中的编号 tnode Q[maxsize]; //循环队列,容量足够大 void creat(BiTree T,ElemType BT[]){ //深度h的二叉树存于一维数组BT[1..2
k
一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]=='#'∣∣112*i>len)p->lchild=null; //左子树为空,'#'表示虚结点 else{ //建立左子女结点并入队列 p一>lchild=(BiTree)malloc(sizeof(BiNode)); //申请结点空间 P一>lchild一>data=BT[2*i]; //左子女数据 tq.bt=p一>lchild;tq.num=2*i;real=(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: real=(real+1)%maxsize;Q[rear]=tq; //计算队尾位置,右子女及其编号入队 } }//while } 提示:本题中的虚结点用'#'表示,应根据二叉树的结点数据的类型而定。
解析
转载请注明原文地址:https://kaotiyun.com/show/BcCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
商代青铜器的制作技术很高,尤其是礼器的制作,造型美观,纹饰精巧,是水平极高的工艺品,其中主流的花纹是()。
中华民国军政府是由下列哪个军阀成立的?()
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
著名的网络OSI七层模型是由()组织提出来的。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因。
对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,为实现编号可采用的遍历是()。
用户程序发出磁盘I/O请求后,系统的处理流程是:用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中,计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
在单CPU和两台输入/输出设备(I1,I2)的多道程序设计环境下,同时投入3个作业J1、J2和J3运行。这3个作业对CPU和输入/输出设备的使用顺序和时间如下所示。J1:12(30ms);CPU(10ms);11(30ms);CPU(10
随机试题
为2岁以下婴幼儿肌内注射,最佳注射部位是
请回答有关摆式仪测试路面摩擦系数方法问题。摆式仪测试路面摩擦系数方法测试步骤如下,正确的顺序是()。①指针调零。②仪器调平。③用喷水壶浇洒测点处路面,使之处于湿润状态。④校核滑动长度。⑤清洁路面。⑥将摆固定在右侧悬臂上,使摆处于水平
通常声波的频率范围是:
自动化仪表调校应遵循的原则是()。
在国际上,施工企业项目经理是企业任命的一个项目的项目管理班子的负责人,其主要任务是()。
棉短绒( )
17,26,37,50,( )
申请宣告死亡的利害关系人顺序是( )。
A、 B、 C、 D、 A
ThecomparativelytreelessplainsofNorthAfricahavesufferedaprogressivedryingup,both【S1】______andman-made,butthere
最新回复
(
0
)