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

[题目分析]知二叉树中序序列与后序序列第题以递归算法建立了二叉树本题是非递归算法

void InPostCreat(ElemType IN[]POST[]int lhlh)

//由二叉树的中序序列IN[]和后序序列POST[]建立二叉树lh和lh分别是中序序列和

//后序序列第一和最后元素的下标初始调用时l=l=h=h=n

{typedef struct {int lhlh; BiTree t; }node;

node s[]p;//s为栈容量足够大

BiTree bt=(BiTree)malloc(sizeof(BiNode)); int top=i;

pl=l; ph=h; pl=l; ph=h; pt=bt; s[++top]=p;//初始化

while(top>)

{p=s[top]; bt=pt; l=pl; h=ph; l=pl; h=ph;//取出栈顶数据

for(i=l;i<=h;i++) if(IN[i]==POST[h]) break;//在中序序列中查等于POST[h]的结点

bt>data=POST[h]; //根结点的值

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

else //将建立左子树的数据入栈

{bt>lchild=(BiTree)malloc(sizeof(BiNode)); pt=bt>lchild;

pl=l; ph=i; pl=l; ph=l+il; s[++top]=p; }

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

else {bt>rchild=(BiTree)malloc(sizeof(BiNode)); pt=bt>rchild;

pl=i+; ph=h; pl=l+il; ph=h; s[++top]=p; }//右子树数据入栈

}// while(top>)

}结束InPostCreat

．BiTree Copy(BiTree t)//复制二叉树t

{BiTree bt;

if (t==null) bt=null;

else{bt=(BiTree)malloc(sizeof(BiNode)); bt>data=t>data;

bt>lchild=Copy(t>lchild);

bt>rchild=Copy(t>rchild);

}

return(bt); }//结束Copy

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