来源：跨考2011-11-25
1．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树 ，根由tree指向。 【南京理工大学 1998 七、1 （6分）】
【参考答案】
BiTree Creat(ElemType A[],int i)
//n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树
{BiTree tree;
if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];
if(2*i>n) tree->lchild=null；else tree->lchild=Creat(A,2*i)；
if(2*i+1>n) tree->rchild=null；else tree->rchild=Creat(A,2*i+1)； }
return (tree)； }//Creat
[算法讨论]初始调用时,i=1。
2．已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。【北京航空航天大学 1999 七、 (15分)】
【参考答案】
[题目分析]二叉树采用顺序存储结构（一维数组）是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。
typedef struct
{BiTree bt; //二叉树结点指针
int num; }tnode // num是结点在一维数组中的编号
tnode Q[maxsize]; //循环队列,容量足够大
void creat(BiTree T,ElemType BT[ ])
//深度h的二叉树存于一维数组BT[1:2h-1]中，本算法生成该二叉树的二叉链表存储结构
{tnode tq; //tq是队列元素
int len=2h-1; //数组长度
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.num=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.num=2*i+1;
rear=(rear+1)%maxsize; Q[rear]=tq; //计算队尾位置,右子女及其编号入队
}
} //while
}//结束creat
[算法讨论] 本题中的虚结点用‘#’表示。应根据二叉树的结点数据的类型而定。