．[題目分析]在中序穿線二叉樹中求某結點p的後序後繼q需要知道p的雙親結點f的信息（中序線索樹的性質若p是f的左子女則f是p的最右子孫的右線索若p是f的右子女則f是p的最左子孫的左線索）找到f後若p是f的右子女則p的後繼是f若p是f的左子女且f無右子女則p的後繼也是f若p是f的左子女且f有右子女則f的右子樹中最左邊的葉子結點是p的後繼因此算法思路是先找p的雙親f根據p是f的左/右子女再確定p的後序後繼
BiThrTree InThrPostSucc(BiThrTree rp)
//在中序線索二叉樹r上求結點p（假定存在）的後序後繼結點q）
{if(p==r)return(null) //若p為根結點後序後繼為空
T=p
while(T>LT==) T=T>LL; //找p的最左子孫的左線索
q=T>LL; //q是 p最左子孫的左線索是p的祖先
if(q>RL==p) return(q); //p是q的右子女則q是p後序後繼
T=p;
while(T>RT==) T=T>RL; //找p的最右子孫的右線索
q=T>RL; //q是p最右子孫的右線索
if(q>LL=p) //若p是q的左子女
if(q>RT==) return(q);//若p是q的左子女且q無右子女則p的後序後繼是q
else //p的雙親q有右子樹則q的右子樹上最左下的葉子結點是p的後繼
{q=q>RL;
while(q>LT==||q>RT==) //找q右子樹中最左下的葉子結點
{while(q>LT==) q=q>LL; //向左下
if(q>RT==) q=q>RL; //若q無左子女但有右子女則向右下直到葉子結點
}
return(q); //q是的p後繼
}
} //結束InThrPostSucc
[算法討論] 請注意本題條件標記為時是線索而為時是指向子女
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23690.html
