线索二叉树

发表于   |   分类于

可以找到任意结点前驱或后继的二叉树.

一. 线索二叉树结构的设计

叶子结点的左右指针为空, 可以利用这里空链域记录它们前驱和后继结点, 如果 Ltag 或 Rtag 为 1, 说明左右指针指向的不是子树, 而是前驱和后继.

1
2
3
4
5
6
typedef struct bitree
{
    int Ltag, Rtag;
    bitree LChild, RChild;
    char data;
}BiTree;

二. 二叉树的线索化

分类: 先序线索二叉树, 中序线索二叉树, 后序线索二叉树
思想:

  • 类似于二叉树的遍历, 只不过在遍历的过程中, 对结点的访问改成: 修改结点为 NULL
    的指针域.
  • 需要有两个结点, pre(前一个结点) 和 root (当前结点)
  • ①如果当前遍历结点 root 的左子域为空，则让左子域指向 pre ；
    ②如果前驱 pre 的右子域为空，则让右子域指向当前遍历结点 root；
    ③为下次做准备，当前访问结点 root 作为下一个访问结点的前驱 pre。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //先序线索化二叉树
    void Inthread(BiTree root)
    {
        if(root!=NULL)    //当前结点存在
        {
            Inthread(root->LChild);    //线索化左子树
            if(root->LChild==NULL)    //如果当前结点的左子树为空, 当前结点的前驱为遍历过程中的前一个结点
            {
                root->Ltag = 1;
                root->LChild = pre;
            }
            if(pre!=NULL && pre->RChild==NULL)    //不知为何, 2017年11月19日 12:27:26
            {
                pre->RChild=root;
                pre->Rtag = 1;
            }
            pre = root;
            Inthread(root->RChild);
        }
    }

三. 线索二叉树结点前驱后继的查找

功能:给一个结点, 找到它的前驱和后继, 前提是二叉树已经被线索化.
根据先中后的不同, 查找方式也不相同, 这里只是中序线索二叉树的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//在中序线索二叉树中查找 p 的前驱, 并用 pre 指针返回结果
BiTree * InPre(BiTree * p)
{
    if(p->Ltag==1)
    {
        pre = p->LChild;
    }
    else    //Ltag 不为 1, 说明 p 的左子树一定不为空.
    {
        for(q=p->LChild; q->Rtag==0; q=q->Rtag);
        pre = q;
    }
    return pre;
}

//在中序线索二叉树中查找 p 的后继, 并用 pre 指针返回结果
BiTree * InNext(BiTree * p)
{
    if(p->Rtag==1)
    {
        pre = p->RChild;
    }
    else
    {
        if(p->RChild!=NULL)    //可能有右子树, 也可能没有右子树
        {
            for(q=p->RChild; q->Ltag==0; q=q->LChild);
                Next = q;
        }
        else
        {
            Next = NULL;
        }
    }
    return Next;
}

四. 遍历线索二叉树

功能: 取树中的一个结点, 找出它后面的结点.

这里只是以中序线索二叉树为例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//遍历中序线索二叉树
//第一步, 找出一棵二叉树中序遍历使的第一个结点
BiTree * InFirst(BiTree Bt)
{
    BiTree * p = Br;
    if(!p) return (NULL);
    while(p->Ltag==0)
    {
        p = p->LChild;
    }
    return p;
}
//第二步, 不断找出其后继结点
void TInOrder(BiTree Bt)
{
    BiTree * p;
    p = InFirst(Bt);
    while(p)
    {
        Visit(p);
        p = InNext(p);
    }
}

五. 总结

线索二叉树存储某个结点的前驱和后继, 可以做到: 取其中任意一个结点, 都可以遍历出它后面的结点. 如果是一般的二叉树, 只能从根完整地遍历一次.

操作有:

  • 线索化二叉树, 也就是把原本的空指针域用来指向前驱或后继结点. 有先序线索二叉树, 中序线索二叉树, 后序线索二叉树三种类型, 它们线索化的方式是不同的.
  • 查找某个结点的前驱或后继结点. 如果该结点的指针域是线索, 那么就可以马上找到前驱或后继结点. 否则, 需要通过规律来找到前驱或后继结点. 而三类线索树的规律又是不同的, 所以查找方式是不同的.

线索二叉树的缺点是: 太难了, 让我搞不懂. 三种序列索化二叉树的操作不同, 查找前驱和后继结点的操作也不同, 甚至这些操作可以用递归实现也可以用非递归实现…