二叉树（三）——线索二叉树

定义

对于具有n个结点的二叉树，二叉链表中空的指针域数目为 n+1，如下图：

注：n+1 的推导过程如下：2*n - (n-1) = n+1

利用二叉链表中空的指针域指出结点在某种遍历序列中的直接前驱或直接后继。指向前驱和后继的指针称为线索，加了线索的二叉树称为线索二叉树。

构造线索二叉树

利用链结点的空的左指针域存放该结点的直接前驱的地址，空的右指针域存放该结点直接后继的地址；而非空的指针域仍然存放结点的左孩子或右孩子的地址。

指针与线索的区分方法

法一：

法二：

不改变链结点的构造，而是在作为线索的地址前加一个负号,即“负地址”表示线索，“正地址”表示指针。

本文采用第一种方法。

线索二叉树链结点类型定义

C语言的线索二叉树链结点类型定义为：

typedef struct node {
    datatype data;
    struct node *lchild, *rchild;
    int lbit, rbit;
} TBTNode, *TBTREE;      

整体结构如下：

约定：序列中的头和尾的直接前驱和直接后继线索均指向头结点；

以中序序列为例，一颗完整的中序线索二叉树如下图：

中序序列为：D, B, J, E, A, H, F, I, C, G

线索二叉树的建立

线索二叉树建立的主旨思想为在遍历过程中建立线索，以下以中序序列为例，如下图：

中序序列为：B,D,A,E,C

建立如下指针：

prior: 指向前一次访问结点；

p: 指向当前访问结点；

则建立线索的规律如下：

1、若当前访问的结点的左指针域为空，则左指针域指向prior指的结点，同时置lbit为0，否则，置lbit为1；

2、若prior所指结点的右指针域为空，则右指针域指向当前访问的结点，同时置rbit为0，否则，置rbit为1；

3、遍历结束时，将prior->rchild指向头结点，并置prior->rbit为0。

基于上述规律，得到C语言的算法实现如下：

线索二叉树的应用

线索二叉树的主要应用：确定某一结点的直接前驱和直接后继。

以下，以在中序线索二叉树中确定地址为x的结点的直接后继为例。

算法规律如下：

1、当x->rbit=0时，x->rchild指出的结点就是x的直接后继结点；

2、当x->rbit=1时，沿着x的右子树的根的左子树方向查找，直到某结点的 lchild域为线索时（该结点的lbit=0），此结点就是x结点直接后继结点。

该算法的C语言实现如下：

TBTREE INSUCC(TBTREE x)
{
    TBTREE s;
    s=x->rchild;
    if(x->rbit==1)
        while (s->lbit==1)
            s=s->lchild;
    return(s);
}