目錄：
1.線索二叉樹的由來
2.線索二叉樹的概念和結(jié)構(gòu)
3.二叉樹的線索化
4.中序線索二叉樹的代碼實現(xiàn)
5.遍歷線索二叉樹

1.線索二叉樹的由來

我問表弟下面的一個問題：

在n個結(jié)點一個二叉鏈表中，有多少個空指針域？

表弟一臉蒙蔽，于是我解釋道：既然有n個結(jié)點，那么總共應(yīng)該有2n個指針域，我們的根結(jié)點是無結(jié)點指向的，其他的結(jié)點肯定都有一個結(jié)點指向，也就是說一共用了n-1個指針域(根結(jié)點無結(jié)點指向所以需要減1)，那么也就是說還有n+1個指針域沒有使用，由此我們可以得出一個結(jié)論:

任何一顆含n個結(jié)點的二叉樹都有n+1個指針域是空指針域

那么這么多的空指針域造成浪費(fèi) ，表弟你心疼不，表弟：管我屁事
我：

為了解決這些浪費(fèi)的空指針域，我們引進(jìn)線索二叉樹

2.線索二叉樹的概念和結(jié)構(gòu)

2.1線索二叉樹的概念

表弟：你給我講講線索二叉樹唄
我：你以為我和你搞著玩？講就講come on baby

線索二叉樹實際上就是使用這些空指針域來存儲結(jié)點之間前趨和后繼關(guān)系的一種特殊的二叉樹。線索二叉樹中，如果結(jié)點有左子樹，則lchild 指針域指向左孩子，否則lchild 指針域指向該結(jié)點的直接前趨；同樣，如果結(jié)點有右子樹，則rchild 指針域指向右孩子，否則rchild 指針域指向該結(jié)點的直接后繼。

LTag 和RTag 為標(biāo)志域。實際上就是兩個布爾類型的變量：
LTag 值為0 時，表示lchild 指針域指向的是該結(jié)點的左孩子；為1 時，表示指向的是該結(jié)點的直接前趨結(jié)點；
RTag 值為0 時，表示rchild 指針域指向的是該結(jié)點的右孩子；為1 時，表示指向的是該結(jié)點的直接后繼結(jié)點。

2.2線索二叉樹的結(jié)構(gòu)代碼實現(xiàn)

表弟：你這講的花里胡哨的，裸敲個線索二叉樹的結(jié)構(gòu)代碼我看看
我：你這是質(zhì)疑你表哥我的實力啊，上DEVC++

#define TElemType int//定義元素的數(shù)據(jù)類型 typedef struct BiThrNode{//線索二叉樹那穩(wěn)的是鏈?zhǔn)浇Y(jié)構(gòu)TElemType data;struct BiThrNode *lchild,*rchild;int LTag;int Rtag; }BiThrNode,*BiThrTree;

3.二叉樹的線索化

表弟：那到底怎樣建立一個線索二叉樹呢
我：別急啊，聽我慢慢說

將二叉樹轉(zhuǎn)化為線索二叉樹，實質(zhì)上是在遍歷二叉樹的過程中，將二叉鏈表中的空指針改為指向直接前趨或者直接后繼的線索。
??線索化的過程即為在遍歷的過程中修改空指針的過程。在遍歷過程中，如果當(dāng)前結(jié)點沒有左孩子，需要將該結(jié)點的lchild 指針指向遍歷過程中的前一個結(jié)點，所以在遍歷過程中，設(shè)置一個指針（名為pre ），時刻指向當(dāng)前訪問結(jié)點的前一個結(jié)點。

表弟：空指針域里存放這些前驅(qū)和后繼有啥用，僅僅就是為了不浪費(fèi)，但是存放了沒有用的東西和浪費(fèi)不是差不多嗎
我：這個問題問的好，其實存放前驅(qū)和后繼的意義是：

線索二叉樹的建立過程其實就是提高遍歷二叉樹效率的過程

表弟：這話我TM聽不懂，說人話
我：臥槽你個**,多大點說對表哥我說臟話，你這是上天啊

表弟：可不是要上天，你趕緊講講剛那句話啥意思
我：其實你想，我們根據(jù)普通的二叉樹的某一個結(jié)點是不是只能找到它的左孩子和右孩子，我們想要知道某一個結(jié)點的前驅(qū)和后繼，是不是就要重新遍歷整個二叉樹，也就是說我們每一次想要知道某一個結(jié)點的前驅(qū)和后繼，都要遍歷一遍整個二叉樹，但是我們?nèi)绻麆?chuàng)建的是線索二叉樹，那么它的空指針域里就存放它的前驅(qū)和后繼的信息，遍歷起來就特別的方便，就不需要遍歷整棵二叉樹，就大大提高了遍歷的效率。

注意我們以不同的方式遍歷二叉樹它的前驅(qū)和后繼也就不同,所以線索二叉樹又分為前序線索二叉樹，中序線索二叉樹，后續(xù)線索二叉樹

其實我們構(gòu)建一顆線索二叉樹的過程其實就是，等同是把一顆二叉樹變成一個雙向鏈表的過程，這怎么理解呢，下面是一顆二叉樹的模型

我們中序遍歷利用指向右孩子的空指針(指向后繼)

再利用指向左孩子的空指針(指向前驅(qū))

聯(lián)合起來就變成如下圖(是不是類似一個雙向鏈表)

4.詳解中序線索二叉樹

表弟：那怎么用代碼實現(xiàn)遍歷過程中讓一顆二叉樹變成線索二叉樹呢
我：我教你用遍歷中序二叉樹的方法構(gòu)造一個中序線索二叉樹，看下面一段代碼

BiThrTree pre;//所以在遍歷過程中，設(shè)置一個全局變量pre,時刻指向當(dāng)前訪問結(jié)點的前一個結(jié)點。 void InThreading(BiThrTree p)//以p為根的子樹中序線索化 {//如果當(dāng)前結(jié)點存在if (p){//遞歸當(dāng)前結(jié)點的左子樹，進(jìn)行線索化InThreading(p->lchild); //如果當(dāng)前結(jié)點沒有左孩子，左標(biāo)志位設(shè)為1，左指針域指向上一結(jié)點preif (!p->lchild)//p的左孩子為空 {//前驅(qū)線索p->Ltag =1;//左孩子指針指向前驅(qū)p->lchild = pre; }elsep->LTag=0; //如果pre 沒有右孩子，右標(biāo)志位設(shè)為1，右指針域指向當(dāng)前結(jié)點。if (!pre->rchild){//后繼線索pre->Rtag =1;//前驅(qū)右孩子指針指向后繼(當(dāng)前結(jié)點p)pre->rchild =p;}else pre->RTag=0;pre = p; //pre 指向當(dāng)前結(jié)點InThreading(p->rchild); //遞歸右子樹進(jìn)行線索化} }

還有一種情況，那就是帶頭結(jié)點的中序線索二叉樹的構(gòu)建方法，那么什么是帶頭結(jié)點的二叉樹呢
我們還拿這顆二叉樹來說：

把上述二叉樹轉(zhuǎn)變成線索二叉樹后會發(fā)現(xiàn)H結(jié)點無前驅(qū)，G結(jié)點無后繼，這時候引入一個頭結(jié)點

那么我們怎樣線索化帶頭結(jié)點的線索二叉樹呢，看下面這一段代碼

//建立頭指針，使其左指針指向根結(jié)點，右指針指向遍歷的最后一個結(jié)點 void InOrder_Thr(BiThrTree &Thr,BiThrTree T)//中序遍歷二叉樹T，并將其中序線索化，Thr為頭指針指向頭結(jié)點 {Thr=new BiThrNode; //建立一個頭結(jié)點 Thr->LTag=0;//頭結(jié)點有左孩子若樹非空那么左孩子指向根結(jié)點 Thr->RTag=1;//右孩子指針為右索引 Thr->rchild=Thr; //初始化的時候右指針指向自己 if(!T)//如果樹為空那么初始化的時候指針也指向自己 Thr->lchild=Thr;else{Thr->lchild=T;//頭結(jié)點左孩子指向根，pre初始值為頭結(jié)點 InThreading(T);//對以T為根的二叉樹進(jìn)行線索化 pre->rchild=Thr;//中序線索化后pre為遍歷的最后結(jié)點 ，讓最后的結(jié)點的右結(jié)點指向頭結(jié)點 pre->RTag=1;Thr->rchild=pre;//頭結(jié)點的右索引指向pre } }

5.遍歷線索二叉樹

下圖中是一個按照中序遍歷建立的線索二叉樹。其中，實線表示指針，指向的是左孩子或者右孩子。虛線表示線索，指向的是該結(jié)點的直接前趨或者直接后繼。

??使用線索二叉樹時，會經(jīng)常遇到一個問題，如上圖中，結(jié)點8的直接后繼直接通過指針域獲得，為結(jié)點5；而由于結(jié)點5的度為2 ，無法利用指針域指向后繼結(jié)點，整個鏈表斷掉了。當(dāng)在遍歷過程，遇到這種問題是解決的辦法就是：尋找先序、中序、后序遍歷的規(guī)律，找到下一個結(jié)點。

???在先序遍歷過程中，如果結(jié)點因為有右孩子導(dǎo)致無法找到其后繼結(jié)點，如果結(jié)點有左孩子，則后繼結(jié)點是其左孩子；否則，就一定是右孩子。拿上圖舉例，結(jié)點2的后繼結(jié)點是其左孩子結(jié)點4 ，如果結(jié)點4不存在的話，就是結(jié)點5 。
??在中序遍歷過程中，結(jié)點的后繼是遍歷其右子樹時訪問的第一個結(jié)點，也就是右子樹中位于最左下的結(jié)點。例如上圖中結(jié)點5，后繼結(jié)點為結(jié)點11，是其右子樹中位于最左邊的結(jié)點。反之，結(jié)點的前趨是左子樹最后訪問的那個結(jié)點。
??后序遍歷中找后繼結(jié)點需要分為3 種情況：
??1. 如果該結(jié)點是二叉樹的根，后繼結(jié)點為空；
??2. 如果該結(jié)點是父結(jié)點的右孩子（或者是左孩子，但是父結(jié)點沒有右孩子），后繼結(jié)點是父結(jié)點；
??3. 如果該結(jié)點是父結(jié)點的左孩子，且父結(jié)點有右子樹，后繼結(jié)點為父結(jié)點的右子樹在后序遍歷列出的第一個結(jié)點。
??使用后序遍歷建立的線索二叉樹，在真正使用過程中遇到鏈表的斷點時，需要訪問父結(jié)點，所以在初步建立二叉樹時，宜采用三叉鏈表做存儲結(jié)構(gòu)。

表弟：這么多,勸退？
我：我們重點掌握中序的就行，下面我實現(xiàn)一下中序線索二叉樹的遍歷的非遞歸代碼你看看

void InOrderTraverse_Thr(BiThrTree T) {//T為頭指針，頭結(jié)點的左鏈lchild指向根結(jié)點BiThrTree p=T->lchild;//p指向根結(jié)點 while(p!=T)//空樹或者遍歷結(jié)束時p==T {while(p->Ltag==0)p=p->lchild;//沿著左孩子向下 cout<<p->data;//訪問左子樹為空的結(jié)點 while(p->Rtag==1&&p->rchild!=T){p=p->rchild;//沿著右線索訪問后繼結(jié)點 cout<<p->data;}p=p->rchild;//轉(zhuǎn)向p的右子樹 } }

結(jié)合下面圖一起看，下面圖的中序遍歷結(jié)果時4 2 8 5 11 9 12 1 6 3 7

總結(jié)

以上是生活随笔為你收集整理的我这么讲线索二叉树，我三岁大的表弟笑了笑的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。