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

[题目分析]二叉树结点p所对应子树的第一个后序遍历结点q的求法如下若p有左子树则q是p的左子树上最左下的叶子结点若p无左子树仅有右子树则q是p的右子树上最左下的叶子结点

BiTree PostFirst(p)

{BiTree q=p;

if (!q) return(null); else

while(q>lchild || q>rchild); //找最左下的叶子结点

if(q>lchild) q=q>lchild; //优先沿左分枝向下去查最左下的叶子结点

else q=q>rchild; //沿右分枝去查最左下的叶子结点

return(q);

}

[算法讨论]题目求p所对应子树的第一个后序遍历结点蕴涵p是子树的根若p是叶子结点求其后继要通过双亲

()由先序序列A[n]和中序序列B[n]可以确定一棵二叉树详见本章四第题

（）void PreInCreat( ElemTypeA[]B[]int lhlh)

//由二叉树前序序列A[n]和中序序列B[n]建立二叉树lh和lh分别为先序序列和

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

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

BiTree bt;

int top=i; node s[]p; //s为栈容量足够大

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

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(B[i]==A[l]) break; //到中序序列中查根结点的值

bt>data=A[l]; //A[l]为根结点的值

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

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

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

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

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

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

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

}//while

}结束PreInCreat

()当二叉树为单支树时栈深n当二叉树左右子树高相等时栈深logn时间复杂度O(n)

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