轉(zhuǎn)載

原文地址：https://blog.csdn.net/UncleMing5371/article/details/54176252

一、線索二叉樹(shù)原理

??????前面介紹二叉樹(shù)原理及特殊二叉樹(shù)文章中提到，二叉樹(shù)可以使用兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)和二叉鏈表。在使用二叉鏈表的存儲(chǔ)結(jié)構(gòu)的過(guò)程中，會(huì)存在大量的空指針域，為了充分利用這些空指針域，引申出了“線索二叉樹(shù)”。回顧一下二叉鏈表存儲(chǔ)結(jié)構(gòu)，如下圖：?

??????通過(guò)觀察上面的二叉鏈表，存在著若干個(gè)沒(méi)有指向的空指針域。對(duì)于一個(gè)有n個(gè)節(jié)點(diǎn)的二叉鏈表，每個(gè)節(jié)點(diǎn)有指向左右節(jié)點(diǎn)的2個(gè)指針域，整個(gè)二叉鏈表存在2n個(gè)指針域。而n個(gè)節(jié)點(diǎn)的二叉鏈表有n-1條分支線，那么空指針域的個(gè)數(shù)=2n-(n-1) = n+1個(gè)空指針域，從存儲(chǔ)空間的角度來(lái)看，這n+1個(gè)空指針域浪費(fèi)了內(nèi)存資源。?
??????從另外一個(gè)角度來(lái)分析，如果我們想知道按中序方式遍歷二叉鏈表時(shí)B節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)或者后繼節(jié)點(diǎn)時(shí)，必須要按中序方式遍歷二叉鏈表才能夠知道結(jié)果，每次需要結(jié)果時(shí)都需要進(jìn)行一次遍歷，是否可以考慮提前存儲(chǔ)這種前驅(qū)和后繼的關(guān)系來(lái)提高時(shí)間效率呢？?
??????綜合以上兩方面的分析，可以通過(guò)充分利用二叉鏈表中的空指針域，存放節(jié)點(diǎn)在某種遍歷方式下的前驅(qū)和后繼節(jié)點(diǎn)的指針。 我們把這種指向前驅(qū)和后繼的指針成為線索，加上線索的二叉鏈表成為線索鏈表，對(duì)應(yīng)的二叉樹(shù)就成為“線索二叉樹(shù)(Threaded Binary Tree)” ?。

---

二、構(gòu)建線索二叉樹(shù)過(guò)程

1、我們對(duì)二叉樹(shù)進(jìn)行中序遍歷（不了解二叉樹(shù)遍歷請(qǐng)參考二叉樹(shù)及特殊二叉樹(shù)介紹），將所有的節(jié)點(diǎn)右子節(jié)點(diǎn)為空的指針域指向它的后繼節(jié)點(diǎn)。如下圖：?

??????通過(guò)中序遍歷我們知道H的right指針為空，并且H的后繼節(jié)點(diǎn)為D（如上圖第1步），I的right指針為空，并且I的后繼節(jié)點(diǎn)為B（如上圖第2步），以此類推，知道G的后繼節(jié)點(diǎn)為null，則G的right指針指向null。

2、接下來(lái)將這顆二叉樹(shù)的所有節(jié)點(diǎn)左指針域?yàn)榭盏闹羔樣蛑赶蛩那膀?qū)節(jié)點(diǎn)。如下圖：?

??????如上圖，H的left指針域指向Null（如第1步），I的前驅(qū)節(jié)點(diǎn)是D，則I的left指針指向D，以此類推。

??????通過(guò)上面兩步完成了整個(gè)二叉樹(shù)的線索化，最后結(jié)果如下圖：?

??????通過(guò)觀察上圖（藍(lán)色虛線代表后繼、綠色虛線代表前驅(qū)），可以看出，線索二叉樹(shù)，等于是把一棵二叉樹(shù)轉(zhuǎn)變成了一個(gè)“ 特殊的雙向鏈表 “(后面會(huì)解釋為什么叫特殊的雙向鏈表），這樣對(duì)于我們的新增、刪除、查找節(jié)點(diǎn)帶來(lái)了方便。所以我們對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程稱做是線索化。如下圖：?

?

??????仔細(xì)分析上面的雙向鏈表，與線索化之后的二叉樹(shù)相比，比如節(jié)點(diǎn)D與后繼節(jié)點(diǎn)I，在完成線索化之后，并沒(méi)有直接線索指針，而是存在父子節(jié)點(diǎn)的指針；節(jié)點(diǎn)A與節(jié)點(diǎn)F，在線索化完成之后，節(jié)點(diǎn)A并沒(méi)有直接指向后繼節(jié)點(diǎn)F的線索指針，而是通過(guò)父子節(jié)點(diǎn)遍歷可以找到最終的節(jié)點(diǎn)F，前驅(qū)節(jié)點(diǎn)也存在同樣的問(wèn)題，正因?yàn)楹芏喙?jié)點(diǎn)之間不存在直接的線索，所以我將此雙向鏈表稱做“ 特殊的雙向鏈表 ”，再使用過(guò)程中根據(jù)指針是線索指針還是子節(jié)點(diǎn)指針來(lái)分別處理，所以在每個(gè)節(jié)點(diǎn)需要標(biāo)明當(dāng)前的左右指針是線索指針還是子節(jié)點(diǎn)指針，這就需要修改節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。修改后的數(shù)據(jù)結(jié)構(gòu)如下：

class Node {String data; //數(shù)據(jù)域Node left; //左指針域Node right; //右指針域byte leftType; //左指針域類型 0：指向子節(jié)點(diǎn)、1：前驅(qū)或后繼線索byte rightType; //右指針域類型 0：指向子節(jié)點(diǎn)、1：前驅(qū)或后繼線索}

• 1
• 2
• 3
• 4
• 5
• 6
• 7

最終的二叉鏈表修改為如下圖的樣子：?

---

三、線索二叉樹(shù)的代碼（Java版）

下面是中序線索化二叉樹(shù)的實(shí)現(xiàn)代碼：

/*** @Title: 二叉樹(shù)相關(guān)操作* @Description：* @Author： Uncle Ming* @Date：2017年1月6日 下午2:49:14* @Version V1.0*/ public class ThreadBinaryTree {private Node preNode; //線索化時(shí)記錄前一個(gè)節(jié)點(diǎn)//節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)static class Node {String data; //數(shù)據(jù)域Node left; //左指針域Node right; //右指針域boolean isLeftThread = false; //左指針域類型 false：指向子節(jié)點(diǎn)、true：前驅(qū)或后繼線索boolean isRightThread = false; //右指針域類型 false：指向子節(jié)點(diǎn)、true：前驅(qū)或后繼線索Node(String data) {this.data = data;}}/*** 通過(guò)數(shù)組構(gòu)造一個(gè)二叉樹(shù)（完全二叉樹(shù)）* @param array* @param index* @return*/static Node createBinaryTree(String[] array, int index) {Node node = null;if(index < array.length) {node = new Node(array[index]);node.left = createBinaryTree(array, index * 2 + 1);node.right = createBinaryTree(array, index * 2 + 2);}return node;}/*** 中序線索化二叉樹(shù)* @param node 節(jié)點(diǎn)*/void inThreadOrder(Node node) {if(node == null) {return;}//處理左子樹(shù)inThreadOrder(node.left);//左指針為空,將左指針指向前驅(qū)節(jié)點(diǎn)if(node.left == null) {node.left = preNode;node.isLeftThread = true;}//前一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)if(preNode != null && preNode.right == null) {preNode.right = node;preNode.isRightThread = true;}preNode = node;//處理右子樹(shù)inThreadOrder(node.right);}/*** 中序遍歷線索二叉樹(shù)，按照后繼方式遍歷（思路：找到最左子節(jié)點(diǎn)開(kāi)始）* @param node*/void inThreadList(Node node) {//1、找中序遍歷方式開(kāi)始的節(jié)點(diǎn)while(node != null && !node.isLeftThread) {node = node.left;}while(node != null) {System.out.print(node.data + ", ");//如果右指針是線索if(node.isRightThread) {node = node.right;} else { //如果右指針不是線索，找到右子樹(shù)開(kāi)始的節(jié)點(diǎn)node = node.right;while(node != null && !node.isLeftThread) {node = node.left;}}}}/*** 中序遍歷線索二叉樹(shù)，按照前驅(qū)方式遍歷（思路：找到最右子節(jié)點(diǎn)開(kāi)始倒序遍歷）* @param node*/void inPreThreadList(Node node) {//1、找最后一個(gè)節(jié)點(diǎn)while(node.right != null && !node.isRightThread) {node = node.right;}while(node != null) {System.out.print(node.data + ", ");//如果左指針是線索if(node.isLeftThread) {node = node.left;} else { //如果左指針不是線索，找到左子樹(shù)開(kāi)始的節(jié)點(diǎn)node = node.left;while(node.right != null && !node.isRightThread) {node = node.right;}}}}/*** 前序線索化二叉樹(shù)* @param node*/void preThreadOrder(Node node) {if(node == null) {return;}//左指針為空,將左指針指向前驅(qū)節(jié)點(diǎn)if(node.left == null) {node.left = preNode;node.isLeftThread = true;}//前一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)if(preNode != null && preNode.right == null) {preNode.right = node;preNode.isRightThread = true;}preNode = node;//處理左子樹(shù)if(!node.isLeftThread) {preThreadOrder(node.left);}//處理右子樹(shù)if(!node.isRightThread) {preThreadOrder(node.right);}}/*** 前序遍歷線索二叉樹(shù)（按照后繼線索遍歷）* @param node*/void preThreadList(Node node) {while(node != null) {while(!node.isLeftThread) {System.out.print(node.data + ", ");node = node.left;}System.out.print(node.data + ", ");node = node.right;}}public static void main(String[] args) {String[] array = {"A", "B", "C", "D", "E", "F", "G", "H"};Node root = createBinaryTree(array, 0);ThreadBinaryTree tree = new ThreadBinaryTree();tree.inThreadOrder(root);System.out.println("中序按后繼節(jié)點(diǎn)遍歷線索二叉樹(shù)結(jié)果：");tree.inThreadList(root);System.out.println("\n中序按后繼節(jié)點(diǎn)遍歷線索二叉樹(shù)結(jié)果：");tree.inPreThreadList(root);Node root2 = createBinaryTree(array, 0);ThreadBinaryTree tree2 = new ThreadBinaryTree();tree2.preThreadOrder(root2);tree2.preNode = null;System.out.println("\n前序按后繼節(jié)點(diǎn)遍歷線索二叉樹(shù)結(jié)果：");tree.preThreadList(root2);} }

---

四、小結(jié)

線索化的實(shí)質(zhì)就是將二叉鏈表中的空指針改為指向前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)的線索；

線索化的過(guò)程就是修改二叉鏈表中空指針的過(guò)程，可以按照前序、中序、后序的方式進(jìn)行遍歷，分別生成不同的線索二叉樹(shù)；

有了線索二叉樹(shù)之后，我們?cè)俅伪闅v時(shí)，就相當(dāng)于操作一個(gè)雙向鏈表。

使用場(chǎng)景：如果我們?cè)谑褂枚鏄?shù)過(guò)程中經(jīng)常需要遍歷二叉樹(shù)或者查找節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，可以考慮采用線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)。

總結(jié)

以上是生活随笔為你收集整理的线索二叉树原理及前序、中序线索化（Java版）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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