Fz's Blog
Fz's Blog

线索化二叉树

房子 房子 收录于 考研408
  约 2700 字 预计阅读 6 分钟 - 次阅读   - 条评论  

线索二叉树的三种构造方法

中序线索二叉树的构造

摘要

在二叉树中有N个节点,共有2N个指针域,而只有N-1条边, 所以还有

2N-(N-1)=N+1个空闲指针域

既然这些指针本来是空的，不如用它们存储遍历时的前驱和后继。

这里的前驱、后继指的是： 在某种遍历序列中，某个结点的前一个结点和后一个结点。

总结

把二叉树中的空指针改造成“线索”，用来指向某种遍历序列中的前驱或后继，从而提高空指针利用率，并>且方便非递归、无栈地遍历二叉树。

代码实现 

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

typedef struct ThreadNode
{
    int data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;//定义标志位用于区分是前驱(后继)节点还是普通左(右)孩子节点
}ThreadNode,*ThreadTree;

ThreadNode *pre = NULL;//全局变量前驱节点,定义在全局不用考虑引用传递

//线索化的主要逻辑
void visit(ThreadTree q)
{
    if(q->lchild == NULL)//左子树为空
    {
        q->lchild = pre;//前驱设为pre
        q->ltag = 1;
    }
    if(pre != NULL && pre->rchild == NULL)//前驱节点不为空且前驱右孩子为空,说明此时pre为一个具体的节点
    {
        pre->rchild = q;//后继设为q
        pre->rtag = 1;
    }
    pre = q;//更新pre
}
//中序遍历二叉树改造成中序线索化二叉树
void InThread(ThreadTree T)
{
    if(T!=NULL)
    {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

//前序遍历二叉树改造成前序线索化二叉树
void PreThread(ThreadTree T)
{
    if(T!=NULL)
    {
        visit(T);
        if(T->ltag == 0)PreThread(T->lchild);
        if(T->rtag == 0)PreThread(T->rchild);//注意判断左右孩子不是前驱和后继节点,否则导致循环
    }
}

//后序遍历二叉树改造成后序线索化二叉树
void PosThread(ThreadTree T)
{
    if(T!=NULL)
    {
        PosThread(T->lchild);
        PosThread(T->rchild);
        visit(T);
    }
}
void CreateThreadTree(ThreadTree T)
{
    pre = NULL;
    if(T != NULL)
    {
        InThread(T);
        //PosThread(T);后序线索二叉树
        //PreThread(T);前序线索二叉树
        if(pre->rchild == NULL)
        {
            pre->rtag = 1;//处理遍历的最后一个节点
        }
    }
}

细节总结

信息

普通二叉树中的空指针可以这样利用：

原来的空指针 在线索二叉树中的作用
空的左指针 指向遍历前驱
空的右指针 指向遍历后继

因此，在线索二叉树中，需要增加两个标志位：

1
2

ltag;
rtag;

它们的含义如下：

标志位 值 含义
ltag 0 lchild 指向左孩子
ltag 1 lchild 指向前驱线索
rtag 0 rchild 指向右孩子
rtag 1 rchild 指向后继线索

1.中序线索二叉树的构造的代码实现

结点结构定义 

1
2
3
4
5
6

typedef struct ThreadNode
{
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;   // 标志位：区分孩子指针和线索指针
} ThreadNode, *ThreadTree;
全局变量 pre
1

ThreadNode *pre = NULL;

pre 用来记录当前访问结点的前驱结点。

在线索化过程中，我们需要知道两个关系：

  • 当前结点 q 的前驱是谁？
  • 前一个结点 pre 的后继是谁？

所以使用 pre 保存刚刚访问过的结点。

线索化核心逻辑 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void visit(ThreadTree q)
{
    // 如果当前结点没有左孩子，则建立前驱线索
    if(q->lchild == NULL)
    {
        q->lchild = pre;
        q->ltag = 1;
    }

    // 如果前驱结点存在，并且前驱结点没有右孩子，则建立后继线索
    if(pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;
        pre->rtag = 1;
    }

    // 更新 pre，使当前结点成为下一个结点的前驱
    pre = q;
}

这段代码主要完成两件事：

操作 含义
q->lchild = pre 当前结点的左线索指向前驱
pre->rchild = q 前驱结点的右线索指向当前结点
最后：
1

pre = q;

表示当前结点访问结束，当前结点会成为下一个被访问结点的前驱。

中序遍历顺序为：

1

左子树 → 根结点 → 右子树

所以中序线索化代码如下：

1
2
3
4
5
6
7
8
9

void InThread(ThreadTree T)
{
    if(T != NULL)
    {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

2.前序线索化二叉树的代码实现

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void PreThread(ThreadTree T)
{
    if(T != NULL)
    {
        visit(T);

        if(T->ltag == 0)
            PreThread(T->lchild);

        if(T->rtag == 0)
            PreThread(T->rchild);
    }
}
这里需要注意：
1

if(T->ltag == 0)

和：

1

if(T->rtag == 0)

这两个判断是为了防止把线索当成孩子继续递归。

因为在线索化过程中，原来的空指针可能已经被改成了前驱或后继线索。

如果不判断，就可能造成重复访问，甚至死循环。

3. 后序线索化二叉树的代码实现

代码如下：

1
2
3
4
5
6
7
8
9

void PosThread(ThreadTree T)
{
    if(T != NULL)
    {
        PosThread(T->lchild);
        PosThread(T->rchild);
        visit(T);
    }
}

后序线索化的构造思想和中序、前序类似，都是在对应的遍历顺序中调用 visit()。

但是需要注意：

后序线索二叉树的构造并不难，但后序线索二叉树的遍历通常比较复杂，因为寻找后继时往往需要父结点 信息。

因此，在数据结构学习和考试中，最常重点掌握的是中序线索二叉树。

4. 创建线索树 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void CreateThreadTree(ThreadTree T)
{
    pre = NULL;

    if(T != NULL)
    {
        InThread(T);

        // 处理遍历序列中的最后一个结点
        if(pre->rchild == NULL)
        {
            pre->rtag = 1;
        }
    }
}
这段代码中：
1

pre = NULL;

表示线索化开始前，当前结点没有前驱。

中序线索化结束后，pre 指向遍历序列中的最后一个结点。

最后一个结点没有后继，所以需要处理：

1
2
3
4
5

if(pre->rchild == NULL)
{
   pre->rchild = NULL;
   pre->rtag = 1;
}

它表示：

1

最后一个结点的右指针是后继线索，但后继为空。

完整代码 

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include <stdio.h>

typedef struct ThreadNode
{
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;   // 标志位：区分孩子指针和线索指针
} ThreadNode, *ThreadTree;

ThreadNode *pre = NULL; // 全局变量，记录当前访问结点的前驱结点

// 线索化的核心逻辑
void visit(ThreadTree q)
{
    // 如果当前结点没有左孩子，则建立前驱线索
    if(q->lchild == NULL)
    {
        q->lchild = pre;
        q->ltag = 1;
    }

    // 如果前驱结点存在，并且前驱结点没有右孩子，则建立后继线索
    if(pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;
        pre->rtag = 1;
    }

    // 更新 pre，使当前结点成为下一个结点的前驱
    pre = q;
}

// 中序遍历二叉树，并改造成中序线索二叉树
void InThread(ThreadTree T)
{
    if(T != NULL)
    {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

// 前序遍历二叉树，并改造成前序线索二叉树
void PreThread(ThreadTree T)
{
    if(T != NULL)
    {
        visit(T);

        // 只有 lchild 是真正的左孩子时，才继续递归
        if(T->ltag == 0)
            PreThread(T->lchild);

        // 只有 rchild 是真正的右孩子时，才继续递归
        if(T->rtag == 0)
            PreThread(T->rchild);
    }
}

// 后序遍历二叉树，并改造成后序线索二叉树
void PosThread(ThreadTree T)
{
    if(T != NULL)
    {
        PosThread(T->lchild);
        PosThread(T->rchild);
        visit(T);
    }
}

// 创建中序线索二叉树
void CreateThreadTree(ThreadTree T)
{
    pre = NULL;

    if(T != NULL)
    {
        InThread(T);

        // 处理遍历序列中的最后一个结点
        if(pre->rchild == NULL)
        {
            pre->rchild = NULL;
            pre->rtag = 1;
        }
    }
}

注意事项

1. 结点创建时需要初始化标志位

每个结点在创建时，ltag 和 rtag 应该初始化为 0。

1
2

node->ltag = 0;
node->rtag = 0;

因为一开始普通二叉树中的 lchild 和 rchild 默认表示孩子指针。

如果不初始化，ltag 和 rtag 可能是随机值，可能导致判断错误。

2. 前序线索化时需要防止把线索当成孩子

前序线索化中，访问顺序是：

1

根 → 左 → 右

调用 visit(T) 之后，T 的空指针可能已经被改造成线索。

所以递归左、右孩子之前，最好判断：

1
2
3
4
5

if(T->ltag == 0)
    PreThread(T->lchild);

if(T->rtag == 0)
    PreThread(T->rchild);
说明

只有当 lchild/rchild 真正表示孩子时，才继续递归。

3. 后序线索二叉树的遍历相对复杂

后序遍历顺序是：

1

左 → 右 → 根

后序线索化本身可以使用同样的 visit() 思想。

但是后序线索树在寻找某个结点的后继时，往往需要知道它的父结点。

如果结点结构中没有父指针，后序线索树的遍历会比中序线索树麻烦。

小结

线索二叉树的核心思想可以概括为：

利用二叉树中的空指针，保存遍历序列中的前驱和后继信息。

其中：

1
2

空左指针 → 指向前驱
空右指针 → 指向后继

同时，用 ltag 和 rtag 区分指针含义：

1
2

tag = 0：指向孩子
tag = 1：指向线索

中序线索二叉树最常用，也最容易掌握。

它的构造过程，本质上就是：

1

在中序遍历过程中，一边访问结点，一边建立前驱和后继线索。

相关内容

更新于 2026-06-23 
数据结构算法代码
返回 | 主页

目录