写在前面：
上一讲我们实现了代码量较大的二叉排序树，这一讲我们讲一个新的类型 —— 线索二叉树。这一讲代码量不多，但在理解上需要大家花一点功夫~

思考

在我们之前学到的树中可以发现，一个拥有 N 结点的二叉树，它一定有 N-1 条边是指向节点的即有效分支，但是有 2N-(N-1) = N+1 条边是指向空指针域的，这就导致了空间上的浪费。

此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列。如果所示，中序遍历的结果为 6 3 7 1 2 。但是，这种关系的获得是建立在完成遍历后得到的，那么可不可以在建立二叉树时就记录下前驱后继的关系呢，那么在后续寻找前驱结点和后继结点时将大大提升效率。

线索二叉树的定义

为了利用其这些空指针域，我们将规则定义如下：
若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空，则该结点的右孩子指针指向其后继结点。
这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种次序遍历，并添加线索的过程称为线索化。
这样构建起二叉树之后，我们可以发现，进行中序遍历的话只用从最左边的孩子开始，沿着每个结点的右指针一直遍历即可，可以不用递归了，真的不要太爽！（下图展示的是中序线索化）

线索化问题

有些小伙伴可能已经发现了问题，这样子创建的线索树该如何区分它的左右指针呢，我怎么知道它想指向的是左右孩子还是前驱后继呀。
所以这里我们就需要在结点结构体中多定义两个变量，用于表示它左右指针的类型，并且规定如下规则：
left_type 为 0 时，指向左孩子，为 1 时指向前驱。
right_type 为 0 时，指向右孩子，为 1 时指向后继。

typedef struct Thread {
    struct Thread* left_node;    //左指针
    struct Thread* right_node;    //右指针
    int data;
    //默认0代表左右孩子，1代表前驱或者后继
    int left_type;        //左指针类型
    int right_type;        //右指针类型
}Node;

增加定义之后，我们就可以开始对二叉树进行线索化啦，中序线索化是比较常见的，我会进行重点讲解，前序和后序的实现我也会加在后面一同实现。

二叉树的线索化

中序线索化

我们可以通过中序遍历的方式进行构建，这里需要一个指向前驱结点的指针和一个指向当前结点的指针。遍历的方式跟我们之前学的二叉树的中序遍历几乎一样，先来回顾一下二叉树的遍历：

//中序遍历
void show_tree(tree_node *node) {
    if (node == NULL)
        return;
    show_tree(node->left_child);
    cout << node->data << " ";    
    show_tree(node->right_child);
}

这里构建线索二叉树时，只需要改动上面代码中打印结点的那一部分，将那里改成对前驱后继连接的代码即可。
（1）先递归到最左边的孩子，我们线索化要做的就是处理各个结点的空指针即处理叶子结点，既然是中序遍历，先打印的肯定是最左边的孩子，所以要先找到它，并以它为起点开始线索化。
（2）处理叶子结点的左右指针，将左指针指向它的前驱，右指针指向它的后继。这里实现的方式是先定义一个全局的 pre 指针，在递归到最左孩子后，开始进行操作，将叶子结点的的左指针指向这个 pre ，在执行完指针操作后对 pre 进行更新，指向当前结点。另外，后继结点也要用到 pre ，但是对指针的操作则是在递归到最左孩子后的下一个结点再进行操作。（具体看下面代码会清楚很多）
（3）对右孩子进行同样的递归操作。

Node *pre;        //指向上一个结点
//中序线索化（递归）
void inOrderThreadTree(Node *node) {
    if (node == NULL) {
        return;
    }
    inOrderThreadTree(node->left_node);    //先遍历到最左边
    if (node->left_node == NULL) {
        //设置前驱结点
        node->left_type = 1;
        node->left_node = pre;
    }
    //如果结点的右子结点为NULL，则处理前驱的右指针
    if (pre != NULL && pre->right_node == NULL) {
        //设置后继
        pre->right_node = node;
        pre->right_type = 1;
    }
    pre = node;        //更新前驱指针
    inOrderThreadTree(node->right_node);    //在遍历右边孩子
}

//中序线索化（非递归-栈实现）
void inOrderThreadTreeStack(Node *node) {
    stack<Node *> s;
    pre = NULL;
    if (node == NULL) {
        return;
    }
    while (node || !s.empty()) {
        //一直将结点推入堆栈直至最左边的孩子
        while (node) {
            s.push(node);
            node = node->left_node;
        }
        node = s.top();    //找到最左孩子
        s.pop();    //弹出栈顶，使栈顶现在保存的是node的后继结点
        //设置前驱
        if (node->left_node == NULL) {
            node->left_type = 1;
            node->left_node = pre;
        }
        pre = node;
        //设置后继
        if (node->right_node == NULL && !s.empty()) {
            node->right_type = 1;
            node->right_node = s.top();
            node = NULL;    //防止死循环
        } else {
            node = node->right_node;    //往其右子树进行线索化
        }
    }
}

前序线索化

前序线索化和中序有所不同，是先 根结点 | 左子树 | 右子树 的结构，但是大致操作类似，只是将指针判断操作的那一块放在了递归左孩子之前。

//前序线索化
void prevOrderThreadTree(Node *node) {
    if (node == NULL) {
        return;
    }
    //设置前驱
    if (node->left_node == NULL) {
        node->left_type = 1;
        node->left_node = pre;
    }
    //设置后继
    if (pre != NULL && pre->right_node == NULL) {
        pre->right_type = 1;
        pre->right_node = node;
    }
    pre = node;
    //这里必须要判断类型，如果不判断，就会进入上面线索化的左指针，从而导致死循环
    if (node->left_type == 0)
        prevOrderThreadTree(node->left_node);
    if (node->right_type == 0)
        prevOrderThreadTree(node->right_node);
}

后序线索化

后序线索化更是大同小异，将指针判断操作放到最后即可，有没有一种和前中后序遍历的递归代码有点类似的感觉~

//后序线索化
void BackOrderThreadTree(Node *node) {
    if (node == NULL) {
        return;
    }
    prevOrderThreadTree(node->left_node);
    prevOrderThreadTree(node->right_node);
    //设置前驱
    if (node->left_node == NULL) {
        node->left_type = 1;
        node->left_node = pre;
    }
    //设置后继
    if (pre != NULL && pre->right_node == NULL) {
        pre->right_type = 1;
        pre->right_node = node;
    }
    pre = node;
}

线索二叉树的遍历

中序遍历

当构建其线索二叉树之后，我们每次遍历它就变得十分方便，不用不断的递归了，直接找到最左边的那个结点（中序遍历第一个打印的是最左边的孩子），然后沿着右指针进行输出。但是这里有一个地方需要注意，在输出完根结点左子树后，根结点的右孩子可能会有左子树，如果一直沿着右指针输出，会错过其右孩子的左子树，所以要加一个判断。

//中序遍历
void inOrderTraverse(Node *root) {
    //从根结点开始找到最左边
    if (root == NULL) {
        return;
    }
    Node *temp = root;
    while (temp != NULL && temp->left_type == 0) {
        temp = temp->left_node;    //找到最左边的结点
    }
    //开始打印结点
    while (temp != NULL) {
        cout << temp->data << " ";
        //如果该结点右指针没有线索化，要判断其右孩子有无左子树
        if (temp->right_node != NULL && temp->right_type == 0) {
            temp = temp->right_node;
            while (temp->left_node != NULL && temp->left_type == 0) {
                temp = temp->left_node;
            }
        } else
            temp = temp->right_node;
    }
    cout << endl;
}

前序遍历

前序遍历这里需要去判断根结点右孩子是否有左孩子，其实和中序遍历有点类似，都需要加一个额外的判断。

//前序遍历
void prevOrderTraverse(Node *root) {
    if (root == NULL)
        return;
    Node *temp = root;
    //这里要两层嵌套，因为你不清楚遍历完左边再遍历右边时，根结点的右孩子是否有左孩子
    //所以不能先像中序一样，先遍历完左孩子，再一条路往右走到黑
    while (temp != NULL) {
        //往左遍历的同时打印每个结点
        while (temp->left_type == 0) {
            cout << temp->data << " ";
            temp = temp->left_node;
        }
        if (temp != NULL)
            cout << temp->data << " ";
        temp = temp->right_node;
    }
    cout << endl;
}

全部代码

#include <bits/stdc++.h>
using namespace std;

typedef struct Thread {
    struct Thread *left_node;    //左指针
    struct Thread *right_node;    //右指针
    int data;
    //默认0代表左右孩子，1代表前驱或者后继
    int left_type = 0;        //左指针类型
    int right_type = 0;        //右指针类型
} Node;

Node *pre;        //指向上一个结点

//中序线索化（递归）
void inOrderThreadTree(Node *node) {
    if (node == NULL) {
        return;
    }
    inOrderThreadTree(node->left_node);    //先遍历到最左边
    if (node->left_node == NULL) {
        //设置前驱结点
        node->left_type = 1;
        node->left_node = pre;
    }
    //如果结点的右子结点为NULL，则处理前驱的右指针
    if (pre != NULL && pre->right_node == NULL) {
        //设置后继
        pre->right_node = node;
        pre->right_type = 1;
    }
    pre = node;        //更新前驱指针
    inOrderThreadTree(node->right_node);    //在遍历右边孩子
}

//中序线索化（非递归-栈实现）
void inOrderThreadTreeStack(Node *node) {
    stack<Node *> s;
    pre = NULL;
    if (node == NULL) {
        return;
    }
    while (node || !s.empty()) {
        //一直将结点推入堆栈直至最左边的孩子
        while (node) {
            s.push(node);
            node = node->left_node;
        }
        node = s.top();    //找到最左孩子
        s.pop();    //弹出栈顶，使栈顶现在保存的是node的后继结点
        //设置前驱
        if (node->left_node == NULL) {
            node->left_type = 1;
            node->left_node = pre;
        }
        pre = node;
        //设置后继
        if (node->right_node == NULL && !s.empty()) {
            node->right_type = 1;
            node->right_node = s.top();
            node = NULL;    //防止死循环
        } else {
            node = node->right_node;    //往其右子树进行线索化
        }
    }
}

//前序线索化
void prevOrderThreadTree(Node *node) {
    if (node == NULL) {
        return;
    }
    //设置前驱
    if (node->left_node == NULL) {
        node->left_type = 1;
        node->left_node = pre;
    }
    //设置后继
    if (pre != NULL && pre->right_node == NULL) {
        pre->right_type = 1;
        pre->right_node = node;
    }
    pre = node;
    //这里必须要判断类型，如果不判断，就会进入上面线索化的左指针，从而导致死循环
    if (node->left_type == 0)
        prevOrderThreadTree(node->left_node);
    if (node->right_type == 0)
        prevOrderThreadTree(node->right_node);
}

//后序线索化
void BackOrderThreadTree(Node *node) {
    if (node == NULL) {
        return;
    }
    prevOrderThreadTree(node->left_node);
    prevOrderThreadTree(node->right_node);
    //设置前驱
    if (node->left_node == NULL) {
        node->left_type = 1;
        node->left_node = pre;
    }
    //设置后继
    if (pre != NULL && pre->right_node == NULL) {
        pre->right_type = 1;
        pre->right_node = node;
    }
    pre = node;
}

//中序遍历
void inOrderTraverse(Node *root) {
    //从根结点开始找到最左边
    if (root == NULL) {
        return;
    }
    Node *temp = root;
    while (temp != NULL && temp->left_type == 0) {
        temp = temp->left_node;    //找到最左边的结点
    }
    //开始打印结点
    while (temp != NULL) {
        cout << temp->data << " ";
        //如果该结点右指针没有线索化，要判断其右孩子有无左子树
        if (temp->right_node != NULL && temp->right_type == 0) {
            temp = temp->right_node;
            while (temp->left_node != NULL && temp->left_type == 0) {
                temp = temp->left_node;
            }
        } else
            temp = temp->right_node;
    }
    cout << endl;
}

//前序遍历
void prevOrderTraverse(Node *root) {
    if (root == NULL)
        return;
    Node *temp = root;
    //这里要两层嵌套，因为你不清楚遍历完左边再遍历右边时，根结点的右孩子是否有左孩子
    //所以不能先像中序一样，先遍历完左孩子，再一条路往右走到黑
    while (temp != NULL) {
        //往左遍历的同时打印每个结点
        while (temp->left_type == 0) {
            cout << temp->data << " ";
            temp = temp->left_node;
        }
        if (temp != NULL)
            cout << temp->data << " ";
        temp = temp->right_node;
    }
    cout << endl;
}

//递归法构建二叉树
int n;
Node *creatTree(vector<int> nums, int index) {
    //判断是否为空
    if (nums[index] == '#')
        return NULL;

    //创建新结点
    Node *root = new Node;
    root->data = nums[index];

    //设置左右指针
    if (index * 2 < n) {
        root->left_node = creatTree(nums, index * 2);    //找到左孩子
    } else
        root->left_node = NULL;
    if (index * 2 + 1 < n)
        root->right_node = creatTree(nums, index * 2 + 1);    //找到右孩子
    else
        root->right_node = NULL;

    return root;
}

int main() {
    vector<int> nums = { '#', 1, 3, 2, 6, 7, 8, 9};    //从下标为1开始存储数据
    n = nums.size();
    //中序线索化（递归）
    pre = NULL;
    Node *root1 = creatTree(nums, 1);
    inOrderThreadTree(root1);
    cout << "中序线索化结果（递归）：";
    inOrderTraverse(root1);
    //中序线索化（非递归）
    pre = NULL;
    Node *root2 = creatTree(nums, 1);
    inOrderThreadTreeStack(root2);
    cout << "中序线索化结果（非递归）：";
    inOrderTraverse(root2);
    //前序线索化
    pre = NULL;
    Node *root3 = creatTree(nums, 1);
    prevOrderThreadTree(root3);
    cout << "前序线索化结果：";
    prevOrderTraverse(root3);
}

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~