線索二叉樹圖文詳解

線索二叉樹（或引線二叉樹，Threaded BinaryTree）是添加了直接指向節點的前驅和後繼指針的二叉樹。我們知道在二叉樹中每個節點都有兩個指針，分別指向左子樹和右子樹。如果某個節點只有一個子節點，那麼它有一個指針是指向空的，如果某個節點是葉子節點，那麼他的兩個指針都指向空。這些空的指針能不能被利用起來呢？當然是可以的。

如果一個節點的左指針爲空，就讓他左指針指向他的前驅節點，如果一個節點的右指針爲空，就讓他右指針指向他的後繼節點。這樣構造的二叉樹就是線索二叉樹。爲了區分一個節點的左指針究竟是指向左子節點還是前驅節點，我們需要使用一個變量來區分，同理右指針也一樣，節點類如下。

 public class BiTreeNode{
     public int val;// 節點值
     // isPre 爲false時，left指向左子節點。
     // isPost 爲false時，right指向右子節點。
     // isPre 爲true時，left指向前驅節點。
     // isPost 爲true時，right指向後繼節點。
     public boolean isPre, isPost;
     // 二叉樹的左右子節點
     public BiTreeNode left, right;
     public BiTreeNode parent;// 後續遍歷的時候會用到，前序和中序遍歷用不到。

     public BiTreeNode() {
    }

     public BiTreeNode(int val) {
         this.val = val;
    }
 }

注意這裏的說的前驅節點和後繼節點在不同的遍歷方式中值是不同的。比如前序遍歷的結果是 [a，b，c，d]，那麼 b 的前驅節點就是 a ，後繼節點是 c 。比如後續遍歷的結果是 [a，b，c，d]，c 的前驅節點就是 b ，後繼節點是 d 。

線索化

對二叉樹以某種遍歷順序進行掃描併爲每個節點添加線索的過程稱爲二叉樹的線索化，進行線索化的目的是爲了加快查找二叉樹中某節點的前驅和後繼的速度。 那麼在有 N 個節點的二叉樹中需要利用 N+1 個空指針添加線索。這是因爲在 N 個節點的二叉樹中，每個節點有 2 個指針，所以一共有 2N 個指針，除了根節點以外每一個節點都有一個指針從它的父節點指向它，所以一共使用了 N-1 個指針。所以剩下 2N-(N-1) 個空指針（來自維基百科）。

無論是前序遍歷，中序遍歷還是後序遍歷，如果一個節點沒有左子節點就讓他的左指針指向他的前驅節點，如果一個節點沒有後繼節點，就讓他的右指針指向他的後繼節點。我們來看下二叉樹的前中後三種線索化的步驟。

二叉樹前序線索化

二叉樹的前序線索化如上圖所示，這裏要注意遍歷的時候需要使用一個變量 pre 記錄每一個節點的前驅節點，

• 如果當前節點的左指針爲空，就讓當前節點的左指針指向前驅節點 pre 。

• 如果當前節點的右指針爲空，需要讓當前節點的右指針指向他的後繼節點，但是這個時候後繼節點還沒有遍歷到。所以這個時候我們一般不操作當前節點，而是操作前一個節點，因爲當前節點是前一個節點的後繼節點。如果前一個節點 pre 的右指針爲空，就讓 pre 的右指針指向當前節點。

代碼如下所示。

 // 前驅節點
 private BiTreeNode pre;

 // 二叉樹的前序線索化算法
 private void preThread(BiTreeNode root) {
     if (root == null)
         return;

     // 左子節點爲空，讓left指向前驅節點
     if (root.left == null) {
         root.left = pre;
         root.isPre = true;//left標記爲指向前驅節點。
    }

     // 處理的是前一個節點的右子節點。
     if (pre != null && pre.right == null) {
         pre.right = root;// pre的右指針指向當前節點
         pre.isPost = true;
    }

     pre = root;// 更新pre節點

     if (!root.isPre)
         preThread(root.left);// 遞歸左子樹

     if (!root.isPost)
         preThread(root.right);// 遞歸右子樹
 }

二叉樹中序線索化

二叉樹的前序，中序以及後續線索化代碼非常相似，只不過線索化的位置不太一樣，來看下。

 // 二叉樹的中序線索化算法
 private void inThread(BiTreeNode root) {
     if (root == null)
         return;
     if (!root.isPre)
         inThread(root.left);  // 遞歸左子樹

     // 左子節點爲空，處理的是當前節點。
     if (root.left == null) {
         root.left = pre;// 左指針指向前驅節點
         root.isPre = true;
    }

     // 處理的是上一個節點的右子節點。
     if (pre != null && pre.right == null) {
         pre.right = root;// pre的右指針指向後繼節點
         pre.isPost = true;
    }

     pre = root;// 更新pre節點

     if (!root.isPost)
         inThread(root.right);  // 遞歸右子樹
 }

二叉樹後序線索化

後線索化之後在遍歷的時候不太方便，遍歷的時候還需要知道每個節點的父節點，所以在線索化的時候要記錄下。

線索二叉樹的後序遍歷可以看做是從下往上遍歷，如果根節點沒有右子節點，相當於根節點是最後一個被遍歷的，我們查找後繼節點的時候都是操作前一個節點，所以根節點的後繼節點沒有被賦值，所以在操作完之後還需要單獨判斷下。

 private void postThread(BiTreeNode root) {
     postThreadHelper(root);
     // 如果根節點沒有右子節點，需要把根節點的 isPost 變成 true 。
     if (root.right == null)
         root.isPost = true;
 }

 private void postThreadHelper(BiTreeNode root) {
     if (root == null)
         return;

     // 如果有父節點，記錄當前節點的父節點。
     if (root.left != null && !root.isPre)
         root.left.parent = root;
     if (root.right != null && !root.isPost)
         root.right.parent = root;

     if (!root.isPre)
         postThreadHelper(root.left);  // 遞歸左子樹
     if (!root.isPost)
         postThreadHelper(root.right);  // 遞歸右子樹

     // 左子節點爲空，處理的是當前節點。
     if (root.left == null) {
         root.left = pre;// 左指針指向前驅節點
         root.isPre = true;
    }

     // 處理的是上一個節點的右子節點。
     if (pre != null && pre.right == null) {
         pre.right = root;
         pre.isPost = true;
    }

     pre = root;// 更新pre節點
 }

線索二叉樹前序遍歷

在線索二叉樹的前序遍歷中先打印當前節點，然後是左子節點，最後是右子節點。根節點就是第一個被訪問的節點，所以從根節點開始打印。如果當前節點有左子節點，把右指針斷開。如果當前節點沒有左子節點，把左指針（指向前驅節點）斷開。注意這裏的斷開並不是真正的斷開，只是我們假象的。如下圖所示，就變成了一個鏈表，這題就變成了對鏈表的打印，這個就比較簡單了。

步驟如下：

• 如果當前節點有左子節點下一步到到當前節點的左子節點。

• 如果當前節點沒有左子節點，下一步到當前節點的右子節點。注意這裏的右子節點並不一定是真正的右子節點，也有可能是我們線索化的時候串起來的。所以這裏不需要判斷究竟是右子節點還是後繼節點。

代碼如下：

 private void threadPreTraverse(BiTreeNode root) {
     BiTreeNode cur = root;
     while (cur != null) {
         System.out.println(cur.val);// 打印當前節點
         // 如果沒有左子節點，下一步到右子節點，否則下一步繼續到左子節點。
         cur = cur.isPre ? cur.right : cur.left;
    }
 }

線索二叉樹中序遍歷

線索二叉樹中序遍歷的順序是左子節點，當前節點，右子節點。在打印當前節點的時候必須把當前節點的左子樹都打印完才能打印當前節點。所以在打印當前節點之前必須先找到當前節點一直往左的節點。

步驟如下：

• 一直找到最左邊的節點，然後打印該節點。

• 如果該節點有右子節點，繼續按照上面的步驟操作右子節點。

• 如果該節點沒有右子節點，就一直遍歷後繼節點，直到沒有後繼節點爲止。

代碼如下：

 private void threadInTraverse(BiTreeNode root) {
     BiTreeNode cur = root;
     while (cur != null) {
         // 一直往左找到最左邊的子節點。
         while (!cur.isPre)
             cur = cur.left;
         System.out.println(cur.val);
         // 如果沒有右子節點，一直遍歷後繼節點，否則找右子節點。
         while (cur.isPost) {
             cur = cur.right;// 到 cur 的後繼節點。
             System.out.println(cur.val);
        }
         cur = cur.right;
    }
 }

線索二叉樹後序遍歷

線索二叉樹後序遍歷的順序是左子節點，右子節點，當前節點。他是先打印子節點，最後在打印當前節點。可以看做是二叉樹從下往上打印，我們知道在二叉樹中可以很容易找到一個節點的子節點，但很難找到一個節點的父節點，所以在前面二叉樹後序遍歷線索化的時候我們記錄了每一個節點的父節點。

步驟如下：

• 找到當前節點最左邊的節點，看他有沒有右子節點，如果沒有右子節點，直接打印該節點，下一步到該節點的後繼節點。

• 如果有右子節點需要打印完右子樹之後才能打印該節點，所以需要判斷右子樹有沒有被打印完，如果右子樹沒被打印完，到右子樹中繼續按照上面的步驟執行。如果右子樹打印完了，就打印該節點，表示該節點爲根節點的子樹也都被打印完了，下一步到該節點的父節點繼續打印。

代碼如下：

 private void threadPostTraverse(BiTreeNode root) {
     BiTreeNode cur = root;
     // 找到最左邊的節點
     while (cur != null && !cur.isPre)
         cur = cur.left;
     BiTreeNode pre = null;// 後序遍歷中前一個節點
     while (cur != null) {
         if (cur.isPost) {
             // 如果沒有右子節點，就打印當前節點。
             System.out.println(cur.val);
             pre = cur;
             cur = cur.right;// 下一步到後繼節點
        } else {
             // 如果有右子節點，判斷右子樹有沒有打印完。
             if (cur.right == pre) {
                 // 當前節點的子樹都打印完了，打印當前節點。
                 System.out.println(cur.val);
                 pre = cur;// 更新 pre 節點。
                 // 後續遍歷可以看做是從下往上打印，右子節點都打印完了，下一步該到父節點了
                 cur = cur.parent;
            } else {// 當前節點的右子樹還沒打印，到右子樹中打印。
                 cur = cur.right;
                 // 還是找到當前節點最左邊的節點。
                 while (cur != null && !cur.isPre)
                     cur = cur.left;
            }
        }
    }
 }

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/SMS4qkxFkaRA11uPYyfuyQ