线索二叉树

问题导向

遍历二叉树是以一定的规则将二叉树中的节点排列成一个线性序列，得到二叉树中的先序、中序和后序序列。这实质上是将一个非线性结构进行线性化操作，是每一个节点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前驱和直接后继。
但是，当以二叉链表作为存储结构时，只能找到节点的左、右孩子信息，而不能直接得到在任一序列中的前驱和后继信息，这种信息只有在遍历的动态的过程中才能得到。

解决方案

如何保存这种在遍历过程中得到的信息呢？
一种直接的办法就是在每个节点再增加两个指针，分别指向节点在任一次序遍历中得到的前驱和后继信息，但这样大量指针会使存储密度降低；
另一种办法就是在现有存储结构上做文章，对二叉链表结构分析发现，n 个节点的二叉链表中必然存在 n+1 个空连域，显然可以用这些空链域来存储前驱和后继信息。

n 个节点共有 2n 个链域，n-1 条连接双亲和孩子的边，故剩余 n-1 个空链域

于是，对树节点的左右孩子指针做如下规定：
如果节点有左孩子，则其 lchild 指向其左孩子，否则令其指向其前驱节点；
如果节点有右孩子，则其 rchild 指向其右孩子，否则令其指向其后继节点；

为了区分这两种指向，再增加两个标志位，用以标识区分，于是新的二叉树节点定义更新为：

typedef enum {Link, Thread} PointerTag;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag ltag, rtag;
}BiThrNode, *BiThrTree;

其中：

$$ltag =
\begin{cases}
0& \text{lchild 指向节点的左孩子}\\
1& \text{lchild 指向节点的前驱}
\end{cases}$$

$$rtag =
\begin{cases}
0& \text{rchild 指向节点的右孩子}\\
1& \text{rchild 指向节点的后继}
\end{cases}$$

以这种节点结构构成的二叉链表称为线索链表，其中指向前驱和后继的指针称为线索，加上线索的二叉树称为线索二叉树。
以某种次序遍历二叉树时将其变为线索二叉树（添加线索指向）的过程称为线索化，具体实施就是将遍历过程中的访问节点信息的操作变更为建立线索的操作。

先序线索及遍历

先序线索树遍历：
先序线索树中，所有叶子节点的的左、右链均为线索，则其左、右（孩子）链域分别直接指示了节点的前驱和后继；
所有非终端节点最多只有一个链为线索，于是就无法直接获取前驱或信息，不过根据遍历的规律仍可以找到前驱或后继。

(1) 寻找前驱：
如果节点左链标识为线索(Thread)，则其左链的直接线索指向就是前驱；
否则有如下三种情形：
(Ⅰ) 节点是二叉树的根，则其前驱为空；
(Ⅱ) 节点是其双亲的左孩子或者是其双亲的右孩子且其双亲没有左子树，则其前驱为其双亲；
(Ⅲ) 节点是其双亲的右孩子且其双亲有左子树，则其后继为双亲左子树上按先序遍历最后一个节点（双亲左子树最底层的最后一个节点）。

可见，在先序线索树上找前驱时需要继续知道双亲，于是仍需要辅助栈参与或者使用带标志域的三叉链表（有指向双亲的指针）。

(2) 寻找后继：
如果节点右链标识为线索(Thread)，则其右链的直接线索指向就是后继；
否则有如下两种情形：
(Ⅰ) 节点有左孩子，则其后继为左孩子；
(Ⅱ) 节点没有左孩子但有右孩子，则其后继为右孩子；

可见，在先序线索树非递归遍历时（通过后继正序），其时间复杂度不变，但是常数因子比二叉树遍历小；其空间复杂度减小，不再需要辅助栈参与。

应用场景：
所用二叉树需要经常遍历或者查找遍历序列中的后继时，宜采用线索链表结构。

中序线索及遍历

中序线索化：中序遍历时将节点的线索分别前驱和后继，故需要一个额外指针 pre 用于上一个访问的节点，以便于进行线索化。

需要注意的是，递归进入子树时，节点的标识是 Link，必要情况下需要先判断，例如先序递归建立线索时，如果不加判断，遍历时可能会把 Thread 当作 Link 递归，从而变成死循环。

// pre 指针指向前一个访问的节点，以便于建立线索
Status InThreading_Recursion(BiThrTree T, BiThrTree *pre)
{
    if (T)
    {
        InThreading_Recursion(T->lchild, pre);
        // 建立当前节点的前驱
        if (T->lchild == NULL)
        {
            T->ltag = Thread;
            T->lchild = (*pre);
        }
        // 建立前驱节点的后继
        if ((*pre)->rchild == NULL)
        {
            (*pre)->rtag = Thread;
            (*pre)->rchild = T;
        }
        // 移动 pre 指针
        (*pre) = T;
        InThreading_Recursion(T->rchild, pre);
    }
    return 0;
}

中序线索树遍历：
中序线索树中，所有叶子节点的的左、右链均为线索，则其左、右（孩子）链域分别直接指示了节点的前驱和后继；
所有非终端节点最多只有一个链为线索，于是就无法直接获取前驱或信息，不过根据遍历的规律仍可以找到前驱或后继。

(1) 寻找前驱：
如果节点左链标识为线索(Thread)，则其左链的直接线索指向就是前驱；
如果节点左链标识为指针(Link)，则其左子树最右下的节点即为前驱（遍历左子树时最后访问的节点）。

(2) 寻找后继：
如果节点右链标识为线索(Thread)，则其右链的直接线索指向就是后继；
如果节点右链标识为指针(Link)，则其右子树最左下的节点即为后继（遍历右子树时最先访问的节点）。

显然，在中序线索树非递归遍历时，其时间复杂度不变，但是常数因子比二叉树遍历小；其空间复杂度减小，不再需要辅助栈参与（正序和逆序都不需要）。

应用场景：
所用二叉树需要经常遍历或者查找遍历序列中的前驱和后继时，宜采用线索链表结构。

后序线索及遍历

后序线索树遍历：
后序线索树中，所有叶子节点的的左、右链均为线索，则其左、右（孩子）链域分别直接指示了节点的前驱和后继；
所有非终端节点最多只有一个链为线索，于是就无法直接获取前驱或信息，不过根据遍历的规律仍可以找到前驱或后继。

(1) 寻找前驱：
如果节点左链标识为线索(Thread)，则其左链的直接线索指向就是前驱；
否则有如下两种情形：
(Ⅰ) 节点有右孩子，则其前驱为右孩子；
(Ⅱ) 节点没有右孩子但有左孩子，则其前驱为左孩子；

可见，在后序线索树逆向非递归遍历时（通过前驱正序），其时间复杂度不变，但是常数因子比二叉树遍历小；其空间复杂度减小，不再需要辅助栈参与。

(2) 寻找后继：
如果节点右链标识为线索(Thread)，则其右链的直接线索指向就是后继；
否则有如下三种情形：
(Ⅰ) 节点是二叉树的根，则其后继为空；
(Ⅱ) 节点是其双亲的右孩子或者是其双亲的左孩子且其双亲没有右子树，则其后继为其双亲；
(Ⅲ) 节点是其双亲的左孩子且其双亲有右子树，则其后继为双亲右子树上按后序遍历第一个节点（双亲右子树最底层的第一个节点）。

可见，在后序线索树上找后继时需要继续知道双亲，于是仍需要辅助栈参与或者使用带标志域的三叉链表（有指向双亲的指针）。

应用场景：
所用二叉树需要经常遍历或者查找遍历序列中的前驱时，宜采用线索链表结构。

三种线索树归纳总结

先序线索二叉树有效解决了寻找后继的问题（正向先序遍历），但是寻找前驱仍需要辅助栈的参与，或者使用带标记的三叉链表；

后序线索二叉树有效解决了寻找前驱的问题（逆向后序遍历），但是寻找后继仍需要辅助栈的参与，或者使用带标记的三叉链表；

只有中序线索二叉树在遍历以及寻找前驱和后继时，都不再需要辅助栈的参与。

原因在于本身的遍历规则：

先序：根左右；中序：左根右；后续：左右根

兄弟节点之间没有连接，在二叉链表中，根节点是连接一对兄弟节点唯一的桥梁；
对于先序遍历，根节点在最左侧，节点前驱要么是双亲，要么是双亲左子树中的节点，因此需要通过双亲到达左侧；
对于后序遍历，根节点在最右侧，节点后继要么是双亲，要么是双亲右子树中的节点，因此需要通过双亲到达右侧；
而中序遍历，根节点在中间，节点前驱无线索时，肯定在其左子树中；节点后继无线索时，肯定在其右子树中；