一、定义和数据结构

1. 定义

结点结构中含有线索的的二叉树称为线索二叉树。
若结点有左子树，则其 lchild 域指示其左子，否则令 lchild 域指示其前驱；若结点有右子树，则其 rchild 域指示其右子，否则令 rchild 域指示其后继。
为了避免混淆，需要增加两个标志域 LTag 和 RTag，标志域为 0 表示结点后接指针，标志位为 1 表示结点后接线索。

2. 数据结构

typedef struct BiThrNode
{
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

其中，PointerTag 的定义为

typedef enum PointerTag
{
    Link,
    Thread
} PointerTag;

Link == 0 表示指针，Thread == 1 表示线索。

二、线索化

线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只能在遍历时得到，所以线索化的过程即为在遍历过程中修改空指针的过程。所以为了记录遍历过程中访问结点的先后关系，附设一个指针 pre 始终指向刚刚访问过的结点，即若指针 p 指向当前访问的结点，则 pre 指向它的刚访问过的结点。

void InThreading(BiThrTree p, BiThrTree *pre)
{
    if (p)
    {
        // 左子树线索化.
        InThreading(p->lchild, pre);

        // 前驱线索.
        // 若当前结点无左子，则修改标志域并使得 lchild 指向 p 的前驱.
        if (!(p->lchild))
        {
            p->LTag = Thread;
            p->lchild = (*pre);
        }

        // 后继线索.
        if (!((*pre)->rchild))
        {
            (*pre)->RTag = Thread;

            // 将前驱结点的后继结点设置为当前结点.
            (*pre)->rchild = p;
        }

        // 更新 pre, 使其始终指向刚访问过的结点.
        (*pre) = p;

        // 右子树线索化.
        InThreading(p->rchild ,pre);
    }

    return;
} // InThreading

我这里在学习的时候遇到一个问题：刚访问过的结点 pre 的后继线索设置失败。书中的伪代码未说明 pre 是否为全局变量，而数据结构中也没有存储 pre，所以我先将 pre 作为一个局部变量定义并值传递给了 InThreading，乍一看没什么问题，但是仔细 debug 之后发现，在调用这个递归形式的算法时，系统会维护一个函数调用栈，每进入一层新的递归，系统就会保存当前调用的返回地址，并压入新的调用的返回地址。在执行完子函数后，子函数的返回地址会被弹出栈，此时，之前做的一切修改就都不见了，pre 也不会得到更新。

改进方法有两个：

将 pre 设置为全局变量；
将值传递改为指针传递。

本文采用了第二种方法。

三、遍历

线索化之后，可以很方便地得到结点在遍历所得线性序列中的前驱和后继，也可以很方便地得到线性序列。

Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType e))
{
    // p 指向根结点.
    BiThrNode *p = T->lchild;

    // 空树或遍历结束时.
    while (p != T)
    {
        while (p->LTag != Thread)
        {
            p = p->lchild;
        }

        if (!Visit(p->data))
        {
            return ERROR;
        }

        // 访问后继结点.
        // 找到最左叶结点, 就可以轻松地访问其后继结点.
        while ((p->RTag == Thread) && (p->rchild != T))
        {
            p = p->rchild;
            Visit(p->data);
        }

        p = p->rchild;
    }

    return OK;
} // InOrderTraverse_Thr

笔记本子

线索二叉树的线索化及遍历