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

．[题目分析] 二叉树的层次遍历序列的第一个结点是二叉树的根实际上层次遍历序列中的每个结点都是局部根确定根后到二叉树的中序序列中查到该结点该结点将二叉树分为左根右三部分若左右子树均有则层次序列根结点的后面应是左右子树的根若中序序列中只有左子树或只有右子树则在层次序列的根结点后也只有左子树的根或右子树的根这样定义一个全局变量指针R指向层次序列待处理元素算法中先处理根结点将根结点和左右子女的信息入队列然后在队列不空的条件下循环处理二叉树的结点队列中元素的数据结构定义如下

typedef struct

{ int lvl; //层次序列指针总是指向当前根结点在层次序列中的位置

int lh; //中序序列的下上界

int f; //层次序列中当前根结点的双亲结点的指针

int lr; // 双亲的左子树 双亲的右子树

}qnode;

BiTree Creat(datatype in[]level[]int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树 n是二叉树的结点数

{if (n<) {printf(参数错误\n); exit();}

qnode sQ[]; //Q是元素为qnode类型的队列容量足够大

init(Q); int R=; //R是层次序列指针指向当前待处理的结点

BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点

p>data=level[]; p>lchild=null; p>rchild=null; //填写该结点数据

for (i=; i<n; i++) //在中序序列中查找根结点然后左右子女信息入队列

if (in[i]==level[]) break;

if (i==) //根结点无左子树遍历序列的n是右子树

{p>lchild=null;

slvl=++R; sl=i+; sh=n; sf=p; slr=; enqueue(Qs);

}

else if (i==n) //根结点无右子树遍历序列的n是左子树

{p>rchild=null;

slvl=++R; sl=; sh=i; sf=p; slr=; enqueue(Qs);

}

else //根结点有左子树和右子树

{slvl=++R; sl=; sh=i; sf=p; slr=;enqueue(Qs);//左子树有关信息入队列

slvl=++R; sl=i+;sh=n;sf=p; slr=;enqueue(Qs);//右子树有关信息入队列

}

while (!empty(Q)) //当队列不空进行循环构造二叉树的左右子树

{ s=delqueue(Q); father=sf;

for (i=sl; i<=sh; i++)

if (in[i]==level[slvl]) break;

p=(bitreptr)malloc(sizeof(binode)); //申请结点空间

p>data=level[slvl]; p>lchild=null; p>rchild=null; //填写该结点数据

if (slr==) father>lchild=p;

else father>rchild=p //让双亲的子女指针指向该结点

if (i==sl)

{p>lchild=null; //处理无左子女

slvl=++R; sl=i+; sf=p; slr=; enqueue(Qs);

}

else if (i==sh)

{p>rchild=null; //处理无右子女

slvl=++R; sh=i; sf=p; slr=; enqueue(Qs);

}

else{slvl=++R; sh=i; sf=p; slr=; enqueue(Qs);//左子树有关信息入队列

slvl=++R; sl=i+; sf=p; slr=; enqueue(Qs); //右子树有关信息入队列

}

}//结束while (!empty(Q))

return(p);

}//算法结束

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