自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

【數(shù)據(jù)結(jié)構(gòu)之線索二叉樹(shù)】線索二叉樹(shù)的原理及創(chuàng)建

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

[[396654]]

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

 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ù)的中序遍歷序列寫(xiě)出來(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)要有所變化：

  1. /*線索二叉樹(shù)的結(jié)點(diǎn)的結(jié)構(gòu)體*/ 
  2. typedef struct Node { 
  3.     char data; //數(shù)據(jù)域 
  4.     struct Node *left_child; //左指針域 
  5.     int left_flag; //左指針標(biāo)志位 
  6.     struct Node *right_child; //右指針域 
  7.     int right_flag; //右指針標(biāo)志位 
  8. } 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è)?a >【二叉樹(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ì)使用它。

具體代碼如下：

  1. //全局變量 prev 指針，指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) 
  2. TTreeNode *prev = NULL; 
  3.  
  4. /** 
  5.  * 中序線索化 
  6.  */ 
  7. void inorder_threading(TTreeNode *root) 
  8. { 
  9.     if (root == NULL) { //若二叉樹(shù)為空，做空操作 
  10.         return; 
  11.     } 
  12.     inorder_threading(root->left_child); 
  13.     if (root->left_child == NULL) { 
  14.         root->left_flag = 1; 
  15.         root->left_child = prev; 
  16.     } 
  17.     if (prev != NULL && prev->right_child == NULL) { 
  18.         prev->right_flag = 1; 
  19.         prev->right_child = root; 
  20.     } 
  21.     prev = root; 
  22.     inorder_threading(root->right_child); 
  23. } 

4.2. 先序線索化

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

具體代碼如下：

  1. // 全局變量 prev 指針，指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) 
  2. TTreeNode *prev = NULL; 
  3.  
  4. /** 
  5.  * 先序線索化 
  6.  */ 
  7. void preorder_threading(TTreeNode *root) 
  8. { 
  9.     if (root == NULL) { 
  10.         return; 
  11.     } 
  12.     if (root->left_child == NULL) { 
  13.         root->left_flag = 1; 
  14.         root->left_child = prev; 
  15.     } 
  16.     if (prev != NULL && prev->right_child == NULL) { 
  17.         prev->right_flag = 1; 
  18.         prev->right_child = root; 
  19.     } 
  20.     prev = root; 
  21.     if (root->left_flag == 0) { 
  22.         preorder_threading(root->left_child); 
  23.     } 
  24.     if (root->right_flag == 0) { 
  25.         preorder_threading(root->right_child); 
  26.     } 
  27. } 

4.3. 后序線索化

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

具體代碼如下：

  1. //全局變量 prev 指針，指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) 
  2. TTreeNode *prev = NULL; 
  3.  
  4. /** 
  5.  * 后序線索化 
  6.  */ 
  7. void postorder_threading(TTreeNode *root) 
  8. { 
  9.     if (root == NULL) { 
  10.         return; 
  11.     } 
  12.     postorder_threading(root->left_child); 
  13.     postorder_threading(root->right_child); 
  14.     if (root->left_child == NULL) { 
  15.         root->left_flag = 1; 
  16.         root->left_child = prev; 
  17.     } 
  18.     if (prev != NULL && prev->right_child == NULL) { 
  19.         prev->right_flag = 1; 
  20.         prev->right_child = root; 
  21.     } 
  22.     prev = root; 
  23. } 

5. 總結(jié)

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

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

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

 

責(zé)任編輯：武曉燕 來(lái)源： 二十二畫(huà)程序員
數(shù)據(jù)結(jié)構(gòu)創(chuàng)建
相關(guān)推薦

2021-04-20 08:37:14

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)樹(shù)

2021-04-19 07:47:42

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)Tree

2021-03-22 09:00:22

Java數(shù)據(jù)結(jié)構(gòu)算法

2020-04-27 07:05:58

二叉樹(shù)左子樹(shù)右子樹(shù)

2020-11-02 09:15:47

算法與數(shù)據(jù)結(jié)構(gòu)

2020-09-23 18:25:40

算法二叉樹(shù)多叉樹(shù)

2013-01-30 10:34:02

數(shù)據(jù)結(jié)構(gòu)

2021-03-22 08:23:29

LeetCode二叉樹(shù)節(jié)點(diǎn)

2018-03-15 08:31:57

二叉樹(shù)存儲(chǔ)結(jié)構(gòu)

2021-03-17 08:19:22

二叉樹(shù)LeetCode樹(shù)

2013-07-15 16:35:55

二叉樹(shù)迭代器

2021-09-29 10:19:00

算法平衡二叉樹(shù)

2021-01-07 08:12:47

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)樹(shù)

2022-10-26 23:58:02

二叉樹(shù)數(shù)組算法

2021-08-27 11:36:44

二叉樹(shù)回溯節(jié)點(diǎn)

2021-03-19 10:25:12

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-01 10:34:18

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2021-05-06 17:46:30

二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)

2023-05-08 15:57:16

二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)

2021-09-15 07:56:32

二叉樹(shù)層次遍歷
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)