讲解在线视频

这一节，我们来学习线索二叉树

先来看问题的提出

我们之前讲了树的遍历

比如这样一棵树

它的先序序列是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个指针

这个左指针已经被用过了

所以，我们就让右指针指向最后一个结点

对于其他的树

可能让左指针指向第一个结点

总之

这个指向关系比较灵活