首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2K一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2K一1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child,data,rchild),根结点所在链结点的指针由T给出。
admin
2019-08-15
64
问题
已知深度为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
学硕统考专业
相关试题推荐
华沙条约组织
1870年普鲁士军队侵人巴黎,法国人民组织国民自卫军誓保卫巴黎,参加国民自卫军的大部分是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
路由器采用()方式来发送IP分组。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
简述中断的作用。
随机试题
在健康肉芽组织中不会见到
什么叫焊接化学冶金过程?
区别人参二醇和人参三醇可用
A.0.02%呋喃西林溶液B.0.1%雷佛奴尔溶液C.氧化锌软膏D.10%鱼石脂软膏E.0.75%碘伏保护腹壁造瘘皮肤时用
城市道路横断面规划设计的主要任务是在满足管线敷设以及()等要求的前提下,经济合理地确定横断面各组成部分的宽度、位置排列与高差。
单位工程完工验收由()主持。
商业银行开展金融创新时,关于保护客户利益的表述错误的是()。
拍卖:委托人将物品委托专门机构竞价销售,专门机构在完成委托义务后获得报酬的行为。以下属于拍卖行为的是:
根据域名代码规定,表示政府部门网站的域名代码是()。
Whatistheconversationmainlyabout?
最新回复
(
0
)