[[396654]]

本文轉(zhuǎn)載自微信公眾號「二十二畫程序員」，作者行小觀。轉(zhuǎn)載本文請聯(lián)系二十二畫程序員公眾號。  

 1. 為什么要用到線索二叉樹?

我們先來看看普通的二叉樹有什么缺點。下面是一個普通二叉樹(鏈式存儲方式)：

一顆普通二叉樹

乍一看，會不會有一種違和感?整個結(jié)構(gòu)一共有 7 個結(jié)點，總共 14 個指針域，其中卻有 8 個指針域都是空的。對于一顆有 n 個結(jié)點的二叉樹而言，總共會有 n+1 個空指針域，這個規(guī)律使用所有的二叉樹。

這么多的空指針域是不是顯得很浪費?我們學習數(shù)據(jù)結(jié)構(gòu)和算法的重點就是在想法設法地提高時間效率和空間利用率。這么多的指針域就這么白白浪費了，太敗家了!

所以我們要想法子好好利用它們，利用它們來幫助我們更好地使用二叉樹這個數(shù)據(jù)結(jié)構(gòu)。

那么如何利用呢?

前面已經(jīng)強調(diào)過很多次了，遍歷二叉樹的實質(zhì)是將二叉樹中非線性結(jié)構(gòu)的結(jié)點轉(zhuǎn)化為線性的序列，然后才能方便我們遍歷。

比如上圖的中序遍歷序列為：DBGEACF。

對于一個線性序列(線性表)來說，它有直接前驅(qū)和直接后繼的概念(在【什么是線性表?】中介紹過)。比如在中序遍歷序列中，B 的直接前驅(qū)為 D，直接后繼為 G。

我們之所以能知道 B 的直接前驅(qū)和直接后繼，是因為我們按照中序遍歷的算法，把二叉樹的中序遍歷序列寫出來了，然后根據(jù)這個順序序列說誰的前驅(qū)是誰、后繼是誰。

直接前驅(qū)和直接后繼是不能完全直接通過二叉樹得到的，因為二叉樹中只有雙親和孩子結(jié)點之間的直接關(guān)系，即二叉樹的結(jié)點指針域中只存儲了其孩子結(jié)點的地址。

現(xiàn)在的需求是，我想能直接從二叉樹上得到某結(jié)點在中序遍歷方式下的直接前驅(qū)和直接后繼。

這時候就需要用到線索二叉樹了。

2. 什么是線索二叉樹?

當然，我們肯定需要借助結(jié)點的指針域來保存直接前驅(qū)和直接后繼的地址。

其實，在上圖的普通二叉樹中(以中序遍歷得到的序列)，部分結(jié)點(指針域不為空的結(jié)點)是可以找到其直接前驅(qū)或后繼的，比如結(jié)點 E 的左孩子 G 就是結(jié)點 E 的直接前驅(qū);結(jié)點 A 的右孩子 C 就是結(jié)點 A 的直接后繼。

但部分結(jié)點(指針域為空)是行不通的，比如結(jié)點 G 的直接后繼是 E，直接前驅(qū)是 B，但在二叉樹中卻不能得出這樣的結(jié)論。怎么辦呢?我們注意到，結(jié)點 G 的兩個指針域都為 NULL，并未被利用，那么我們使用這兩個指針，分別指向其前驅(qū)和后繼不就好了嗎?

中序遍歷下結(jié)點G的指向情況

實在是兩全其美，天作之合!但是問題并沒有解決!

因為我們是利用空指針域來指向前驅(qū)或后繼的，對于那些指針域不為空的結(jié)點，這樣是矛盾的，比如結(jié)點 E 和結(jié)點 B。

既然有矛盾，那么我們就發(fā)現(xiàn)產(chǎn)生矛盾的根源，解決矛盾。

產(chǎn)生矛盾的根源是：結(jié)點的指針域為空和不為空時，指針的指向矛盾。即，指針不為空時指向孩子和指針為空時指向前驅(qū)或后繼之間的矛盾。

那么我們對癥下藥，把指針域為空和不為空給區(qū)分出來，清晰地告訴指針：不為空時指向孩子，為空時指向前驅(qū)或后繼。這就需要我們給兩個指針各添加一個標志位。

線索二叉樹的結(jié)點

并約定以下規(guī)則：

• left_flag == 0 時，指針 left_child 指向左孩子
• left_flag == 1 時，指針 left_child 指向直接前驅(qū)
• right_flag == 0 時，指針 right_child 指向右孩子
• right_flag == 1 時，指針 right_child 指向直接前驅(qū)

二叉樹的結(jié)點要有所變化：

/*線索二叉樹的結(jié)點的結(jié)構(gòu)體*/ 
typedef struct Node { 
    char data; //數(shù)據(jù)域 
    struct Node *left_child; //左指針域 
    int left_flag; //左指針標志位 
    struct Node *right_child; //右指針域 
    int right_flag; //右指針標志位 
} TTreeNode; 

有了標志位，一切就能理清了。我們稱指向直接前驅(qū)和后繼的指針為線索。標志位為 0 的指針是指向孩子的指針，標志位為 1 的指針是線索。

一個二叉鏈表樹，結(jié)點結(jié)構(gòu)如上，我們將所有空指針都變?yōu)榫€索，這樣的二叉樹就是二叉線索樹。

3. 如何創(chuàng)造線索二叉樹?

在普通二叉樹中，我們想要獲取某個結(jié)點在某種遍歷次序下的直接前驅(qū)或后繼，每次都需要遍歷獲取到遍歷次序之后才能知道。而在線索二叉樹中，我們只需要遍歷一次(創(chuàng)造線索二叉樹時的遍歷)，之后，線索二叉樹就能“記住”每個結(jié)點的直接前驅(qū)和后繼了，以后都不需要再通過遍歷次序獲取前驅(qū)或后繼了。

我們按照某種遍歷方式，把普通二叉樹變?yōu)榫€索二叉樹的過程被稱為二叉樹的線索化。

接下來，我們用中序遍歷的方式，將下面的二叉樹線索化為線索二叉樹

將標志位為 1 的指針，按照中序遍歷序列，使其指向前驅(qū)或后繼：

其中，結(jié)點 D 沒有直接前驅(qū)，結(jié)點 F 沒有直接后繼，故指針為 NULL。

到此，我們算是解決了擁有 n 個結(jié)點的二叉樹存在 n+1 個空指針域所造成的浪費，解決方式是給每個結(jié)點的指針增加一個標志位，以此來利用空指針域。標志位中存儲的是 0 或 1 的布爾值，與浪費的空指針域相比，是相對比較劃算的。而且使二叉樹具有了一種新特性——二叉樹中能保存在某種遍歷次序下的結(jié)點之間的前驅(qū)和后繼關(guān)系。

4. 線索化的實現(xiàn)

請注意一點，線索二叉樹是由普通二叉樹得來的，而且是按某種遍歷順序得來的。因為線索是在知道某個結(jié)點的前驅(qū)和后繼的情況下才能設置，而前驅(qū)和后繼關(guān)系不能通過二叉樹直接體現(xiàn)，只能通過遍歷二叉樹得到的線性序列得出關(guān)系。所以要通過某種遍歷方式得到具有前驅(qū)和后繼關(guān)系的序列后，才能修改結(jié)點的空指針，進而設置線索。

即：線索化的實質(zhì)是在按照某種遍歷次序進行遍歷二叉樹的過程中修改結(jié)點的空指針，使其指向其在該遍歷次序下的直接前驅(qū)或直接后繼的過程。

我們在【二叉樹的遍歷原理】和【二叉樹的遍歷實現(xiàn)】分別介紹了二叉樹四種遍歷方式的原理及代碼實現(xiàn)。當時我們是以打印為例來介紹遍歷的。但遍歷不止做打印的事，還可以做線索化的事。

所以，代碼的大體結(jié)構(gòu)還是一樣的，我們只需把遍歷代碼中的打印代碼換成線索化的代碼，并作出一些其他改變即可。

下面以下圖為例，分別介紹三種線索化：

一顆未線索化的二叉樹，其所有標志位均默認為 0.

示例

4.1. 中序線索化

按照中序遍歷次序線索化后，可得下圖：

我們先再次明確以下內(nèi)容：

• 我們是在遍歷二叉樹的過程中進行線索化的。
• 中序遍歷的順序為：左子樹 >> 根 >> 右子樹。
• 線索化修改兩個東西：空指針域和其對應的標志位。
• 如何修改?將空指針域置為直接前驅(qū)或后繼。

所以我們的問題變成了：

1. 找到所有空指針域。
2. 找到空指針域所屬結(jié)點，在先序次序下的直接前驅(qū)和直接后繼。
3. 修改空指針域的內(nèi)容，及其標志位，使該指針稱為線索。

說明：我們在遍歷二叉樹時，使用到了遞歸，所以在進行線索化的時候，也會使用它。

具體代碼如下：

//全局變量 prev 指針，指向剛訪問過的結(jié)點 
TTreeNode *prev = NULL; 
 
/** 
 * 中序線索化 
 */ 
void inorder_threading(TTreeNode *root) 
{ 
    if (root == NULL) { //若二叉樹為空，做空操作 
        return; 
    } 
    inorder_threading(root->left_child); 
    if (root->left_child == NULL) { 
        root->left_flag = 1; 
        root->left_child = prev; 
    } 
    if (prev != NULL && prev->right_child == NULL) { 
        prev->right_flag = 1; 
        prev->right_child = root; 
    } 
    prev = root; 
    inorder_threading(root->right_child); 
} 

4.2. 先序線索化

按照先序順序線索化后，可得下圖：

具體代碼如下：

// 全局變量 prev 指針，指向剛訪問過的結(jié)點 
TTreeNode *prev = NULL; 
 
/** 
 * 先序線索化 
 */ 
void preorder_threading(TTreeNode *root) 
{ 
    if (root == NULL) { 
        return; 
    } 
    if (root->left_child == NULL) { 
        root->left_flag = 1; 
        root->left_child = prev; 
    } 
    if (prev != NULL && prev->right_child == NULL) { 
        prev->right_flag = 1; 
        prev->right_child = root; 
    } 
    prev = root; 
    if (root->left_flag == 0) { 
        preorder_threading(root->left_child); 
    } 
    if (root->right_flag == 0) { 
        preorder_threading(root->right_child); 
    } 
} 

4.3. 后序線索化

按照后序遍歷次序線索化后，可得下圖：

具體代碼如下：

//全局變量 prev 指針，指向剛訪問過的結(jié)點 
TTreeNode *prev = NULL; 
 
/** 
 * 后序線索化 
 */ 
void postorder_threading(TTreeNode *root) 
{ 
    if (root == NULL) { 
        return; 
    } 
    postorder_threading(root->left_child); 
    postorder_threading(root->right_child); 
    if (root->left_child == NULL) { 
        root->left_flag = 1; 
        root->left_child = prev; 
    } 
    if (prev != NULL && prev->right_child == NULL) { 
        prev->right_flag = 1; 
        prev->right_child = root; 
    } 
    prev = root; 
} 

5. 總結(jié)

線索二叉樹充分利用了二叉樹中的空指針域，給予二叉樹一個新特性——通過一次遍歷進行線索化后，二叉樹中就能保存其結(jié)點之間的前驅(qū)和后繼關(guān)系。

所以，如果我們需要頻繁遍歷二叉樹，查找某個結(jié)點的直接前驅(qū)或后繼結(jié)點，使用線索二叉樹是非常合適的。

此外，由于代碼涉及到遞歸，初次接觸可能不好理解，我們可以借助斷點進行調(diào)試，細致觀察線索化的整個過程來幫助理解。