摘要：

1，二叉樹的中序線索化

2，中序線索二叉樹查找前驅(qū)節(jié)點

3，中序線索二叉樹查找后繼節(jié)點

4，線索二叉樹的中序遍歷

1，二叉樹的中序線索化

二叉樹線索化的目的主要是為了快速查找一個節(jié)點的前驅(qū)節(jié)點和后繼節(jié)點，具體詳情可以看下前面講的，這里就不在重復(fù)介紹。

在前面我們講過二叉樹的前序線索化只能快速查找一個節(jié)點的后繼節(jié)點，而二叉樹的中序線索化既可以快速查找一個節(jié)點的前驅(qū)節(jié)點，也可以快速查找一個節(jié)點的后繼節(jié)點。二叉樹的節(jié)點類如下：

Java 代碼：

public class TreeNode {
    public int val;// 節(jié)點值
    // isPre 為false時，left指向左子節(jié)點。
    // isPre 為true時，left指向前驅(qū)節(jié)點。
    // isPost 為false時，right指向右子節(jié)點。
    // isPost 為true時，right指向后繼節(jié)點。
    public boolean isPre, isPost;
    // 二叉樹的左右子節(jié)點
    public TreeNode left, right;

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

C++ 代碼：

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

對于二叉樹中序線索化，我們可以按照二叉樹中序遍歷的方式來把節(jié)點串起來，首先還是需要使用一個變量 pre 來記錄當(dāng)前節(jié)點的前一個節(jié)點。

1，如果當(dāng)前節(jié)點的左指針為空，就讓它的左指針指向 pre 節(jié)點。

2，如果 pre 節(jié)點不為空，且 pre 節(jié)點的右指針指向空，就讓 pre 節(jié)點的右指針指向當(dāng)前節(jié)點。

注意中序遍歷中第一個節(jié)點的前驅(qū)節(jié)點是空，因為第一個節(jié)點前面是沒有節(jié)點的。同理最后一個節(jié)點的后繼節(jié)點也是空。