5.4 线索二叉树

利用 n+1 个空指针记录前驱与后继——中序、先序、后序线索化，以及在线索树中寻找前驱和后继。

为什么需要线索

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含 $n$ 个结点的二叉树中，有 $n + 1$ 个空指针。能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

结点结构

规定：若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点。还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）。

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;                  // 左、右线索标志
} ThreadNode, *ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。

线索化的过程

对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。中序线索化的思路：附设指针 pre 指向刚刚访问过的结点，指针 p 指向正在访问的结点，即 pre 指向 p 的前驱。在中序遍历的过程中，检查 p 的左指针是否为空，若为空就将它指向 pre；检查 pre 的右指针是否为空，若为空就将它指向 p。

1void InThread(ThreadTree p, ThreadTree &pre) {
2    if (p != NULL) {
3        InThread(p->lchild, pre);      // 线索化左子树
4        if (p->lchild == NULL) {       // 左子树为空，建立前驱线索
5            p->lchild = pre;
6            p->ltag = 1;
7        }
8        if (pre != NULL && pre->rchild == NULL) {
9            pre->rchild = p;           // 建立前驱结点的后继线索
10            pre->rtag = 1;
11        }
12        pre = p;                       // 标记当前结点成为刚刚访问过的结点
13        InThread(p->rchild, pre);      // 线索化右子树
14    }
15}
16void CreateInThread(ThreadTree T) {
17    ThreadTree pre = NULL;
18    if (T != NULL) {
19        InThread(T, pre);
20        pre->rchild = NULL;            // 处理遍历的最后一个结点
21        pre->rtag = 1;
22    }
23}

在线索树中找后继与前驱

中序线索二叉树

找结点 p 的后继：

• 若 p->rtag == 1，则 p->rchild 就是后继；
• 否则，后继为 p 的右子树中最左下的结点。

找结点 p 的前驱：

• 若 p->ltag == 1，则 p->lchild 就是前驱；
• 否则，前驱为 p 的左子树中最右下的结点。

ThreadNode *Firstnode(ThreadNode *p) {      // 中序序列下的第一个结点
    while (p->ltag == 0) p = p->lchild;    // 最左下结点（不一定是叶结点）
    return p;
}
ThreadNode *Nextnode(ThreadNode *p) {       // 中序序列中 p 的后继
    if (p->rtag == 0) return Firstnode(p->rchild);
    else return p->rchild;                 // rtag == 1 直接返回后继线索
}
void Inorder(ThreadNode *T) {               // 不含头结点的中序线索树的中序遍历
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
        visit(p);
}

利用线索，中序遍历无须借助栈，空间复杂度 $O(1)$。

先序与后序线索二叉树

先序后继：若 p 有左孩子，则左孩子是后继；若 p 无左孩子但有右孩子，则右孩子是后继；若 p 为叶结点，则右链域直接指示了结点的后继。

后序后继分三种情况：① 若 x 是二叉树的根，则其后继为空；② 若 x 是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲；③ 若 x 是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

即时练习