首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1.2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-01
25
问题
已知深度为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
学硕统考专业
相关试题推荐
下列各组古代民族,其语言都属于印欧语系的是()。
中国第一条自行设计修建的铁路是在()。
我国第一部系统的史学理论著作是()。
简述罗马共和国衰亡的原因。
资产阶级改良道路行不通,资产阶级共和国方案夭折,其共同原因在于()。①中国封建势力的强大②帝国主义列强的直接破坏③资产阶级的软弱妥协④没有充分地发动人民群众
太平天国在1853年冬颁布的纲领性文件是()。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车
真值0在原码、反码和补码机器数形式下()。
一个在以太网中的主机试图发送一个帧,当它尝试了16次仍然失败之后,它应该()。
高度为7的AVL树最少有()个结点。
随机试题
首次提出“在正式组织中存在着非正式组织”观点的是()
属于腧穴远治作用的例子是属于腧穴特殊作用的例子是
张某在某糖酒展销会上购买了一瓶误认为是贵州“茅台酒”的贵州某厂产“芽台酒”,该酒的包装与茅台酒几乎一样,张某将该酒送给朋友李某,李某饮后出现不适,李某向茅台酒厂在该市的代表处投诉,此时方发现该酒不是茅台酒,以下说法正确的是:()
建设工程监理管理服务的内涵不包括( )。
( )科目编码必须按财政部的统一编码方案进行编制。
根据以下材料回答问题。2005年我国全社会固定资产投资88604亿元,比上年增长25.7%。其中,城镇投资75096亿元,增长27.2%;农村投资13508亿元,增长18.0%。在城镇投资中,第一产业投资823亿元,增长27.5%;第二产业投资3
把下面的六个小图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是:
m是一个整数。
A、Shewilldrivethemantothesupermarket.B、Themanshouldbuyacarofhisown.C、Themanneedn’tgoshoppingeveryweek.D、
A、Mexico.B、CentralAmerica.C、U.S.D、Honduras.B新闻中提到墨西哥移民实际上正在逐渐离开美国,与此同时,中美洲的移民数量在上涨,故B为答案。原文是说墨西哥的移民实际上正在逐渐离开美国,并没有提到上涨,排除A和
最新回复
(
0
)