数据结构之线索二叉树详细解释

1.1 线索二叉树的原理

我们现在倡导节约型社会，一切都应该以节约为本。但当我们创建二叉树时我们会发现其中一共有两个指针域，有的指针域指向的结构为空，这也就浪费了很多空间。所以为了不去浪费这些空间我们采取了一个措施。就是利用那些空地址，存放指向结点在某种遍历次序之下的前驱和后继结点的地址。就好像GPS导航仪一样，它可以告诉我们下一站是哪里，我们是从那里来的。我们把这种指向前驱和后继的指针成为线索，加上线索的二叉链表称为线索链表，相应的二叉树就成为线索二叉树。

我们将对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

下图是线索化结束的图：

这里存在一个问题，我们怎么知道某一个结点的lchild是指向它的左孩子还是它的前驱呢？rchild是指向其右孩子还是指向后继结点呢？可以在结构体中多两个变量用来去判断是指向前驱后继还是左孩子右孩子。

1.2 线索二叉树结构的实现

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

struct Tree
{
    char name[28];        //需要存储的数据 
    int num;
    int L;        //左右的标志
    int R;
    struct Tree *lchild,*rchild;    //左右孩子的指针
};

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树的时候才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数如下：

struct Tree *pre = NULL;    //全局变量 

void Inthreading(struct  Tree  *p)
{
    Inthreading(p->lchild);    //递归左子树线索化

    if(!p->lchild)            //没有左孩子
    {
        p->L = 1;
        p->lchild = pre;    //本来指向左孩子的指针指向前驱结点 
    }

    if(!pre->rchild)        //没有右孩子
    {
        pre->R = 1;
        pre->rchild = p;    //本来指向右孩子的指针指向后继结点 
    }

    pre = p;    //保持pre指向p的前驱

    Inthreading(p->rchild);    //递归右子树线索化
}

你会发现，代码中除了if语句以外，和二叉树中序遍历的递归代码几乎一模一样。只不过是将打印的代码改为了线索化功能的代码。

if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过（如果是第一个元素则前驱指向NULL），赋值给了 pre，所以可以将pre赋值给p->lchild,并修改p->L为1，以完成前驱结点的线索化。

后继结点的线索化就会麻烦一点。因为此时p结点的后继结点还没有被访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就为pre的后继结点，于是就让pre->rchild = p，并设置pre->R为1，以完成后继结点的线索化。

结果如下图所示：

结构体中有一个标志（L和R）该指针域是否指向其左孩子还是右孩子的结点，若指向左孩子或右孩子则该值为0，若指向前驱或后继时则该值为1。

遍历的代码如下：

void print(struct Tree *T)
{
    struct Tree *p;
    p = T->lchid;    //p指向根结点

    while(p!=T)    //当p是空树，或等于T时结束循环
    {
        while(p->L == 0)
            p = p->lchild;
           cout << name <<" " << num << endl;
        while(p->R == 1 && p->rchild != T)
        {
            p = p->rchild;    //访问后续结点
            cout << name <<" " << num << endl;
        }
        p = p->rchild;
    }
}

大致运行的过程如下：