數(shù)據(jù)結(jié)構(gòu)與算法--線索二叉樹及其前序、中序遍歷

二叉樹如果某個結(jié)點沒有左孩子或右孩子，則這個域就為空。如node.lChild = null，

而葉子結(jié)點兩個指針域都是null。我們知道n個結(jié)點的二叉樹共有2n個指針域，樹只有n-1條分支，也就是說還有2n - (n -1) = n + 1個域是空指針。為了充分利用這些空指針，可以存一些有用的信息——比如某結(jié)點的前驅(qū)和后繼結(jié)點（按某種次序遍歷后的順序）。這種指向前序后繼的指針稱為線索，具有前驅(qū)后繼關(guān)系的二叉樹叫線索二叉樹。線索二叉樹的好處是：不僅節(jié)約了空間，而且一旦按照某種次序（中序、前序或后序）遍歷一次后，線索信息就已經(jīng)初始化好，下次想要獲取某個結(jié)點的前驅(qū)后繼就不用再遍歷整棵樹了。

具體來說，對于所有空指針域，lChild指向該結(jié)點的前驅(qū)結(jié)點；rChild指向該結(jié)點的后繼結(jié)點。但是lChild和rChild同時也表示某結(jié)點的左孩子和右孩子，一個指針有兩種意思，對某個結(jié)點究竟指代的哪種意思？顯然需要一個標志加以區(qū)分，我們給每個結(jié)點的孩子加上標志，如果是false則表示左/右孩子，如果是true則表示前驅(qū)/后繼。這棵二叉樹中序遍歷的結(jié)果是HDIBEAFCG，按照遍歷所得順序，H的后繼就是D，h.rChild本來是null，現(xiàn)在讓其指向D，由于這表示后繼，所以相應(yīng)的標志位應(yīng)該設(shè)置為true。這幅圖將所有rChild為空的指針域都指向了其后繼。

那么前驅(qū)呢？自然是將所有l(wèi)Child為空的指針域指向該結(jié)點的前驅(qū)。如下圖。

如果將這兩幅圖結(jié)合起來，則每個空指針域都已用上了。這棵二叉樹就成了下面這個樣子

虛線表示右孩子或者后繼，實線表示左孩子或者前驅(qū)，具體怎么區(qū)分也就是看給結(jié)點左右孩子設(shè)置的標志位了。仔細觀察，把這顆樹兩頭拉直，就成了雙向鏈表?。ǖ趾推胀ǖ碾p向鏈表不同，這里前驅(qū)后繼的含義指代比較模糊）

現(xiàn)在來試著實現(xiàn)一下。

package Chap6;

public class ThreadTree<Item> {
    public static class Node<T> {
        private T data;
        private Node<T> lchild;
        private Node<T> rchild;
        private boolean isleftThead;
        private boolean isRightThead;

        public Node(T data) {
            this.data = data;
            isleftThead = false;
            isRightThead = false;
        }

        public T getData() {
            return data;
        }

        public Node<T> getLchild() {
            return lchild;
        }

        public Node<T> getRchild() {
            return rchild;
        }

        @Override
        public String toString() {
            String lchildInfo = lchild == null ? null : lchild.getData().toString();
            String rchildInfo = rchild == null ? null : rchild.getData().toString();

            return "Node{" +
                    "data=" + data +
                    ", lchild=" + lchildInfo +
                    ", rchild=" + rchildInfo +
                    '}';
        }
    }

    private Node<Item> root;
    private Node<Item> preNode;
    private int nodesNum;

    public void setRoot(Item data) {
        root = new Node<>(data);
        nodesNum++;
    }

    public void addLeftChild(Item data, Node<Item> parent) {
        parent.lchild = new Node<>(data);
        nodesNum++;
    }

    public void addRightChild(Item data, Node<Item> parent) {
        parent.rchild = new Node<>(data);
        nodesNum++;
    }

    public Node<Item> root() {
        return root;
    }

    /**
     * 中序遍歷線索化二叉樹
     */
    public void inOrderThread(Node<Item> node) {
        if (node == null) {
            return;
        }
        inOrderThread(node.lchild);

        if (node.lchild == null) {
            node.lchild = preNode;
            node.isleftThead = true;
        }

        if (preNode != null && preNode.rchild == null) {
            preNode.rchild = node;
            preNode.isRightThead = true;
        }
        // preNode始終表示上一個訪問的結(jié)點
        preNode = node;
        inOrderThread(node.rchild);
    }

    public void inOrderThread() {
        inOrderThread(root);
    }

    public void inOrderTraversal(Node<Item> node) {
        // 不斷深入左子樹,只要某個結(jié)點左孩子為空，則標志位肯定為true
        while (node != null) {
            while (!node.isleftThead) {
                node = node.lchild;
            }

            System.out.print(node.getData() + " ");
            while (node.isRightThead && node.rchild != null) {
                node = node.rchild;
                System.out.print(node.getData() + " ");
            }
            node = node.rchild;
        }
    }

    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    /**
     * 前序遍歷線索化二叉樹
     */
    public void preOrderThread(Node<Item> node) {
        if (node == null) {
            return;
        }

        if (node.lchild == null) {
            node.lchild = preNode;
            node.isleftThead = true;
        }

        if (preNode != null && preNode.rchild == null) {
            preNode.rchild = node;
            preNode.isRightThead = true;
        }
        // preNode始終表示上一個訪問的結(jié)點
        preNode = node;
        // 這里需要判斷，因為node.lchild和node.rchild可能已經(jīng)被設(shè)置了標志。若還遞歸就會打亂了已設(shè)置好的標志位，而且還會StackOverflow
        // 而中序遍歷遞歸是，標志位均未被設(shè)置，所以無需判斷
        if (!node.isleftThead) {
            preOrderThread(node.lchild);
        }
        if (!node.isRightThead) {
            preOrderThread(node.rchild);
        }
    }

    public void preOrderThread() {
        preOrderThread(root);
    }

    public void preOrderTraversal(Node<Item> node) {
        while (node != null) {
            while (!node.isleftThead) {
                System.out.print(node.getData() + " ");
                node = node.lchild;
            }

            System.out.print(node.getData() + " ");
            node = node.rchild;
        }
    }

    public void preOrderTraversal() {
        preOrderTraversal(root);
    }

    public static void main(String[] args) {
        ThreadTree<String> tree = new ThreadTree<>();
        tree.setRoot("A");
        Node<String> root = tree.root();
        tree.addLeftChild("B", root);
        tree.addRightChild("C", root);
        tree.addLeftChild("D", root.getLchild());

        tree.addLeftChild("E", root.getRchild());
        tree.addRightChild("F", root.getRchild());
        tree.addLeftChild("G", root.getLchild().getLchild());
        tree.addRightChild("H", root.getLchild().getLchild());
        tree.addRightChild("I", root.getRchild().getLchild());

        System.out.println("中序線索化并遍歷");
        tree.inOrderThread();
        tree.inOrderTraversal();

        // 線索化只能調(diào)用一次?。?！一旦設(shè)置好，就不要去打亂了。所以想運行上面的需要注釋掉下面的
//        System.out.println("前序線索化并遍歷");
//        tree.preOrderThread();
//        tree.preOrderTraversal();
    }
}

首先是Node類增加了標志位isleftThead和isRightThread，含義上面解釋過了。然后是ThreadTree類除了有個root成員，還新增了preNode成員，專門表示在線索化中上一個剛訪問過的結(jié)點。部分方法直接使用了普通二叉樹的代碼。這里著重說一下線索化的代碼。前序和后序線索化及遍歷都比較簡單，后序復雜一點我也懶得去實現(xiàn)了。

中序線索化及中序遍歷

之所以稱為中序線索化，是因為它和普通二叉樹中序遍歷的遞歸實現(xiàn)，代碼結(jié)構(gòu)幾乎一樣。看單獨抽取出來的中序線索化實現(xiàn)，只要把中序遍歷遞歸實現(xiàn)中的打印操作換成注釋了begin和end之間的代碼就OK了。

public void inOrderThread(Node<Item> node) {
    if (node == null) {
        return;
    }
    inOrderThread(node.lchild);
    // begin
    if (node.lchild == null) {
      node.lchild = preNode;
      node.isleftThead = true;
    }

    if (preNode != null && preNode.rchild == null) {
        preNode.rchild = node;
        preNode.isRightThead = true;
    }
    // preNode始終表示上一個訪問的結(jié)點
    preNode = node;
    // end
    inOrderThread(node.rchild);
}

中間的代碼做的事主要是：

• 某結(jié)點的左孩子為空，設(shè)置標志位為true，且讓上一個結(jié)點成為當前結(jié)點的前驅(qū)。
• 某結(jié)點的右孩子為空，設(shè)置標志位為true，且讓當前結(jié)點成為前一個結(jié)點的后繼。這里因為要調(diào)用preNode的方法，所以要進行判空操作。
• 當前結(jié)點訪問完，即將訪問下一個結(jié)點了，于是當前結(jié)點也就成了上一個結(jié)點preNode。

這里設(shè)置某結(jié)點的后繼之所以使用preNode，理由很簡單，當前結(jié)點的后繼還沒訪問到呢，只能用已經(jīng)訪問過的前一個結(jié)點，它的后繼可能是當前結(jié)點。

再來看中序遍歷。

public void inOrderTraversal(Node<Item> node) {
    // 不斷深入左子樹,直到遇見第一個線索
    while (node != null) {
        while (!node.isleftThead) {
            node = node.lchild;
        }

      System.out.print(node.getData() + " ");
      while (node.isRightThead && node.rchild != null) {
          node = node.rchild;
          System.out.print(node.getData() + " ");
      }
      node = node.rchild;
    }
}

先是從根結(jié)點開始按照左子樹深入，直到遇見第一個左孩子是線索的結(jié)點，緊接著就打印它，這次打印的其實是鏈表頭。接下來看它的右孩子是不是后繼，如果是就繼續(xù)打??；直到右孩子不是線索，此時轉(zhuǎn)到右子樹，開始和根結(jié)點一樣的循環(huán)...最后一個while中需要判斷node.rchild不為空，如果為空，我們打印出來就是null，這不是我們想要看得結(jié)果。

前序線索化

把設(shè)置標志那一團代碼放到遞歸左右子樹之前，就成了前序線索化。特別注意，在遞歸前判斷了是否為線索結(jié)點。因為前序線索化中，遞歸發(fā)生在設(shè)置標志位之后，所以node.lchild和node.rchild可能已經(jīng)被設(shè)置了標志。若還遞歸就會打亂了已設(shè)置好的標志位，而且還會發(fā)生StackOverflow。而中序線索化中無需判斷是因為，遞歸左子樹發(fā)生在設(shè)置左孩子的線索之前，而右孩子的線索的設(shè)置是針對上一個結(jié)點的，當前結(jié)點的右孩子并沒有線索化，所以對當前結(jié)點的右子樹node.rchild的遞歸并沒有影響。

if (!node.isleftThead) {
    preOrderThread(node.lchild);
}
if (!node.isRightThead) {
    preOrderThread(node.rchild);
}

接著看前序遍歷的。還是根結(jié)點開始，深入左子樹，只要沒遇到左孩子是線索的結(jié)點，就立即打印。然后跳出while循環(huán)打印第一個左孩子是線索的結(jié)點。然后轉(zhuǎn)向其后繼或者是右子樹，繼續(xù)大循壞...

如果我們經(jīng)常需要遍歷二叉樹，并且要知道某結(jié)點的前驅(qū)后繼信息，那么使用線索二叉樹是個不錯的選擇。特別注意一點，線索化只能執(zhí)行一次，已經(jīng)設(shè)置好的標志信息就不要再設(shè)置第二次了（除非清空標志位），否則會導致標志位的混亂，導致遍歷失敗。

by @sunhaiyu

2017.9.14