線索二叉樹
產(chǎn)生背景
現(xiàn)有一棵結(jié)點數(shù)目為n的二叉樹，采用二叉鏈表的形式存儲。對于每個結(jié)點均有指向左右孩子的兩個指針域，而結(jié)點為n的二叉樹一共有n-1條有效分支路徑。那么，則二叉鏈表中存在2n-(n-1)=n+1個空指針域。那么，這些空指針造成了空間浪費。
例如：下圖所示一棵二叉樹一共有10個結(jié)點，空指針^有11個。
此外，當對二叉樹進行中序遍歷時可以得到二叉樹的中序序列。如上圖所示二叉樹的中序遍歷結(jié)果為HDIBJEAFCG，可以得知A的前驅(qū)結(jié)點為E，后繼結(jié)點為F。但是，這種關(guān)系的獲得是建立在完成遍歷后得到的，那么可不可以在建立二叉樹時就記錄下前驅(qū)后繼的關(guān)系呢，那么在后續(xù)尋找前驅(qū)結(jié)點和后繼結(jié)點時將大大提升效率。
線索化
現(xiàn)將某結(jié)點的空指針域指向該結(jié)點的前驅(qū)后繼，定義規(guī)則如下：
若結(jié)點的左子樹為空，則該結(jié)點的左孩子指針指向其前驅(qū)結(jié)點。
若結(jié)點的右子樹為空，則該結(jié)點的右孩子指針指向其后繼結(jié)點。
這種指向前驅(qū)和后繼的指針稱為線索。將一棵普通二叉樹以某種次序遍歷，并添加線索的過程稱為線索化。
按照規(guī)則將上圖所示二叉樹線索化后所示：
圖中黑色點畫線為指向后繼的線索，紫色虛線為指向前驅(qū)的線索。
可以看出通過線索化，既解決了空間浪費問題，又解決了前驅(qū)后繼的記錄問題。
線索化的新問題
可以將一棵二叉樹線索化為一棵線索二叉樹，那么新的問題產(chǎn)生了。我們?nèi)绾螀^(qū)分一個結(jié)點的lchild指針是指向左孩子還是前驅(qū)結(jié)點呢？例如：對于上圖所示的結(jié)點E，如何區(qū)分其lchild的指向的結(jié)點J是其左孩子還是前驅(qū)結(jié)點呢？
為了解決這一問題，現(xiàn)需要添加標志位ltag，rtag。并定義規(guī)則如下：
ltag為0時，指向左孩子，為1時指向前驅(qū)
rtag為0時，指向右孩子，為1時指向后繼
添加ltag和rtag屬性后的結(jié)點結(jié)構(gòu)如下：
上圖所示線索二叉樹轉(zhuǎn)變?yōu)樾陆Y(jié)構(gòu)后所示的二叉樹：
線索二叉樹結(jié)點數(shù)據(jù)結(jié)構(gòu)
enum PointerTag{
Link, Thread
}
public class BiTNode{
public Object data;
//左右孩子節(jié)點
public BiTNode lChild,rChild;
//左右標志
PointerTag lTag, rTag;
}
中序遍歷建立線索二叉樹
中序遍歷的方法已經(jīng)在上一講二叉樹中講解過，那么實現(xiàn)線索化的過程就是在中序遍歷同時修改結(jié)點空指針的指向。
采用中序遍歷的訪問順序?qū)崿F(xiàn)一棵二叉樹的線索化過程代碼如下：
//中序遍歷進行中序線索化
void inThreading(BiTNode t, BiTNode pre){
if(t!=null){
inThreading(t.lChild, pre);//左子樹線索化
if(t.lChild==null){//當前結(jié)點的左孩子為空
t.lTag = PointerTag.Thread;
t.lChild = pre;
}else{
t.lTag = PointerTag.Link;
}
if(pre.rChild==null){//前驅(qū)結(jié)點的右孩子為空
pre.rTag = PointerTag.Thread;
pre.rChild = t;
}else{
pre.rTag = PointerTag.Link;
}
pre = t;
inThreading(t.rChild, pre);//右子樹線索化
}
}
遍歷線索二叉樹
加上線索的二叉樹結(jié)構(gòu)是一個雙向鏈表結(jié)構(gòu)，為了便于遍歷線索二叉樹，我們?yōu)槠涮砑右粋€頭結(jié)點，頭結(jié)點左孩子指向原二叉樹的根結(jié)點，右孩子指針指向中序遍歷的最后一個結(jié)點。同時，將第一個結(jié)點左孩子指針指向頭結(jié)點，最后一個結(jié)點的右孩子指針指向頭結(jié)點。
帶有頭結(jié)點的線索二叉樹遍歷代碼如下：
//t指向頭結(jié)點，頭結(jié)點的lChild鏈域指針指向二叉樹的根結(jié)點
//中序遍歷打印二叉線索樹T（非遞歸算法）
void inOrderTraversePrint(BiTNode t){
BiTNode p = t.lChild;//p指向根結(jié)點
while(p != t){//空樹或遍歷結(jié)束時，p == t
while(p.lTag == PointerTag.Link){
p = p.lChild;
}
//此時p指向中序遍歷序列的第一個結(jié)點（最左下的結(jié)點）
System.out.println(p.data);//打?。ㄔL問）其左子樹為空的結(jié)點
while(p.rTag == PointerTag.Thread && p.rChild != t){
p = p.rChild;
System.out.println(p.data);//訪問后繼結(jié)點
}
//當p所指結(jié)點的rChild指向的是孩子結(jié)點而不是線索時，p的后繼應該是其右子樹的最左下的結(jié)點，即遍歷其右子樹時訪問的第一個節(jié)點
p = p.rChild;
}
}
線索二叉樹充分利用了指針空間，同時又便于尋找結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點。線索二叉樹適用于經(jīng)常需要遍歷尋找結(jié)點前驅(qū)或者后繼結(jié)點的二叉樹。
