1 前言
在上一篇簡(jiǎn)單二叉樹的學(xué)習(xí)中爽彤，初步介紹了二叉樹的一些基礎(chǔ)知識(shí)昵济，本篇文章將重點(diǎn)介紹二叉樹的一種變形——線索二叉樹蕊连。
2 線索二叉樹
2.1 產(chǎn)生背景
現(xiàn)有一棵結(jié)點(diǎn)數(shù)目為n的二叉樹森缠，采用二叉鏈表的形式存儲(chǔ)深滚。對(duì)于每個(gè)結(jié)點(diǎn)均有指向左右孩子的兩個(gè)指針域奕谭，而結(jié)點(diǎn)為n的二叉樹一共有n-1條有效分支路徑涣觉。那么，則二叉鏈表中存在2n-(n-1)=n+1個(gè)空指針域血柳。那么官册，這些空指針造成了空間浪費(fèi)。
例如：圖2.1所示一棵二叉樹一共有10個(gè)結(jié)點(diǎn)难捌，空指針^有11個(gè)膝宁。
此外，當(dāng)對(duì)二叉樹進(jìn)行中序遍歷時(shí)可以得到二叉樹的中序序列根吁。例如：圖2.1所示二叉樹的中序遍歷結(jié)果為HDIBJEAFCG员淫，可以得知A的前驅(qū)結(jié)點(diǎn)為E，后繼結(jié)點(diǎn)為F婴栽。但是满粗，這種關(guān)系的獲得是建立在完成遍歷后得到的，那么可不可以在建立二叉樹時(shí)就記錄下前驅(qū)后繼的關(guān)系呢愚争，那么在后續(xù)尋找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)時(shí)將大大提升效率映皆。
2.2 線索化
現(xiàn)將某結(jié)點(diǎn)的空指針域指向該結(jié)點(diǎn)的前驅(qū)后繼，定義規(guī)則如下：
若結(jié)點(diǎn)的左子樹為空轰枝，則該結(jié)點(diǎn)的左孩子指針指向其前驅(qū)結(jié)點(diǎn)捅彻。
若結(jié)點(diǎn)的右子樹為空，則該結(jié)點(diǎn)的右孩子指針指向其后繼結(jié)點(diǎn)鞍陨。
這種指向前驅(qū)和后繼的指針稱為線索步淹。將一棵普通二叉樹以某種次序遍歷，并添加線索的過程稱為線索化诚撵。
按照規(guī)則將圖2.1所示二叉樹線索化后如圖2.2所示：
圖中黑色點(diǎn)畫線為指向后繼的線索缭裆，紫色虛線為指向前驅(qū)的線索。
可以看出通過線索化寿烟，既解決了空間浪費(fèi)問題澈驼，又解決了前驅(qū)后繼的記錄問題。
2.3 線索化帶來新問題
經(jīng)過2.2節(jié)講解后筛武，可以將一棵二叉樹線索化為一棵線索二叉樹缝其，那么新的問題產(chǎn)生了。我們?nèi)绾螀^(qū)分一個(gè)結(jié)點(diǎn)的lchild指針是指向左孩子還是前驅(qū)結(jié)點(diǎn)呢徘六？例如：對(duì)于圖2.2所示的結(jié)點(diǎn)E内边，如何區(qū)分其lchild的指向的結(jié)點(diǎn)J是其左孩子還是前驅(qū)結(jié)點(diǎn)呢？
為了解決這一問題待锈，現(xiàn)需要添加標(biāo)志位ltag漠其，rtag。并定義規(guī)則如下：
ltag為0時(shí)，指向左孩子辉懒，為1時(shí)指向前驅(qū)
rtag為0時(shí)阳惹，指向右孩子，為1時(shí)指向后繼
添加ltag和rtag屬性后的結(jié)點(diǎn)結(jié)構(gòu)如下：
圖2.2所示線索二叉樹轉(zhuǎn)變?yōu)閳D2.3所示的二叉樹眶俩。
2.4 線索二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
//#define Link 0//指針標(biāo)志
//#define Thread 1//線索標(biāo)志
typedef char TElemType;
//中序線索二叉樹
typedef enum PointerTag {Link, Thread};//結(jié)點(diǎn)的child域類型莹汤，link表示是指針，指向孩子結(jié)點(diǎn)颠印，thread表示是線索纲岭，指示前驅(qū)或后繼結(jié)點(diǎn)
//定義結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
typedef struct ThrBiNode{
TElemType data;
ThrBiNode *lchild, *rchild;//左右孩子指針
PointerTag lTag, rTag;//左右標(biāo)志
}ThrBiNode, *ThrBiTree;
2.5 中序遍歷建立線索二叉樹
中序遍歷的方法已經(jīng)在第一篇二叉樹基礎(chǔ)中講解過，那么實(shí)現(xiàn)線索化的過程就是在中序遍歷同時(shí)修改結(jié)點(diǎn)空指針的指向线罕。
采用中序遍歷的訪問順序?qū)崿F(xiàn)一棵二叉樹的線索化過程代碼如下：
//中序遍歷進(jìn)行中序線索化
void inThreading(ThrBiTree T, ThrBiTree &pre){
if(T){
inThreading(T->lchild, pre);//左子樹線索化
if(!T->lchild){//當(dāng)前結(jié)點(diǎn)的左孩子為空
T->lTag = Thread;
T->lchild = pre;
}else{
T->lTag = Link;
}
if(!pre->rchild){//前驅(qū)結(jié)點(diǎn)的右孩子為空
pre->rTag = Thread;
pre->rchild = T;
}else{
pre->rTag = Link;
}
pre = T;
inThreading(T->rchild, pre);//右子樹線索化
}
}
2.6 加上頭結(jié)點(diǎn)止潮，遍歷線索二叉樹
加上線索的二叉樹結(jié)構(gòu)是一個(gè)雙向鏈表結(jié)構(gòu)，為了便于遍歷線索二叉樹钞楼，我們?yōu)槠涮砑右粋€(gè)頭結(jié)點(diǎn)喇闸，頭結(jié)點(diǎn)左孩子指向原二叉樹的根結(jié)點(diǎn)，右孩子指針指向中序遍歷的最后一個(gè)結(jié)點(diǎn)询件。同時(shí)燃乍，將第一個(gè)結(jié)點(diǎn)左孩子指針指向頭結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右孩子指針指向頭結(jié)點(diǎn)宛琅。
圖2.3所示線索二叉樹添加頭結(jié)點(diǎn)后如圖2.4所示：
帶有頭結(jié)點(diǎn)的線索二叉樹遍歷代碼如下：
//T指向頭結(jié)點(diǎn)刻蟹，頭結(jié)點(diǎn)的lchild鏈域指針指向二叉樹的根結(jié)點(diǎn)
//中序遍歷打印二叉線索樹T（非遞歸算法）
void inOrderTraversePrint(ThrBiTree T){
ThrBiNode *p = T->lchild;//p指向根結(jié)點(diǎn)
while(p != T){//空樹或遍歷結(jié)束時(shí)，p == T
while(p->lTag == Link){
p = p->lchild;
}
//此時(shí)p指向中序遍歷序列的第一個(gè)結(jié)點(diǎn)（最左下的結(jié)點(diǎn)）
printf("%c ", p->data);//打雍俦佟（訪問）其左子樹為空的結(jié)點(diǎn)
while(p->rTag == Thread && p->rchild != T){
p = p->rchild;
printf("%c ", p->data);//訪問后繼結(jié)點(diǎn)
}
//當(dāng)p所指結(jié)點(diǎn)的rchild指向的是孩子結(jié)點(diǎn)而不是線索時(shí)舆瘪，p的后繼應(yīng)該是其右子樹的最左下的結(jié)點(diǎn)，即遍歷其右子樹時(shí)訪問的第一個(gè)節(jié)點(diǎn)
p = p->rchild;
}
printf("\n");
}
3 結(jié)語
線索二叉樹充分利用了指針空間红伦，同時(shí)又便于尋找結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)英古。線索二叉樹適用于經(jīng)常需要遍歷尋找結(jié)點(diǎn)前驅(qū)或者后繼結(jié)點(diǎn)的二叉樹。
