当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.5 线索二叉树 > 讲解
这一节，我们来学习线索二叉树
先来看问题的提出
我们之前讲了树的遍历
比如这样一棵树
它的先序序列是AB
CDE
G
F
在遍历的时候，能不能直接找到下一个(上一个)要(已)访问的结点呢
我们之前讲的递归形式的遍历算法
由于递归可能要进行很深的调用
不是在O(1)的时间复杂度内，找到当前结点的下一个结点
那能不能直接找到
也就是在O(1)的时间复杂度内
找到某一个结点
它的下一个结点或者上一个结点呢
比如，这里的C结点
如果我们当前知道C结点
能不能直接得到它在中序序列当中的下一个结点D，或者前一个结点B呢
这就是问题初衷之一；第二个问题
我们知道，n个结点的二叉链表
它有n+1个空指针
我们能不能把这些为空的
指针利用起来呢
这就是我们要讲的线索
二叉树
线索二叉树将原本为空的左右孩子指针，修改为线索
这些线索
指向该结点在遍历所得序列中的前驱和后继
比如，C结点
它是没有左孩子的
我们现在把本来为空的左孩子指针
让它指向B结点
为什么指向
B结点呢？因为，在先序序列当中
C结点的前驱是B
所以，我让左孩子指针指向它的前一个结点B
而C的后一个结点是D
所以，我让它原本为空的右孩子指针指向D
这样
我们就把为空的左右孩子指针，修改成了一些其它的有用的信息
这些信息就叫做线索
这个过程就是线索化
现在，我们来看几个具体的线索二叉树
图的左上区域，给出了一个中序的线索二叉树
我们来观察一下，那些实线的指针表示的是左右孩子
而虚线的指针原本是空
现在，我们把它修改成线索
以2这个结点为例
在中序序列当中
2前面那个结点是多少呢
也就是说
访问完哪个结点之后，才到2的呢
通过分析
可以发现
2作为1的右子树上
最左的那个结点
它应该是紧接着1被访问的，因为我们知道，中序遍历，访问完1的左子树
然后访问1
然后，再以中序访问1的右子树，1的右子树上
首先被访问的第一个结点，应该是右子树上最左的那个结点
也就是说，1访完了之后
紧接着是2；那么，2的前驱
我们就把这个空指针，修改成指向1
我们再看4，4这个结点
以中序遍历访问完了之后，4后面那个结点又是谁呢
4是5这个结点
它左子树的最右的结点
也就是说，访问完4之后
5的左子树已经访问完了
那紧接着，应该访问5这个根
所以4的后继
应该是5
所以，我们把原本为空的、4的右孩子，把它修改成指向5这个结点
我们如何来区分孩子指针和线索呢
毕竟在纸上
可以用实线、虚线来区分孩子和线索
在内存当中
如何来区分呢
比如，这样一个加了线索的
二叉树，红色虚线的，是表示线索
绿色实线，表示孩子指针，现在，我们来这样区分：无非就是加2个标记
加2个tag，分别标志左、右孩子指针是否真的是孩子还是线索
因为，从内存的角度来说
left、right就是2个指针
你怎么知道这2个指针，指向是孩子还是线索呢
我们用标记
如果这2个标记等于0
说明left和right分别指向左、右孩子
如果它们等于1
说明它们指向的是当前结点
在某一种序的遍历得到的序列当中
这个结点
它前面的那个结点(前驱)
或者后面那个结点(后继)
比如，我们把上面这个图画成内存当中的结构
那么，通过左标志和右标志
来区分到底是孩子还是线索
比如，C这个结点
它的左标志是0
说明这个指针指向的是孩子
E是C的左孩子，而E结点
它的右标志是1，说明right指针指向的是E结点它的后继
现在，我们来看具体的代码实现
首先，我们定义了一个枚举类型的别名
注意，这个Pointer，是枚举类型的别名
将来，用Pointer定义一个变量
它就是枚举变量
因为指针
只能是孩子或线索
在定义lTag和rTag的时候
当然可以定义成整型的0、1
但是为了代码更加友好
我们将0、1改成CHILD和THREAD，也就是孩子和线索
它的本质就是我们刚才讲的0或者1
结构体，前面跟二叉链表都是一样的
只不过，多了2个类型为Pointer的成员
lTag和rTag
它们的取值，要么是CHILD
要么是THREAD
定义2个别名
线索结点、线索树
现在，我们来看二叉线索树的遍历
加了线索的
二叉树，在遍历的时候，是不需要经过递归的
我们可以直接利用树当中的线索，来找到当前结点的前驱和后继
从而把整个遍历序列写出来
如果当前结点
它的指针指向的是左、右孩子
而并不是前驱、后继，也就说，并不是线索
这时候，可以利用规律
利用遍历、利用结点之间的相对位置，来找出结点的前驱和后继
我们以中序线索树为例
中序线索树，它的第一个结点应该是整棵树当中，最左的那个结点
因为，根据中序遍历的遍历规则，是先左、再根、再右
在遍历左子树的时候
又要以中序遍历左子树的左子树
所以，中序遍历第一个被访问的结点，应该是整个树当中最左的那个结点
也就是D
通过后继指针，可以找到下一个元素
那万一当前结点
它的右指针指向的是右孩子，而不是后继呢
我们以B为例
B的右指针指向的是右孩子，而不是后继
通过分析
我们可以发现，以B为根着这棵树
在根B访问完之后
我们应该访问B的右子树，B的右子树以中序遍历，第一个被访问的结点
应该是这棵右子树上，最左的那个结点
也就是G
根据这些规则
我们就能够找出一棵线索
二叉树当中，每一个结点
它的出现位置
我们现在以找后继为例
刚才我们分析了，第一个结点
应该是最左的那个结点
所以是D，D的右指针
我们这里用颜色来标志
它是后继或前驱(绿色的表示线索)
第一个是D
D完了之后，可以直接找到B
刚才我们分析了，右子树最左的那个结点
应该是G
它的右孩子是J
右子树上最左的，只有一个
那就是J，J的后继是E
直接找到，E的后继
是A，直接找到
A
它的后继，应该是右子树上最左的那个结点
因为，A的右子树
根是C
C没有左子树，那最左的结点就是C本身
C的右子树最左的结点，应该是来H
H的右子树最左的结点，应该是L
L直接找到K
K直接找到F，F右子树最左的结点，只有一个结点，是I
这样，我们就把整个序列写出来了
与之对称的
如果我们是通过从右向左找
也就是找前驱
怎么给出这个序列呢
首先，我们要知道最后一个结点
通过分析
可以发现，中序遍历最后一个被访问的结点
应该是树当中处于最右的那个结点
也就是I
我们怎么去找前驱呢
如果left指针指向的是左孩子
而不是前驱
我们可以通过分析发现，左子树上最右的那个结点，应该是访问根结点之前，被访问的那个结点
左子树最右的结点是根结点的前驱
现在，我们从右往左找
根据分析
我们发现，最后一个结点，应该是最右的结点
然后找前驱，直接找到F
F的左子树最右的结点，应该是K
K的左子树最右的结点，只有一个
是L
L直接找到H
H直接找到C
C直接找到A，A的前驱
左子树最右的结点，应该是E
E的前驱，左子树最右的结点，应该是J，J直接找到G，G直接找到B，B的左子树
只有一个结点D
我们从右往左找
找前驱，也能找出最后的中序序列
刚才，我们讲了二叉线索树的遍历
那么，如何给一棵普通的二叉树加线索呢
也就是二叉树的线索化
现在，我们来看算法思想，跟前面的遍历一样
实际上，我们也是在普通的二叉树当中
通过遍历，来逐个地为那些为空的指针
把它们修改成指向结点的前驱和后继的指针
需要注意
如果当前访问的结点是p
比如，p指向5这个结点
那么，一定要保持一个指针
比如pre
它指向p之前访问的那个结点
比如，对于这样一棵
我们准备加中序线索的
二叉树，在访问p的时候
p前一个被访问的那个结点，应该是4
始终让p和pre保持后继和前驱的关系
也就是说
p是pre的后继
这样
就可以
把pre的right指针修改成p，实际上，就是将pre指向的结点
给它加线索
有时候为了方便操作
我们人为地附设一个头结点
我们给树也增加一个结点
这个结点的结构跟树当中
每一个结点的结构都是一样的
然后，建立它与根结点、首结点、末结点之间的指向关系
主要是为了方便操作
比如，我们这里将整棵树的第一个结点，将它的前驱指向头结点
整棵树的最后一个被访问的结点11，将它的后继指向头结点
然后，让头结点的后继认为是最后一个结点
有的同学说，为什么不让头结点的前驱是第一个结点呢
这样方便找第一个结点啊
因为，这棵树(根为8)
它已经作为头结点的左子树了
一个结点只有2个指针
这个左指针已经被用过了
所以，我们就让右指针指向最后一个结点
对于其他的树
可能让左指针指向第一个结点
总之
这个指向关系比较灵活
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
