《征服数据结构》二叉树前序线索化|spiderlinebreak|二叉树|左子|征服数据结构|指针|遍历

摘要：

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) {}
};