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

[题目分析]对一般二叉树仅根据一个先序中序后序遍历不能确定另一个遍历序列但对于满二叉树任一结点的左右子树均含有数量相等的结点根据此性质可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）

void PreToPost(ElemType pre[] post[]int lhlh)

//将满二叉树的先序序列转为后序序列lhlh是序列初始和最后结点的下标

{if(h>=l)

{post[h]=pre[l]; //根结点

half=(hl)/; //左或右子树的结点数

PreToPost(prepostl+l+halfll+half) //将左子树先序序列转为后序序列

PreToPost(prepostl+half+hl+halfh) //将右子树先序序列转为后序序列

} }//PreToPost

BiTree IntoPost(ElemType in[]post[]int lhlh)

//in和post是二叉树的中序序列和后序序列lhlh分别是两序列第一和最后结点的下标

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

bt>data=post[h];//后序遍历序列最后一个元素是根结点数据

for(i=l;i<=h;i++) if(in[i]==post[h])break;//在中序序列中查找根结点

if(i==l) bt>lchild=null; //处理左子树

else bt>lchild=IntoPost(inpostlill+il)

if(i==h) bt>rchild=null; //处理右子树

else bt>rchild=IntoPost(inposti+hl+ilh);

return(bt); }

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