[題目分析]二叉樹結點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)
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23724.html
