線索二叉樹(shù)的原理及創(chuàng)建是怎樣的，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

富寧網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站設(shè)計(jì)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站成立于2013年到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

 1. 為什么要用到線索二叉樹(shù)?

我們先來(lái)看看普通的二叉樹(shù)有什么缺點(diǎn)。下面是一個(gè)普通二叉樹(shù)(鏈?zhǔn)酱鎯?chǔ)方式)：

一顆普通二叉樹(shù)

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

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

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

那么如何利用呢?

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

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

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

我們之所以能知道 B  的直接前驅(qū)和直接后繼，是因?yàn)槲覀儼凑罩行虮闅v的算法，把二叉樹(shù)的中序遍歷序列寫出來(lái)了，然后根據(jù)這個(gè)順序序列說(shuō)誰(shuí)的前驅(qū)是誰(shuí)、后繼是誰(shuí)。

直接前驅(qū)和直接后繼是不能完全直接通過(guò)二叉樹(shù)得到的，因?yàn)槎鏄?shù)中只有雙親和孩子結(jié)點(diǎn)之間的直接關(guān)系，即二叉樹(shù)的結(jié)點(diǎn)指針域中只存儲(chǔ)了其孩子結(jié)點(diǎn)的地址。

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

這時(shí)候就需要用到線索二叉樹(shù)了。

2. 什么是線索二叉樹(shù)?

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

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

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

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

實(shí)在是兩全其美，天作之合!但是問(wèn)題并沒(méi)有解決!

因?yàn)槲覀兪抢每罩羔樣騺?lái)指向前驅(qū)或后繼的，對(duì)于那些指針域不為空的結(jié)點(diǎn)，這樣是矛盾的，比如結(jié)點(diǎn) E 和結(jié)點(diǎn) B。

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

產(chǎn)生矛盾的根源是：結(jié)點(diǎn)的指針域?yàn)榭蘸筒粸榭諘r(shí)，指針的指向矛盾。即，指針不為空時(shí)指向孩子和指針為空時(shí)指向前驅(qū)或后繼之間的矛盾。

那么我們對(duì)癥下藥，把指針域?yàn)榭蘸筒粸榭战o區(qū)分出來(lái)，清晰地告訴指針：不為空時(shí)指向孩子，為空時(shí)指向前驅(qū)或后繼。這就需要我們給兩個(gè)指針各添加一個(gè)標(biāo)志位。

線索二叉樹(shù)的結(jié)點(diǎn)

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

• left_flag == 0 時(shí)，指針 left_child 指向左孩子

• left_flag == 1 時(shí)，指針 left_child 指向直接前驅(qū)

• right_flag == 0 時(shí)，指針 right_child 指向右孩子

• right_flag == 1 時(shí)，指針 right_child 指向直接前驅(qū)

二叉樹(shù)的結(jié)點(diǎn)要有所變化：

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

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

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

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

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

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

接下來(lái)，我們用中序遍歷的方式，將下面的二叉樹(shù)線索化為線索二叉樹(shù)

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

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

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

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

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

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

我們?cè)凇径鏄?shù)的遍歷原理】和【二叉樹(shù)的遍歷實(shí)現(xiàn)】分別介紹了二叉樹(shù)四種遍歷方式的原理及代碼實(shí)現(xiàn)。當(dāng)時(shí)我們是以打印為例來(lái)介紹遍歷的。但遍歷不止做打印的事，還可以做線索化的事。

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

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

一顆未線索化的二叉樹(shù)，其所有標(biāo)志位均默認(rèn)為 0.

示例

4.1. 中序線索化

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

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

• 我們是在遍歷二叉樹(shù)的過(guò)程中進(jìn)行線索化的。

• 中序遍歷的順序?yàn)椋鹤笞訕?shù) >> 根 >> 右子樹(shù)。

• 線索化修改兩個(gè)東西：空指針域和其對(duì)應(yīng)的標(biāo)志位。

• 如何修改?將空指針域置為直接前驅(qū)或后繼。

所以我們的問(wèn)題變成了：

1. 找到所有空指針域。

2. 找到空指針域所屬結(jié)點(diǎn)，在先序次序下的直接前驅(qū)和直接后繼。

3. 修改空指針域的內(nèi)容，及其標(biāo)志位，使該指針?lè)Q為線索。

說(shuō)明：我們?cè)诒闅v二叉樹(shù)時(shí)，使用到了遞歸，所以在進(jìn)行線索化的時(shí)候，也會(huì)使用它。

具體代碼如下：

//全局變量 prev 指針，指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) TTreeNode *prev = NULL;  /**  * 中序線索化  */ void inorder_threading(TTreeNode *root) {     if (root == NULL) { //若二叉樹(shù)為空，做空操作         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 指針，指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) 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 指針，指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) 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; }

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

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

關(guān)于線索二叉樹(shù)的原理及創(chuàng)建是怎樣的問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。