2. 考研
  3. 已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1．．2K一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由T给出。

已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1．．2K一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由T给出。

admin2019-08-15  44
问题 已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1．．2K一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．．2k一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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)