线索二叉树的理解与实现

发表于 更新于 分类于 ，
本文字数： 3.6k

线索二叉树 —— 利用二叉树二叉链结构中的空链域，储存某种遍历次序下每个带空链域的结点的前驱（后继）结点的指针

数据结构课代码实现 之 中序线索二叉树

简要理解：

设p为二叉树中的一个结点

  1. 若 p->lchild 为空 则储存中序遍历序列中 p 的前驱结点
  2. 若 p->rchild 为空 则储存中序遍历序列中 p 的后继结点

那么在遍历二叉树线索化时需要一个标记来指明结点的 lchild 与 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
#include <iostream>
#include <cstring>
#include <cstdlib>

#define OK 1
#define OVERFLOW -2
#define ERROR -1

typedef enum{Link, Thread} PointerTag; //枚举类型

typedef struct BiThrNode // 线索二叉树比普通树多两个标记
{
    char data;
    struct BiThrNode *lchild, *rchild;   
    PointerTag ltag; 
    PointerTag rtag; // 用来标记每个结点的*lchild, *rchild指向的是 线索指针 还是 孩子指针
}BiThrNode, *BiThrTree;

BiThrTree pre; // 很关键的一个指针 用于线索化时储存上一个结点

bool visit(char x)
{
    cout << x << " "; //visit函数
    return true;
}

先序遍历递归建立二叉树

这里踩了个坑，一开始忘记把所有结点的 ltag 和 rtag 全部初始化为 Link，这会导致后面的 InOrderThreading 过程中产生错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int CreateBiThrTree(BiThrTree &T)
{
    char ch;
    cin >> ch; 
    if(ch == '#') T = NULL; // 输入 # 号将当前结点设置为NULL
    else
    {
        if(!(T = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
        T->data = ch;
        T->ltag = Link;
        T->rtag = Link;
        CreateBiThrTree(T->lchild);
        CreateBiThrTree(T->rchild);
    }
    return OK;
}

线索化过程

线索化的过程就是将中序遍历的过程中的访问操作改为线索化过程

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
37
38
39
40
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;   //下文解释此处为何对pre指针进行操作
        }
        pre = p;
        InThreading(p->rchild);
    }
}

// 中序遍历顺序相同 读取数据操作变为线索化过程

int InOrderThreading(BiThrTree &Thrt,BiThrTree T) // 此处新创建一个线索树
{
    if(!(Thrt = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
    Thrt->ltag = Link;       //创建 Thrt 的头结点
    Thrt->rtag = Thread;     //书上将 Thrt 的头结点的 ltag 设置为 Link, ltag 设置为 Link
    Thrt->rchild = Thrt;     //将 Thrt 头结点的 rchild 指向自己
    if(!T) Thrt->lchild = Thrt; //如果 T 为空，则将 Thrt 头结点的 lchild 指向自己
    else
    {
        Thrt->lchild = T;
        pre = Thrt;
        InThreading(T);      //此时 pre指针 指向了 T 中序遍历的最后一个结点
        pre->rchild = Thrt;  //将最后一个结点的后继指针指向 Thrt 的头结点 
        pre->rtag = Thread;  //更改最后一个结点 rchild 的类型
        Thrt->rchild = pre;	 //将 Thrt 的 rchild 指向最后一个结点 在倒中序遍历时有用
    }
    return OK;
}

在 InThreading 中,遍历时，无法确认当前结点的后继结点，但是可以确定 pre结点 的后继结点(也就是当前结点)

在 InOrderThreading 中对 Thrt 的头结点 ltag 与 rtag 的设置貌似并没有多大意义，在这个程序中使用线索非递归化遍历时并没有检查这两个标记，也许在其他地方有用…

中序非递归化遍历线索二叉树

正向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int InOrderTraverse_Thr(BiThrTree T,bool (* visit)(char x))
{
    BiThrTree p = T->lchild;  //指向二叉树的根结点
    while(p != T)             //循环检测是否遍历结束 (最后一个结点的后继结点指向 T)
    {
        while(p->ltag == Link) 
        	p = p->lchild;    //循环直至到中序遍历的第一个结点
		if(!visit(p->data)) return ERROR;
        while(p->rtag == Thread && p->rchild != T)
        {
            p = p->rchild;    //通过后继结点遍历
            visit(p->data);
        }
        p = p->rchild;		  //指向 p结点 的右孩子 (因为此时 p结点 的 rtag 为 Link)
    }
    return OK;
}

反向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int reInOrderTraverse_Thr(BiThrTree T,bool (* visit)(char x))
{
    BiThrTree p = T->rchild;   //指向二叉树的根结点
    while(p != T)              //循环检测是否遍历结束 (第一个结点的前驱结点指向 T)
    {
        while(p->rtag == Link) 
            p = p->rchild;     //循环直至到中序遍历的最后一个结点
        if(!visit(p->data)) return ERROR;
        while(p->ltag == Thread && p->lchild != T)
        {
            p = p->lchild;     //通过前驱结点遍历
            visit(p->data); 
        }
        p = p->lchild;         //同理还是指向 p结点 的左孩子
    }
    return OK;
}

这里还是比较好理解的

递归化遍历方法

为了验证，写一下递归化的遍历方法

1
2
3
4
5
6
7
8
void ooInThreading(BiThrTree p)
{
    if(p == NULL)
        return;
    ooInThreading(p->lchild);
    visit(p->data);
    ooInThreading(p->rchild);
}

main函数

给出一组数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    BiThrTree Tre,Thre;
    CreateBiThrTree(Tre);
    ooInThreading(Tre);
    cout << endl;
    InOrderThreading(Thre, Tre);
    InOrderTraverse_Thr(Thre, visit);
    cout << endl;
    reInOrderTraverse_Thr(Thre, visit);
    return 0;
}
/* 输入： ABPL####CM##NO### */
/* 输出：L P B A M C O N 递归化
        L P B A M C O N 非递归线索化
        N O C M A B P L 反向非递归线索化 */