．[題目分析]第題已討論了在中序線索樹中查找結點p的後序後繼問題本題要求在中序線索樹上進行後序遍歷因後序遍歷是左右根最後訪問根結點即只有從右子樹返回時才能訪問根結點為此設一標志returnflag當其為時表示從右側返回可以訪問根結點為了找當前結點的後繼需知道雙親結點的信息在中序線索樹中某結點最左子孫的左線索和最右子孫的右線索均指向其雙親因此設立兩個函數LeftMost和RightMost求結點的最左和最右子孫為了判定是否是從右子樹返回再設一函數IsRightChild
BiThrTree LeftMost(BiThrTree t) //求結點t最左子孫的左線索
{BiThrTree p=t;
while(p>ltag==) p=p>lchild; //沿左分枝向下
if (p>lchild!=null) return(p>lchild); else return(null);
}//LeftMost
BiThrTree RightMost（BiThrTree t）//求結點t最右子孫的右線索
{BiThrTree p=t;
while(p>rtag==) p=p>rchild; //沿右分枝向下
if (p>rchild!=null) return (p>rchild); else return(null);
}//RightMost
int IsRightChild(BiThrTree tfather) //若t是father 的右孩子返回否則返回
{father=LeftMost(t);
if(father &&f ather>rchild==t) return(); else return();
}//Is RightChild;
void PostOrderInThr (BiThrTree bt) //後序遍歷中序線索二叉樹bt
{BiThrTree father p=bt;
int flag;
while(p!=null)
{while(p>ltag== ) p=p>lchild; // 沿左分枝向下
if(p>rtag==) flag=;//左孩子為線索右孩子為鏈相當從左返回
else flag=; //p為葉子相當從右返回
while(flag==)
{visit(*p);//訪問結點
if(IsRightChild(pfather)) {p=father; flag=;} //修改p指向雙親
else //p是左子女用最右子孫的右線索找雙親
{p=RightMost(p);
if(p&&p>rtag==) flag=; else flag=;
}
}// while(flag==)
if(flag== && p!=null) p=p>rchild; //轉向當前結點右分枝
} }//結束PostOrderInThr
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23691.html
