数据结构考研分类复习真题 第六章 答案 (五)[7]

[题目分析]二叉树采用顺序存储结构（一维数组）是按完全二叉树的形状存储的不是完全二叉树的二叉树顺序存储时要加虚结点数组中的第一个元素是根结点本题中采用队列结构

typedef struct

{BiTree bt; //二叉树结点指针

int num; }tnode // num是结点在一维数组中的编号

tnode Q[maxsize]; //循环队列容量足够大

void creat(BiTree TElemType BT[ ])

//深度h的二叉树存于一维数组BT[:h]中本算法生成该二叉树的二叉链表存储结构

{tnode tq; //tq是队列元素

int len=h; //数组长度

T=(BiTree)malloc(sizeof(BiNode)); //申请结点

T>data=BT[]; //根结点数据

tqbt=T; tqnum=;

Q[]=tq; //根入队列

front=;rear=; //循环队列头尾指针

while(front!=rear) //当队列不空时循环

{front=(front+) % maxsize ;

tq=Q[front] ; p=tqbt; i=tqnum ; //出队取出结点及编号

if (BT[*i]==#||*i>len) p>lchild=null; //左子树为空#表示虚结点

else //建立左子女结点并入队列

{p>lchild=(BiTree) malloc(sizeof(BiNode)); //申请结点空间

p>lchilddata=BT[*i]; // 左子女数据

tqbt=p>lchild; tqnum=*i; rear=(rear+) % maxsize ;//计算队尾位置

Q[rear]=tq; //左子女结点及其编号入队

}

if(BT[*i+]==#|| *i+>len) p>rchild=null; //右子树为空

else //建立右子女结点并入队列

{p>rchild=(BiTree)malloc(sizeof (BiNode); //申请结点空间

p>rchild>data=BT[*i+]; tqbt=p>rchild; tqnum=*i+;

rear=(rear+)%maxsize; Q[rear]=tq; //计算队尾位置右子女及其编号入队

}

} //while

}//结束creat

[算法讨论] 本题中的虚结点用#表示应根据二叉树的结点数据的类型而定

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []