線索二叉樹

1. 線索二叉樹簡介

定義： 在二叉樹的結點上加上線索的二叉樹稱為線索二叉樹。

二叉樹的線索化： 對二叉樹以某種遍歷方式（如先序、中序、后序或層次等）進行遍歷，使其變為線索二叉樹的過程稱為對二叉樹進行線索化。

現在我們來計算一下任意一顆二叉樹有多少個空的指針域

假設有n個結點，一個結點有2個指針域(指向左右子節點)，一共就有2n個結點

除了第一個結點不需要父節點指向，其余所有節點均需要指針，所以有n-1個已經使用的指針域

剩下：2*n-(n-1)=n+1

結論：任意二叉樹的空余指針域為n+1

如上圖所示：紅線就是將二叉樹線索化變成線索二叉樹的過程。

通俗的講：將普通二叉樹的空余指針域都利用起來，指向其前驅結點或后繼結點就變成了線索二叉樹

2. 線索二叉樹的實現

2.1 實現思路

首先我們需要選擇線索化二叉樹的方式-這里我們使用中序線索化二叉樹

在遍歷每個節點時，判斷結點的左子節點和右子節點是否為空(也就是左右指針域)

如果左子節點為空就將其指向當前結點的前驅結點

如果右子節點為空就指向后繼結點(這里的前驅、后繼結點是相對于遍歷方式而言)

相比普通二叉樹我們增加兩個標志位：leftType、rightType

2.2 實現代碼

二叉樹結點類：ThreadedBinaryNode.java

//中序線索二叉樹 public class ThreadedBinaryNode {//結點的值int value;//左節點ThreadedBinaryNode leftNode;//右節點ThreadedBinaryNode rightNode;//線索二叉樹增加的兩個屬性//1代表存儲的是前驅、后續結點。0代表左右兒子(默認為0)int leftType,rightType;//初始化值public ThreadedBinaryNode(int value){this.value=value;}//設置左節點public void setLeftNode(ThreadedBinaryNode leftNode) {this.leftNode = leftNode;}//設置右節點public void setRightNode(ThreadedBinaryNode rightNode) {this.rightNode = rightNode;} }

線索二叉樹類：ThreadedBinaryTree.java

增加了一個存儲前驅結點的pre，主要實現中序線索化的threadedMid方法，遍歷方法threadedIterate

public class ThreadedBinaryTree {//根節點ThreadedBinaryNode root;//存儲前序結點ThreadedBinaryNode pre=null;//設置根節點、獲取根節點public ThreadedBinaryNode getRoot() {return root;}public void setRoot(ThreadedBinaryNode root) {this.root = root;}//遍歷中序化線索二叉樹public void threadedIterate(){ThreadedBinaryNode node=root;while(node!=null){//先找到中序遍歷最左邊的結點while(node.leftType==0){node=node.leftNode;}System.out.print(node.value+" ");//遍歷右指針域指向后繼基點的結點while(node.rightType==1){node=node.rightNode;System.out.print(node.value+" ");}//替換遍歷結點node=node.rightNode;}}//方便調用public void threadedMid(){threadedMid(root);}//中序線索化二叉樹-將左右指針域為空的標記1，不為空(指向左右兒子)的默認為0public void threadedMid(ThreadedBinaryNode node){if(node==null)return;//遞歸處理左子樹threadedMid(node.leftNode);//處理當前結點的左指針域if(node.leftNode==null){//將當前結點的左指針域指向前序結點node.leftNode=pre;//標記node.leftType=1;}//處理前驅結點pre的右指針域//因為這里拿不到當前結點的下一個結點，所以不能處理當前節點的右指針域if(pre!=null&&pre.rightNode==null){//如果pre的右指針為空，就指向他的后繼結點-nodepre.rightNode=node;pre.rightType=1;}//保存當前結點，為下一結點的prepre=node;//遞歸處理右子樹threadedMid(node.rightNode);} }

測試類

public class TestThreadedTree {public static void main(String[] args) {//創建一顆空二叉樹ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();//創建根結點ThreadedBinaryNode root=new ThreadedBinaryNode(1);threadedBinaryTree.setRoot(root);//創建根結點的左節點和右節點ThreadedBinaryNode leftNode = new ThreadedBinaryNode(2);ThreadedBinaryNode rightNode = new ThreadedBinaryNode(3);//將左右結點連接在根結點后root.setLeftNode(leftNode);root.setRightNode(rightNode);//增加四個節點 4、5、6、7方便遍歷leftNode.setLeftNode(new ThreadedBinaryNode(4));leftNode.setRightNode(new ThreadedBinaryNode(5));rightNode.setLeftNode(new ThreadedBinaryNode(6));rightNode.setRightNode(new ThreadedBinaryNode(7));//中序線索化二叉樹threadedBinaryTree.threadedMid();//遍歷中序線索二叉樹System.out.println("遍歷中序線索二叉樹結果為：");threadedBinaryTree.threadedIterate();} }

結果：

遍歷中序線索二叉樹結果為： 4 2 5 1 6 3 7

3. 總結：

線索二叉樹減少了的空指針域的同時又對每個節點增加了兩個標志位。好處：在遍歷時不需要使用遞歸，相比普通二叉樹遍歷效率更高在查找前驅/后繼結點時更加高效

4. 應用

當路由器使用CIDR，選擇下一跳的時候，或者轉發分組的時候，通常會用最長前綴匹配（最佳匹配）來得到路由表的一行數據，為了更加有效的查找最長前綴匹配，通常使用的數據結構為二叉線索。

總結

以上是生活随笔為你收集整理的【线索二叉树详解】数据结构06(java实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。