摘要：

1，線索二叉樹的介紹

2，二叉樹的前序線索化

3，線索二叉樹的前序遍歷

4，線索二叉樹中查找后繼節點

1，線索二叉樹的介紹

我們知道在二叉樹中每個節點都有兩個指針，分別指向左子樹和右子樹。如果某個節點只有一個子節點，那么它有一個指針是指向空的，如果某個節點是葉子節點，那么它的兩個指針都指向空。

在一個有 N 個節點的二叉樹中有 N+1 個指針是指向空的。這是因為在 N 個節點的二叉樹中，每個節點有 2 個指針，所以一共有 2N 個指針，除了根節點以外每一個節點都有一個指針從它的父節點指向它，所以一共使用了 N-1 個指針，還剩下 N+1 個指針是指向空的。

這些空的指針能不能被利用起來呢？當然是可以的，如果一個節點的左指針為空，就讓它的左指針指向它的前驅節點，如果一個節點的右指針為空，就讓它的右指針指向它的后繼節點，這樣構造的二叉樹就是線索二叉樹。

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

對二叉樹以某種遍歷順序進行掃描并為每個節點添加線索的過程稱為二叉樹的線索化，進行線索化的目的是為了加快查找二叉樹中某節點的前驅和后繼的速度。

實際上在線索二叉樹中只有中序線索二叉樹中可以快速查找某個節點的前驅節點和后繼節點，而在前序線索二叉樹中只能快速查找后繼節點，后序線索二叉樹中只能快速查找前驅節點。

為了區分一個節點的左指針究竟是指向左子節點還是前驅節點，我們需要使用一個變量來區分，同理右指針也一樣，節點類如下。

Java 代碼：

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(int val) {
        this.val = val;
    }
}

C++ 代碼：

struct TreeNode {
    int val;// 節點值
    // isPre 為false時，left指向左子節點。
    // isPre 為true時，left指向前驅節點。
    // isPost 為false時，right指向右子節點。
    // isPost 為true時，right指向后繼節點。
    bool isPre = false, isPost = false;
    // 二叉樹的左右子節點
    TreeNode *left = nullptr;// 左子樹
    TreeNode *right = nullptr;// 右子樹
    TreeNode(int val) : val(val) {}
};