线索二叉树

n个节点的二叉链表，每个节点有指向左右孩子的两个指针域，所以一共有2n个指针域，n-1条分支线数。存在2n-(n-1)即n+1个空指针域，这些空间不做任何事情，白白浪费内存资源。

只有遍历一次之后才知道某个节点的前驱和后继，每次都需要遍历的话这是很大的时间浪费。

综合以上两个角度，我们可以利用这些空地址来存放指向节点在某种遍历次序下的前驱和后继节点的地址。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。

线索二叉树就是把一颗二叉树转变成一个双向链表，这样对我们的插入、删除、查找节点带来方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。

线索二叉树结构

二叉树线索存储结构定义如下：

typedef enum {Link, Thread} PointerTag;// 0：表示左、右孩子指针，1：表示前驱或后继的线索

typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;/* 左右孩子指针 */
    PointerTag LTag;/* 左标志 */
    PointerTag RTag;/* 右标志 */
} BiThrNode, *BiThrTree;

线索化的过程就是在遍历的过程中修改空指针的过程。代码如下所示：

BiThrTree pre;/* 全局变量，始终指向刚刚访问过的节点 */

void InThreading(BiThrTree p)
{
    if  (p)
    {
        InThreading(p->lchild);// 线索化左子树
        if  (!p->lchild)/* 当前节点没有左孩子 */
        {
            p->LTag = Thread;/* 前驱线索 */
            p->lchild = pre;/* 左孩子指针域指向前驱 */
        }
        if (!pre->rchild)/* 前驱没有右孩子 */
        {
            pre->RTag = Thread;/* 后继线索 */
            pre->rchild = p;/* 前驱右孩子指针域指向当前节点p */
        }
        pre = p;/* 访问过的节点开始移动 */
        InThreading(p->rchild);// 线索化右子树
    }
}

遍历线索二叉树等于是操作一个双向链表结构，给它添加一个头节点，这样我们既可以从第一个节点起顺后继遍历，也可以从最后一个节点起顺前驱遍历。代码如下：

Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild;
    while (p != T)
    {
        while (p->LTag == Link)
        {
            p = p->lchild;
        }
        printf("%c", p->data);
        while (p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild;
            printf("%c", p->data);
        }
        p = p->rchild;
    }
    return OK;
}