首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2k一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2k一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
32
问题
已知深度为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
学硕统考专业
相关试题推荐
解放军渡江战役中横渡长江的东西两个攻击点是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争。这一古老文件是()
在意大利统一过程中,加富尔为了获得拿破仑三世的支持,让与法国的领土是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
试述西欧城市兴起的原因、方式及其影响。
下列历史事件发生的先后顺序是()。①“铁幕”演说②马歇尔计划③北大西洋公约
下列哪一个不是罗马王政时代的管理机构?()
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
假设在一台单处理机上执行如下表所示的进程,且假定这些进程在时刻0以1,2,3,4,5的顺序创建。时间单位为时间片,优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时,这些进程的执行
随机试题
建设社会主义文化强国的关键是()。
Sixteenyearsago,EileenDoyle’shusband,anengineer,tookhisfourchildrenupforanearlymorningcupoftea,packedasmal
患儿5个月,提前半个月因宫内缺氧剖宫产,出生时体重2.6kg。现在竖头不稳,不能独坐,翻身,双手无取物意识,四肢肌张力低下,母亲怀孕期间有感冒疾病史。此期的主要干预措施有
患者男性,35岁,血胸置闭式胸膜腔引流,引流用的水封瓶放在
家畜心脏的正常形态是()
工程咨询单位负责市场开发、组织项目技术服务的管理层是()。
学前教育行动研究的目的是()。
请在“答题”菜单下选择“字处理”命令,然后按照题目要求再打开相应的命令,完成下面的内容,具体要求如下:设置表格行高为0.8厘米,设置第1、2列的列宽为4厘米,第3、4列的列宽为3厘米;设置表格外框线为1.5磅红色双实线,内框线为0.75磅黄色单实线。
CanMixofTeachers,ComputersLeadtoPupilSuccess?[A]WhenvisitorstotheCarpeDiemcharterschoolsee175studentswea
Asaphysicianwhotravelsquitealot,Ispendalotoftimeonplaneslisteningforthatdreaded"Isthereadoctorunboard?"
最新回复
(
0
)