什么是Java線索化二叉樹

本篇內(nèi)容主要講解“什么是Java線索化二叉樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“什么是Java線索化二叉樹”吧!

先看一個(gè)問題

將數(shù)列{1,3,6,8,10,14}構(gòu)建成一顆二叉樹.n+1=7,如下圖所示

問題分析：

1. 當(dāng)我們對上面的二叉樹進(jìn)行中序遍歷時(shí)，數(shù)列為{8,3,10,1,14,6}

2. 但是6，8，10，14這幾個(gè)節(jié)點(diǎn)的左右指針，并沒有完全的利用上。

3. 如果我們希望充分的利用各個(gè)節(jié)點(diǎn)的左右指針，讓各個(gè)節(jié)點(diǎn)指向自己的前后節(jié)點(diǎn)怎么辦?

4. 解決方案-線索二叉樹

線索二叉樹基本介紹

1. n 個(gè)節(jié)點(diǎn)的二叉鏈表中含有n+1【公式  2n-(n-1)=n+1】個(gè)空指針域。利用二叉鏈表中的空指針域，存放該節(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼點(diǎn)的指針(這種附加的指針稱為線索)。

2. 這種加了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded  BinaryTree)。根據(jù)線索的性質(zhì)不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹、后序線索二叉樹三種。

3. 一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，稱為前驅(qū)節(jié)點(diǎn)。

4. 一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，稱為后繼節(jié)點(diǎn)。

中序線索二叉樹圖解

中序遍歷的結(jié)果{8,3,10,1,14,6}

說明：當(dāng)線索化二叉樹后，Node節(jié)點(diǎn)的屬性left和right,有如下情況：

1. left指向的值左子樹，也可能是指向的前驅(qū)節(jié)點(diǎn)，比如①節(jié)點(diǎn)left指向的左子樹，而⑩節(jié)點(diǎn)的left指向的就是前驅(qū)節(jié)點(diǎn)。

2. right指向的右子樹，也可能是指向后繼節(jié)點(diǎn)，比如①節(jié)點(diǎn)right指向的是右子樹，而⑩節(jié)點(diǎn)的right指向的是后繼節(jié)點(diǎn)。

代碼案例

package com.xie.tree.threadedbinarytree;  public class ThreadedBinaryTreeDemo {     public static void main(String[] args) {         //測試中序線索二叉樹         HeroNode root = new HeroNode(1, "tom");         HeroNode node2 = new HeroNode(3, "jack");         HeroNode node3 = new HeroNode(6, "smith");         HeroNode node4 = new HeroNode(8, "mary");         HeroNode node5 = new HeroNode(10, "king");         HeroNode node6 = new HeroNode(14, "dim");          root.setLeft(node2);         root.setRight(node3);          node2.setLeft(node4);         node2.setRight(node5);          node3.setLeft(node6);          ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();         threadedBinaryTree.setRoot(root);         threadedBinaryTree.threadedNodes();          //測試：以10號節(jié)點(diǎn)測試         HeroNode left = node5.getLeft();         System.out.println("10號節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是：" + left);         HeroNode right = node5.getRight();         System.out.println("10號節(jié)點(diǎn)的后繼節(jié)點(diǎn)是：" + right);          System.out.println("使用線索化的方式遍歷 線索二叉樹");         threadedBinaryTree.threadedBinaryTreeList();          /**          * 10號節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是：HeroNode{no=3, name=jack}          * 10號節(jié)點(diǎn)的后繼節(jié)點(diǎn)是：HeroNode{no=1, name=tom}          * 使用線索化的方式遍歷 線索二叉樹          * HeroNode{no=8, name=mary}          * HeroNode{no=3, name=jack}          * HeroNode{no=10, name=king}          * HeroNode{no=1, name=tom}          * HeroNode{no=14, name=dim}          * HeroNode{no=6, name=smith}          */      } }  //實(shí)現(xiàn)了線索化功能的二叉樹 class ThreadedBinaryTree {     private HeroNode root;     //為了實(shí)現(xiàn)線索化，需要創(chuàng)建一個(gè)指向當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針     //在遞歸進(jìn)行線索化時(shí)，pre總是保留前一個(gè)節(jié)點(diǎn)     private HeroNode pre;      public void setRoot(HeroNode root) {         this.root = root;     }      /**      * 遍歷線索化二叉樹的方法。      */     public void threadedBinaryTreeList() {         //定義一個(gè)變量，存儲當(dāng)前遍歷的節(jié)點(diǎn)，從root開始         HeroNode node = root;         while (node != null) {             //循環(huán)找到leftType==1的節(jié)點(diǎn),第一個(gè)找到就是8節(jié)點(diǎn)             //后面隨著遍歷而變化，因?yàn)楫?dāng)leftType==1時(shí)，說明該節(jié)點(diǎn)是按照線索化處理后的有效節(jié)點(diǎn)             while (node.getLeftType() == 0) {                 node = node.getLeft();             }             //打印當(dāng)前節(jié)點(diǎn)             System.out.println(node);             //如果當(dāng)前節(jié)點(diǎn)的右指針指向的是后繼節(jié)點(diǎn)，就一直輸出             while (node.getRightType() == 1) {                 //獲取到當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)                 node = node.getRight();                 System.out.println(node);             }             //替換這個(gè)遍歷的節(jié)點(diǎn)             node = node.getRight();         }     }      /**      * 重載threadedNodes方法      */     public void threadedNodes() {         threadedNodes(root);     }      /**      * 編寫對二叉樹進(jìn)行線索化的方法      *      * @param node 當(dāng)前需要線索化的節(jié)點(diǎn)      */     public void threadedNodes(HeroNode node) {         if (node == null) {             return;         }          //先線索化左子樹         threadedNodes(node.getLeft());         //線索化當(dāng)前節(jié)點(diǎn)【有難度】          //處理當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)         //以8節(jié)點(diǎn)來理解，8節(jié)點(diǎn).left=null         if (node.getLeft() == null) {             //讓當(dāng)前節(jié)點(diǎn)的左指針指向前驅(qū)節(jié)點(diǎn)             node.setLeft(pre);             //修改當(dāng)前節(jié)點(diǎn)的左指針類型             node.setLeftType(1);         }          //處理后繼節(jié)點(diǎn)         if (pre != null && pre.getRight() == null) {             //讓前驅(qū)節(jié)點(diǎn)的右指針指向當(dāng)前節(jié)點(diǎn)             pre.setRight(node);             //修改前驅(qū)節(jié)點(diǎn)的右指針類型             pre.setRightType(1);         }         //每處理一個(gè)節(jié)點(diǎn)后，讓當(dāng)前節(jié)點(diǎn)是下一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)         pre = node;          //再線索化右子樹         threadedNodes(node.getRight());     }  }  //創(chuàng)建HeroNode節(jié)點(diǎn) class HeroNode {     static int preCount = 0;     static int infoxCount = 0;     static int postCount = 0;      private int no;     private String name;     private HeroNode left;     private HeroNode right;      //0 表示指向的是左子樹，1 表示指向的是前驅(qū)節(jié)點(diǎn)     private int leftType;     //0 表示指向右子樹，1 表示指向的是后繼節(jié)點(diǎn)     private int rightType;      public HeroNode(int no, String name) {         this.no = no;         this.name = name;     }      public int getNo() {         return no;     }      public void setNo(int no) {         this.no = no;     }      public String getName() {         return name;     }      public void setName(String name) {         this.name = name;     }      public HeroNode getLeft() {         return left;     }      public void setLeft(HeroNode left) {         this.left = left;     }      public HeroNode getRight() {         return right;     }      public void setRight(HeroNode right) {         this.right = right;     }      public int getLeftType() {         return leftType;     }      public void setLeftType(int leftType) {         this.leftType = leftType;     }      public int getRightType() {         return rightType;     }      public void setRightType(int rightType) {         this.rightType = rightType;     }      @Override     public String toString() {         return "HeroNode{" +                 "no=" + no +                 ", name=" + name +                 '}';     }      //前序遍歷     public void preOrder() {         System.out.println(this);         //遞歸向左子樹前序遍歷         if (this.left != null) {             this.left.preOrder();         }          //遞歸向右子樹前序遍歷         if (this.right != null) {             this.right.preOrder();         }     }      //中序遍歷     public void infixOrder() {         //遞歸向左子樹中序遍歷         if (this.left != null) {             this.left.infixOrder();         }         System.out.println(this);         //遞歸向右子樹中序遍歷         if (this.right != null) {             this.right.infixOrder();         }     }      //后序遍歷     public void postOrder() {         //遞歸向左子樹后序遍歷         if (this.left != null) {             this.left.postOrder();         }         //遞歸向右子樹后序遍歷         if (this.right != null) {             this.right.postOrder();         }         System.out.println(this);     }      //遞歸刪除節(jié)點(diǎn)     //1.如果刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)。     //2.如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，則刪除該樹。     public void delNo(int no) {         /**          * 1.因?yàn)槲覀兊亩鏄涫菃蜗虻?，所以我們是判斷?dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否是需要刪除的節(jié)點(diǎn)，而不能去判斷當(dāng)前節(jié)點(diǎn)是否是需要刪除的節(jié)點(diǎn)。          * 2.如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空，并且左子節(jié)點(diǎn)就是需要刪除的節(jié)點(diǎn)，就將this.left = null；并且返回（結(jié)束遞歸）。          * 3.如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，并且右子節(jié)點(diǎn)就是需要刪除的節(jié)點(diǎn)，將將this.right = null;并且返回（結(jié)束遞歸）。          * 4.如果第2步和第3步?jīng)]有刪除節(jié)點(diǎn)，那么就要向左子樹進(jìn)行遞歸刪除。          * 5.如果第4步也沒有刪除節(jié)點(diǎn)，則應(yīng)當(dāng)向右子樹進(jìn)行遞歸刪除。          */         if (this.left != null && this.left.no == no) {             this.left = null;             return;         }          if (this.right != null && this.right.no == no) {             this.right = null;             return;         }          if (this.left != null) {             this.left.delNo(no);         }          if (this.right != null) {             this.right.delNo(no);         }      }      //前序遍歷查找     public HeroNode preOrderSearch(int no) {          HeroNode res = null;          preCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實(shí)際的比較         //若果找到，就返回         if (this.no == no) {             return this;         }         //沒有找到，向左子樹遞歸進(jìn)行前序查找         if (this.left != null) {             res = this.left.preOrderSearch(no);         }         //如果res ！= null 就直接返回         if (res != null) {             return res;         }         //如果左子樹沒有找打，向右子樹進(jìn)行前序查找         if (this.right != null) {             res = this.right.preOrderSearch(no);         }         //如果找到就返回         if (res != null) {             return res;         }         return res;     }      //中序遍歷查找     public HeroNode infixOrderSearch(int no) {          HeroNode res = null;         if (this.left != null) {             res = this.left.infixOrderSearch(no);         }         if (res != null) {             return res;         }         infoxCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實(shí)際的比較         if (this.no == no) {             return this;         }         if (this.right != null) {             res = this.right.infixOrderSearch(no);         }         if (res != null) {             return res;         }         return res;     }      //后序遍歷查找     public HeroNode postOrderSearch(int no) {          HeroNode res = null;         if (this.left != null) {             res = this.left.postOrderSearch(no);         }         if (res != null) {             return res;         }          if (this.right != null) {             res = this.right.postOrderSearch(no);         }         if (res != null) {             return res;         }         postCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實(shí)際的比較         if (this.no == no) {             return this;         }         return res;     } }

到此，相信大家對“什么是Java線索化二叉樹”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！