[題目分析]求中序全線索樹任意結點p的前序後繼其規則如下若p有左子女則左子女就是其前序後繼若p無左子女而有右子女則p的右子女就是p的前序後繼若p無左右子女這時沿p的右線索往上直到p的右標志為（非線索）這時若p的右子女為空則表示這是中序遍歷最後一個結點故指定結點無前序後繼否則該結點就是指定結點的前序後繼程序段如下
if(p>ltag== && p>lchild!=null) return(p>lchild); //p的左子女是p的前序後繼
else if(p>rtag==) && p>rchild!=null) return(p>rchild);//p右子女是其前序後繼
else //p無左右子女應沿右線索向上（找其前序後繼）直到某結點右標記為
{while (p>rtag==) p=p>rchild;
if (p>rchild) return(p>rchild);else return(null); }//指定結點的前序後繼
[算法討論]請注意題目中序序列第一結點的左標志和最後結點的右標志皆為０（非線索）對應指針皆為空的說明若無這一說明只要結點的左標記為其左子女就是其前序後繼最後當p無子女沿右線索向上找其前序後繼時若最後結點的右標志為０但對應指針為空p也無前序後繼
[題目分析] 不借助輔助堆棧實現中序遍歷必須解決如何查找後繼的問題使用線索樹就行為此將結點結構修改為(ltaglchilddatarchildrtag)各字段的含義在上面已多次使用不再介紹設二叉樹已中序線索化下面首先編寫一查中序後繼的函數接著是中序遍歷的非遞歸算法
BiTree After(BiThrTree t) //查中序線索二叉樹上結點t的後繼
{if (t>rtag==) return(t>rchild);
p=t>rchild;
while(p>ltag==) p=p>lchild; //p右子樹中最左下的結點是p的中序後繼
return(p); } //if
void InOrder(BiThrTree bt)
//非遞歸中序遍歷帶頭結點的中序線索二叉樹bt
{p=bt>lchild; //p指向原二叉樹的根結點
if (p!=bt) //二叉樹非空
{while (p>ltag==) p=p>lchild; //找中序遍歷的第一個結點
while (p!=bt) //沒回到頭結點就一直找後繼並遍歷
{visit(*p); p=After(p); }
}//if }結束算法InOrder
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23698.html
