线索二叉树

二叉链表是一种单向链接结构，从一个结点出发，沿着指针走向只能到达其子孙结点，却无法返回其祖先结点。由于具有 n 个结点的二叉树有 n + 1 个空指针域，利用二叉链表的空指针域来存放遍历后结点的前驱和后继信息，这就是线索二叉树构成的思想。

后继线索和前驱线索的用途实际上是不一样的。对于后继线索，其是为了在正序遍历时，搭配算法一起遍历；前驱线索则是为了逆序遍历，并不是说只利用前驱和后继线索进行正序遍历。

存储方式

线索二叉树的结点结构包含两个标志域：

ltag, rtag 为两个标志域
ltag = 0：lch 域指示结点的左孩子
ltag = 1：lch 域指示结点的前驱
rtag = 0：rch 域指示结点的右孩子
rtag = 1：rch 域指示结点的后继

线索化与遍历

1. 生成头节点方法

要求在中序遍历下的第一个结点的前驱线索和最后一个结点的后继线索均指向头结点。

对于头节点本身有下面两种初始化方法：

当二叉树不为空时：

head → lch = T（二叉树的根）
head → rch = head
head → ltag = 0
head → rtag = 0

当二叉树为空时：

head → lch = head
head → rch = head
head → ltag = 1
head → rtag = 0

第二种方法：

head → lch 指向根结点
head → rch 指向中序最后一个结点
head → ltag = 0
head → rtag = 1

2. 线索化

简单来说，需要按照中序遍历的顺序建立线索，如果没有左孩子，则在左孩子处存储前驱，如果没有右孩子，则在右孩子处存储后继。

首先要清楚我们要做的是中序线索，因此要进行一次中序遍历，即线索化左节点，对当前结点操作，线索化右节点。

对于当前节点进行操作需要通过维护一个 pre 指针进行。当前结点指针为 p，只要 pre 存在且 pre 的右节点是空的，则 pre 的后继为 p；只要 p 的左节点是空的，p 的前驱为 pre。接下来将 pre 更新到 p，p 正常进行中序更新即可。

3. 查找中序前驱方法

当结点没有左子树时，即 p → ltag = 1 时，p → lch 即为所求前驱结点（线索）。
当结点有左子树时，即 p → ltag = 0 时，p 的前驱结点为 p 的左子树的最右下结点。

4. 查找中序后继方法

当结点没有右子树时，即 p → rtag = 1 时，p → rch 即为所求后继结点（线索）。
当结点有右子树时，即 p → rtag = 0 时，p 的后继结点为 p 的右子树的最左下结点。

5. 遍历

中序遍历线索二叉树的递归算法：

void TraverseInthread(threadbithptr *p)
{
    if (p ![[= NULL) {
        while (p->ltag == 0)         // 找中序序列的开始结点
            p = p->lch;
        do {
            Visit(p->data);
            p = Next(p);             // 找 p 的中序后继结点
        } while (p != NULL);
    }
}