线索二叉树详解

Posted on | In | Visitors:

概述

为了方便的找到二叉树指定节点在某种线性序列中的前趋和后继，一种解决方案是在二叉树中加入指向前趋/后继的指针，这就是线索二叉树。为了节约空间，可以添加两个标志位。ltag和rtag，如果ltag的值为1，则表示lchild指向前趋，如果其为0，表示lchild指向左孩子结点；rtag为1，则rchild指向后继，如果为0，rchild指向右孩子结点。

实现

中序线索二叉树的建立和遍历

在中序线索二叉树中，每一个前趋线索指示结点在中序下前一个访问的结点，每一个后继线索指示结点在中序下下一个访问的结点。如果前趋线索为空，该结点是中序下第一个访问的结点，如果后继线索为空，则该结点是中序下最后一个访问的结点。

1
2
3
4
5
6
7
8
9
//结点构造
#include<stdio.h>
#Include<stdlib.h>
typedef int TElemType;
typedef struct TRNode{
    int ltag,rtag;    //线索标志
    struct TRNode *lchild,*rchild;
    TElemType data;
}ThreadNode;

寻找指定节点*t为根的子树中第一个访问的结点

设中序线索二叉树的类型定义为
typedef ThreadNode *InThreadTree
以*p为根的中序线索二叉树中中序下的第一个结点是从*p出发，沿结点左孩子指针链走到底，直到某个结点的ltag=1为止，该结点是中序线索二叉树的中序第一个结点。

1
2
3
4
5
ThreadNode *inFirst(InThreadTree t){
    while(t->ltag == 0)
        t = t->lchild;
    return t;
}

寻找指定节点*t的中序后继

规则：

  1. 如果*t结点的rchild指向后继线索（rtag=1），则rchild直接指向它的后继。
  2. 如果*t结点的rchild指向右孩子（rtag=0），则后继为*t的右子树在中序下的第一个结点。
    1
    2
    3
    4
    5
    6
    ThreadNode *inNext(InTreadTree t){
        if(t->rtag == 1)
            return t->rchild;
        else
            return (inFirst(t->rchild));
    }

如果把inFirst中的ltag和lchild换成rtag和rchild，可得到中序序列下的最后一个访问的结点Last；如果把inNext中的rtag和rchild换成ltag和lchild，可得到指定节点的前驱Prior。

在中序线索二叉树上进行中序遍历

1
2
3
4
5
6
void Inorder(InTreadTree t){
    for(ThreadNode *p = inFirst(t);p!=NULL;p = inNext(p)){
        printf("%d ",p->data);
    }
    printf("\n");
}

通过中序遍历建立中序线索二叉树

需要设一个指针pre，它在遍历的过程中总是指向遍历指针p的中序下直接前驱结点，即在中序遍历下刚刚访问过的结点，初始时pre=NULL。在中序遍历中，只要一遇到空指针域就填入中序前驱或后继线索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef TreadNode *InTreadTree;
void InTreaded(ThreadNode *p,ThreadNode *&pre){
    if(p!=NULL){
        InThreaded(p->lchild,pre);    //递归，左子树线索化
        if(p->lchild == NULL){    //建立当前节点的前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!=NULL && pre->rchild == NULL){    //建立前驱结点的后继线索
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InTreaded(p->rchild,pre);
    }
}
void createInThread(InThreadTree t){
    ThreadNode *pre = NULL;
    if(t != NULL){
        InThreaded(t,pre);
        pre->rchild = NULL;    //处理最后一个结点
        pre->rtag = 1;
    }
}

先序和后序线索二叉树

先序和后序线索二叉树的建立过程与中序类似，唯一的不同之处在于加入前驱和后继线索的时机不同。

先序线索二叉树

对于指定节点*p，求其直接前趋的步骤为：

  1. 看*p是否有前趋线索（p->ltag = 1），如果有，直接返回p->lchild；否则执行2
  2. 找*p的双亲*q，如果*q不存在，则*p没有前趋；如果有双亲，执行3
  3. 判断p是不是q的左孩子，如果是左孩子或者*p是*q的右孩子且q没有左孩子，则\p的前驱为*q，否则，则执行4
  4. *p的前驱是*q的左子树中最后一个访问的结点。（此时的状态是*p是*q的右孩子，并且*q有左孩子）
    流程图：

    对于指定节点*p，求其先序序列下的直接后继的步骤为：
  5. 如果*p有左孩子，则该左孩子为其后继。
  6. 如果*p没有左孩子但有右孩子，则该右孩子为其后继。
  7. 如果*p既没有左孩子，也没有右孩子，判断p->rchild==NULL，如果等于NULL，则表明p是最后一个访问的节点，没有后继，如果不等于NULL，则p->rchild指向其直接后继。
    流程图：

后序线索二叉树

后序线索二叉树的查找前趋于后继的方法与中序和先序类似，不再赘述，流程图：

参考资料：
《数据结构——殷人昆》