圖解線索二叉樹與雙向線索二叉樹（附原始碼）
@［TOC］
線索二叉樹的概念
當我們對普通的二叉樹進行遍歷時需要使用棧結構做重複性的操作。線索二叉樹不需要如此，在遍歷的同時，使用二叉樹中空閒的記憶體空間記錄某些結點的前趨和後繼元素的位置（不是全部）。這樣在演算法後期需要遍歷二叉樹時，就可以利用儲存的結點資訊，提高了遍歷的效率。使用這種方法構建的二叉樹，即為“線索二叉樹”。
線索二叉樹的結構
每一棵二叉樹上，很多結點都含有未使用的指向NULL 的指標域。除了度為2 的結點，度為1 的結點，有一個空的指標域；葉子結點兩個指標域都為NULL。
線索二叉樹實際上就是使用這些空指標域來儲存結點之間前趨和後繼關係的一種特殊的二叉樹。線索二叉樹中，如果結點有左子樹，則lchild 指標域指向左孩子，否則lchild 指標域指向該結點的直接前趨；同樣，如果結點有右子樹，則rchild 指標域指向右孩子，否則rchild 指標域指向該結點的直接後繼。
LTag 和RTag 為標誌域。實際上就是兩個布林型別的變數：
LTag 值為0 時，表示lchild 指標域指向的是該結點的左孩子；為1 時，表示指向的是該結點的直接前趨結點；
RTag 值為0 時，表示rchild 指標域指向的是該結點的右孩子；為1 時，表示指向的是該結點的直接後繼結點。
結點結構程式碼實現：
#define TElemType int//宏定義，結點中資料域的型別
//列舉，Link 為0，Thread 為1
typedef enum PointerTag{
Link，
Thread
}PointerTag；
//結點結構構造
typedef struct BiThrNode{
TElemType data；//資料域
struct BiThrNode* lchild，*rchild；//左孩子，右孩子指標域
PointerTag Ltag，Rtag；//標誌域，列舉型別
}BiThrNode，*BiThrTree；
二叉樹的線索化
將二叉樹轉化為線索二叉樹，實質上是在遍歷二叉樹的過程中，將二叉連結串列中的空指標改為指向直接前趨或者直接後繼的線索。
線索化的過程即為在遍歷的過程中修改空指標的過程。在遍歷過程中，如果當前結點沒有左孩子，需要將該結點的lchild 指標指向遍歷過程中的前一個結點，所以在遍歷過程中，設定一個指標（名為pre ），時刻指向當前訪問結點的前一個結點。
程式碼實現（拿中序遍歷為例）：
/**
* @Description： 中序對二叉樹進行線索化
* @Param： BiThrTree p 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InThreading（BiThrTree p）
{
//如果當前結點存在
if （p）
{
//遞迴當前結點的左子樹，進行線索化
InThreading（p->lchild）；
//如果當前結點沒有左孩子，左標誌位設為1，左指標域指向上一結點pre
if （！p->lchild）
{
//前驅線索
p->Ltag = Thread；
//左孩子指標指向前驅
p->lchild = pre；
}
//如果pre 沒有右孩子，右標誌位設為1，右指標域指向當前結點。
if （pre && ！pre->rchild）
{
//後繼線索
pre->Rtag = Thread；
//前驅右孩子指標指向後繼（當前結點p）
pre->rchild = p；
}
pre = p； //pre 指向當前結點
InThreading（p->rchild）； //遞迴右子樹進行線索化
}
}
注意：中序對二叉樹進行線索化的過程中，在兩個遞迴函式中間的執行程式，和之前介紹的中序遍歷二叉樹的輸出函式的作用是相同的。將中間函式移動到兩個遞迴函式之前，就變成了前序對二叉樹進行線索化的過程；後序線索化同樣如此。
線索二叉樹進行遍歷
下圖中是一個按照中序遍歷建立的線索二叉樹。其中，實線表示指標，指向的是左孩子或者右孩子。虛線表示線索，指向的是該結點的直接前趨或者直接後繼。
！［在這裡插入圖片描述］（
https：//
img-blog。csdnimg。cn/202
00601202737420。png？x-oss-process
=image/watermark，type_ZmFuZ3poZW5naGVpdGk，shadow_10，text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2OTMzNjAx，size_16，co
lor_FFFFFF，t_70）
使用線索二叉樹時，會經常遇到一個問題，如上圖中，結點8的直接後繼直接透過指標域獲得，為結點5；而由於結點5的度為2 ，無法利用指標域指向後繼結點，整個
連結串列斷掉了
。當在遍歷過程，遇到這種問題是解決的辦法就是：
尋找先序、中序、後序遍歷的規律
，找到下一個結點。
在先序遍歷過程中，如果結點因為有右孩子導致無法找到其後繼結點，如果結點有左孩子，則後繼結點是其左孩子；否則，就一定是右孩子。拿上圖舉例，結點2的後繼結點是其左孩子結點4 ，如果結點4不存在的話，就是結點5 。
在中序遍歷過程中，結點的後繼是遍歷其右子樹時訪問的第一個結點，也就是右子樹中位於最左下的結點。例如上圖中結點5，後繼結點為結點11，是其右子樹中位於最左邊的結點。反之，結點的前趨是左子樹最後訪問的那個結點。
後序遍歷中找後繼結點需要分為3 種情況：
1。 如果該結點是二叉樹的根，後繼結點為空；
2。 如果該結點是父結點的右孩子（或者是左孩子，但是父結點沒有右孩子），後繼結點是父結點；
3。 如果該結點是父結點的左孩子，且父結點有右子樹，後繼結點為父結點的右子樹在後序遍歷列出的第一個結點。
使用後序遍歷建立的線索二叉樹，在真正使用過程中遇到連結串列的斷點時，需要訪問父結點，所以在初步建立二叉樹時，宜採用三叉連結串列做儲存結構。
遍歷線索二叉樹非遞迴程式碼實現：
/**
* @Description： 中序遍歷線索二叉樹 非遞迴
* @Param： BiThrTree p 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThraverse_Thr（BiThrTree p）
{
while （p）
{
//一直找左孩子，最後一個為中序序列中排第一的
while （p->Ltag == Link）
{
p = p->lchild；
}
//此時p指向中序遍歷序列的第一個結點（最左下的結點）
//列印（訪問）其左子樹為空的結點
printf（“%c ”， p->data）；
//當結點右標誌位為1 時，直接找到其後繼結點
while （p->Rtag == Thread && p->rchild ！= NULL）
{
p = p->rchild；
//訪問後繼結點
printf（“%c ”， p->data）；
}
//當p所指結點的rchild指向的是孩子結點而不是線索時，p的後繼應該是其右子樹的最左下的結點，即遍歷其右子樹時訪問的第一個節點
p = p->rchild；
}
}
完整程式碼如下：
/*
* @Description： 線索二叉樹
* @Version： V1。0
* @Autor： Carlos
* @Date： 2020-05-20 16：31：33
* @LastEditors： Carlos
* @LastEditTime： 2020-06-01 20：19：22
*/
#include
#include
#define TElemType char //宏定義，結點中資料域的型別
//列舉，Link 為0，Thread 為1
typedef enum
{
Link，
Thread
} PointerTag；
//結點結構構造
typedef struct BiThrNode
{
//資料域
TElemType data；
//左孩子，右孩子指標域
struct BiThrNode *lchild， *rchild；
//標誌域，列舉型別
PointerTag Ltag， Rtag；
} BiThrNode， *BiThrTree；
BiThrTree pre = NULL；
/**
* @Description： 初始化二叉樹
* @Param： BiTree *T 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void CreateBiTree（BiThrTree *T）{
*T=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->data=1；
（*T）->lchild=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->rchild=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->lchild->data=2；
（*T）->lchild->lchild=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->lchild->rchild=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->lchild->rchild->data=5；
（*T）->lchild->rchild->lchild=NULL；
（*T）->lchild->rchild->rchild=NULL；
（*T）->rchild->data=3；
（*T）->rchild->lchild=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->rchild->lchild->data=6；
（*T）->rchild->lchild->lchild=NULL；
（*T）->rchild->lchild->rchild=NULL；
（*T）->rchild->rchild=（BiThrNode*）malloc（sizeof（BiThrNode））；
（*T）->rchild->rchild->data=7；
（*T）->rchild->rchild->lchild=NULL；
（*T）->rchild->rchild->rchild=NULL；
（*T）->lchild->lchild->data=4；
（*T）->lchild->lchild->lchild=NULL；
（*T）->lchild->lchild->rchild=NULL；
}
/**
* @Description： 採用前序初始化二叉樹 中序和後序只需改變賦值語句的位置即可
* @Param： BiThrTree *tree 二叉樹的結構體指標陣列
* @Return： 無
* @Author： Carlos
*/
void CreateTree（BiThrTree *tree）
{
char data；
scanf（“%c”， &data）；
if （data ！= ‘#’）
{
if （！（（*tree） = （BiThrNode *）malloc（sizeof（BiThrNode））））
{
printf（“申請結點空間失敗”）；
return；
}
else
{
//採用前序遍歷方式初始化二叉樹
（*tree）->data = data；
//初始化左子樹
CreateTree（&（（*tree）->lchild））；
//初始化右子樹
CreateTree（&（（*tree）->rchild））；
}
}
else
{
*tree = NULL；
}
}
/**
* @Description： 中序對二叉樹進行線索化
* @Param： BiThrTree p 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InThreading（BiThrTree p）
{
//如果當前結點存在
if （p）
{
//遞迴當前結點的左子樹，進行線索化
InThreading（p->lchild）；
//如果當前結點沒有左孩子，左標誌位設為1，左指標域指向上一結點pre
if （！p->lchild）
{
//前驅線索
p->Ltag = Thread；
//左孩子指標指向前驅
p->lchild = pre；
}
//如果pre 沒有右孩子，右標誌位設為1，右指標域指向當前結點。
if （pre && ！pre->rchild）
{
//後繼線索
pre->Rtag = Thread；
//前驅右孩子指標指向後繼（當前結點p）
pre->rchild = p；
}
pre = p； //pre 指向當前結點
InThreading（p->rchild）； //遞迴右子樹進行線索化
}
}
/**
* @Description： 中序遍歷線索二叉樹 非遞迴
* @Param： BiThrTree p 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThraverse_Thr（BiThrTree p）
{
while （p）
{
//一直找左孩子，最後一個為中序序列中排第一的
while （p->Ltag == Link）
{
p = p->lchild；
}
//此時p指向中序遍歷序列的第一個結點（最左下的結點）
//列印（訪問）其左子樹為空的結點
printf（“%c ”， p->data）；
//當結點右標誌位為1 時，直接找到其後繼結點
while （p->Rtag == Thread && p->rchild ！= NULL）
{
p = p->rchild；
//訪問後繼結點
printf（“%c ”， p->data）；
}
//當p所指結點的rchild指向的是孩子結點而不是線索時，p的後繼應該是其右子樹的最左下的結點，即遍歷其右子樹時訪問的第一個節點
p = p->rchild；
}
}
int main（）
{
BiThrTree t；
printf（“輸入前序二叉樹：\n”）；
CreateTree（&t）；
// CreateBiTree（&t）；
InThreading（t）；
printf（“輸出中序序列：\n”）；
InOrderThraverse_Thr（t）；
return 0；
}
雙向線索二叉樹的概念
在遍歷使用中序序列建立的線索二叉樹時，對於其中的每個結點，即使沒有線索的幫助
下，也可以透過中序遍歷的規律找到直接前趨和直接後繼結點的位置。也就是說，建立的線索二叉連結串列可以從兩個方向對結點進行中序遍歷。線索二叉連結串列可以從第一個結點往後逐個遍歷。但是起初由於沒有記錄中序序列中最後一個結點的位置，所以不能實現從最後一個結點往前逐個遍歷。雙向線索連結串列的作用就是可以讓線索二叉樹從兩個方向實現遍歷。
雙向線索二叉樹的實現過程
線上索二叉樹的基礎上，額外新增一個結點。此結點的作用類似於連結串列中的頭指標，資料域不起作用，
只利用兩個指標域
（由於都是指標，標誌域都為0 ）。
左指標域指向二叉樹的樹根
，確保可以正方向對二叉樹進行遍歷；同時，
右指標指向線索二叉樹形成的線性序列中的最後一個結點
。
這樣，二叉樹中的線索連結串列就變成了雙向線索連結串列，既可以從第一個結點透過不斷地找後繼結點進行遍歷，也可以從最後一個結點透過不斷找前趨結點進行遍歷。
程式碼實現
/**
* @Description： 建立雙向線索連結串列
* @Param： BiThrTree *h 結構體指標陣列 BiThrTree t 結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThread_Head（BiThrTree *h， BiThrTree t）
{
//初始化頭結點
（*h） = （BiThrTree）malloc（sizeof（BiThrNode））；
if （（*h） == NULL）
{
printf（“申請記憶體失敗”）；
return；
}
（*h）->rchild = *h；
（*h）->Rtag = Link；
//如果樹本身是空樹
if （！t）
{
（*h）->lchild = *h；
（*h）->Ltag = Link；
}
else
{
//pre 指向頭結點
pre = *h；
//頭結點左孩子設為樹根結點
（*h）->lchild = t；
（*h）->Ltag = Link；
//線索化二叉樹，pre 結點作為全域性變數，線索化結束後，pre 結點指向中序序列中最後一個結點
InThreading（t）；
//連結最後一個節點（最右下角G節點）和頭結點
pre->rchild = *h；
pre->Rtag = Thread；
//將頭結點的右指標指向中序序列最後一個節點
（*h）->rchild = pre；
}
}
雙向線索二叉樹的遍歷
雙向線索二叉樹遍歷時，如果正向遍歷，就從樹的根結點開始。整個遍歷過程結束的標誌是：當從頭結點出發，遍歷回頭結點時，表示遍歷結束。
/**
* @Description： 中序正向遍歷雙向線索二叉樹
* @Param： BiThrTree h 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThraverse_Thr（BiThrTree h）
{
BiThrTree p；
//p 指向根結點
p = h->lchild；
while （p ！= h）
{
//當ltag = 0 時迴圈到中序序列的第一個結點。
while （p->Ltag == Link）
{
p = p->lchild；
}
//顯示結點資料，可以更改為其他對結點的操作
printf（“%c ”， p->data）；
//如果當前節點經過了線索化，直接利用該節點訪問下一節點
while （p->Rtag == Thread && p->rchild ！= h）
{
p = p->rchild；
printf（“%c ”， p->data）；
}
//如果沒有線索化或者跳出迴圈，說明其含有右子樹。p 進入其右子樹
p = p->rchild；
}
}
逆向遍歷線索二叉樹的過程即從頭結點的右指標指向的結點出發，逐個尋找直接前趨結點，結束標誌同正向遍歷一樣：
/**
* @Description： 中序逆方向遍歷線索二叉樹 和正向的區別在於 p = p->rchild 。逆向遍歷我們要一直訪問到右子樹的最後一個。
* @Param： BiThrTree h 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThraverse_Thr（BiThrTree h）
{
BiThrTree p；
p = h->rchild；
while （p ！= h）
{
while （p->Rtag == Link）
{
p = p->rchild；
}
printf（“%c”， p->data）；
//如果lchild 為線索，直接使用，輸出
while （p->Ltag == Thread && p->lchild ！= h）
{
p = p->lchild；
printf（“%c”， p->data）；
}
p = p->lchild；
}
}
完整程式碼如下
/*
* @Description： 雙向線索二叉樹的遍歷
* @Version： V1。0
* @Autor： Carlos
* @Date： 2020-06-01 20：46：38
* @LastEditors： Carlos
* @LastEditTime： 2020-06-01 21：17：23
*/
#include
#include
//宏定義，結點中資料域的型別
#define TElemType char
//列舉，Link 為0，Thread 為1
typedef enum
{
Link，
Thread
} PointerTag；
//結點結構構造
typedef struct BiThrNode
{
//資料域
TElemType data；
//左孩子，右孩子指標域
struct BiThrNode *lchild， *rchild；
//標誌域，列舉型別
PointerTag Ltag， Rtag；
} BiThrNode， *BiThrTree；
BiThrTree pre = NULL；
/**
* @Description： 採用前序初始化二叉樹 中序和後序只需改變賦值語句的位置即可
* @Param： BiThrTree *tree 二叉樹的結構體指標陣列
* @Return： 無
* @Author： Carlos
*/
void CreateTree（BiThrTree *tree）
{
char data；
scanf（“%c”， &data）；
if （data ！= ‘#’）
{
if （！（（*tree） = （BiThrNode *）malloc（sizeof（BiThrNode））））
{
printf（“申請結點空間失敗”）；
return；
}
else
{
//採用前序遍歷方式初始化二叉樹
（*tree）->data = data；
//初始化左子樹
CreateTree（&（（*tree）->lchild））；
//初始化右子樹
CreateTree（&（（*tree）->rchild））；
}
}
else
{
*tree = NULL；
}
}
/**
* @Description： 中序對二叉樹進行線索化
* @Param： BiThrTree p 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InThreading（BiThrTree p）
{
//如果當前結點存在
if （p）
{
//遞迴當前結點的左子樹，進行線索化
InThreading（p->lchild）；
//如果當前結點沒有左孩子，左標誌位設為1，左指標域指向上一結點pre
if （！p->lchild）
{
p->Ltag = Thread；
//pre為頭結點，連結中序遍歷的第一個節點（最左邊的結點）與頭結點
p->lchild = pre；
}
//如果pre 沒有右孩子，右標誌位設為1，右指標域指向當前結點。
if （pre && ！pre->rchild）
{
pre->Rtag = Thread；
pre->rchild = p；
}
//pre 指向當前結點
pre = p；
//遞迴右子樹進行線索化
InThreading（p->rchild）；
}
}
/**
* @Description： 建立雙向線索連結串列
* @Param： BiThrTree *h 結構體指標陣列 BiThrTree t 結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThread_Head（BiThrTree *h， BiThrTree t）
{
//初始化頭結點
（*h） = （BiThrTree）malloc（sizeof（BiThrNode））；
if （（*h） == NULL）
{
printf（“申請記憶體失敗”）；
return；
}
（*h）->rchild = *h；
（*h）->Rtag = Link；
//如果樹本身是空樹
if （！t）
{
（*h）->lchild = *h；
（*h）->Ltag = Link；
}
else
{
//pre 指向頭結點
pre = *h；
//頭結點左孩子設為樹根結點
（*h）->lchild = t；
（*h）->Ltag = Link；
//線索化二叉樹，pre 結點作為全域性變數，線索化結束後，pre 結點指向中序序列中最後一個結點
InThreading（t）；
//連結最後一個節點（最右邊下角）和頭結點
pre->rchild = *h；
pre->Rtag = Thread；
（*h）->rchild = pre；
}
}
/**
* @Description： 中序正向遍歷雙向線索二叉樹
* @Param： BiThrTree h 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThraverse_Thr（BiThrTree h）
{
BiThrTree p；
//p 指向根結點
p = h->lchild；
while （p ！= h）
{
//當ltag = 0 時迴圈到中序序列的第一個結點。
while （p->Ltag == Link）
{
p = p->lchild；
}
//顯示結點資料，可以更改為其他對結點的操作
printf（“%c ”， p->data）；
//如果當前節點經過了線索化，直接利用該節點訪問下一節點
while （p->Rtag == Thread && p->rchild ！= h）
{
p = p->rchild；
printf（“%c ”， p->data）；
}
//如果沒有線索化或者跳出迴圈，說明其含有右子樹。p 進入其右子樹
p = p->rchild；
}
}
/**
* @Description： 中序逆方向遍歷線索二叉樹 和正向的區別在於 p = p->rchild 。逆向遍歷我們要一直訪問到右子樹的最後一個。
* @Param： BiThrTree h 二叉樹的結構體指標
* @Return： 無
* @Author： Carlos
*/
void InOrderThraverse_Thr（BiThrTree h）
{
BiThrTree p；
p = h->rchild；
while （p ！= h）
{
while （p->Rtag == Link）
{
p = p->rchild；
}
printf（“%c”， p->data）；
//如果lchild 為線索，直接使用，輸出
while （p->Ltag == Thread && p->lchild ！= h）
{
p = p->lchild；
printf（“%c”， p->data）；
}
p = p->lchild；
}
}
int main（）
{
BiThrTree t；
BiThrTree h；
printf（“輸入前序二叉樹：\n”）；
CreateTree（&t）；
InOrderThread_Head（&h， t）；
printf（“輸出中序序列：\n”）；
InOrderThraverse_Thr（h）；
return 0；
}
總結
二叉樹的線索化就是充分利用了節點的空指標域。所有節點線索化的過程也就是當前節點指標和上一結點指標進行連結的過程，不斷遞迴所有節點。線索化二叉樹的訪問，以中序遍歷為例，首先需要訪問到中序遍歷的第一個節點，若當前節點進行了線索化，可以直接利用該節點進行下一節點的訪問。否則，說明當前節點含有右子樹，則進入右子樹進行訪問。雙向線索二叉樹的建立，其實就將頭結點的左指標和樹的根節點連結，頭結點的右指標和中序遍歷的最後一個節點的連結。這樣我們就可以進行雙向訪問了。當從頭結點出發，遍歷回頭結點時，表示遍歷結束。
如遇到排版錯亂的問題或者有任何疑問、建議，可以在“我的主頁”找到我的聯絡方式和我的部落格連結。
