首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-01-16
76
问题
已知深度为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
学硕统考专业
相关试题推荐
下面有关兵制的内容,与唐玄宗有关的是()
明治维新的主要内容不包括()。
北约和华约两个组织对峙近半个世纪,其影响是()。
冶铁技术中的淬火法提高了铁器的坚韧与锋利程度,这一技术最早出现在()。
秦始皇焚书时未被列入焚书范围的是()。
论述欧洲一体化的进程及影响。
1908年安庆新军起义是由()领导的。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
用链接方式存储的队列,在进行删除运算时,下面正确的是()。
随机试题
Didyoueverhavesomeone’snameonthetipofyourtongueandyetyouwereunabletorecallit?【C1】______thishappensagain,do
如图所示正方形截面对z1轴的惯性矩与对z轴惯性矩的关系是:
某超市位于居民区内,该居民区人口密集。某晚19时22分,该超市发生火灾,经过3个小时的扑救,将火扑灭。这起火灾事故造成2人死亡,9人重伤,直接经济损失260万元。根据《生产安全事故报告和调查处理条例》(国务院令第493号),这起事故等级属于(
利须商贸公司于2007年3月2日办理了工商登记并领取了营业执照,会计张某于当月办理了税务登记并领取了税务登记证,随即在注册地银行开立了基本存款账户。5月4日该公司出纳签发了一张支票,但未在支票上注明收款人姓名和金额;6月公司聘用了一位退休老会计担任出纳,他
下列各项,应通过“固定资产清理”科日核算的有()。
村集体经济组织本年实现的收益总额指的是()。
伤亡事故报告和处理制度的内容,包括()
根据以下资料,回答下列问题。2017年,A省完成邮电业务总量6065.71亿元。其中,电信业务总量3575.86亿元,同比增长75.8%;邮政业务总量2489.85亿元,增长32.0%。2017年,A省移动电话期末用户1.48亿户,比上
向量组α1,α2,…,αm线性无关的充分必要条件是().
A、Becauseeveryengineermustworkwiththesesciences.B、Becauseeveryengineerknowsalotofthem.C、Becausethetwosciences
最新回复
(
0
)