首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-01
49
问题
已知深度为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
学硕统考专业
相关试题推荐
论述王莽改制的内容并分析失败的原因。
论述西欧十字军东侵的历史原因及后果。
试述1946年政治协商会议的主要原因及意义。
简述十字军东侵的原因和影响。
标志着整风运动开始向反“右派”斗争转变的重要文件是()。
下列法律文件中,规定内阁对君主负责的是()。
下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
两个进程P、Q都需要三个资源1,2,3,系统中有资源1、2、3各一个,如果P请求资源的顺序是1、2、3,Q请求资源的顺序任意,共有3!=6种排列,其中共有()个排列可能导致死锁。
随机试题
相向接头是指两焊缝在起头处连接。
测原油含水,称样要准确,精确到()和0.05mL。
患者,男,45岁,神疲乏力,畏寒肢冷,腰膝酸软,脉沉迟,应选用()
不是线性药物动力学模型的识别方法的有
根据《国家突发环境事件应急预案》,以下属特别重大环境事件的是()。
我国发明专利的保护期为()。
背景资料某施工单位承接了跨度为105m+180m+105m三跨预应力混凝土连续刚构桥的施工。施工单位在整个箱梁浇筑过程中主要施工过程如下:(1)在桥墩上按0号块设计标高安装托架并与桥墩可靠连接,托架承载力按0号块理论重量的130%设计,托架安装后开始绑
下列说法符合不记名股票特点的有()。
在稀疏矩阵所对应的三元组线性表中,每个三元组元素按【】为主序排列。
若在窗体设计过程中,命令按钮Command0的事件属性设置如下图所示,则含义是( )。
最新回复
(
0
)