6.5 线索二叉树在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论线索二叉树

上一节课中

我们讨论了遍历二叉树

遍历是二叉树中最重要

一般也是最频繁的操作

基本方法是利用递归实现遍历

但是，递归程序的执行，一般来说效率不高

这就带来了一个挑战，如何提高遍历的效率？

我们分析一下，遍历是按照一个策略

依照访问次序，依次访问树中的每个结点

如果我们能够不通过遍历，而是从访问序列的前一个结点

直接找到后一个结点，当然实现的代价要合理

那么，遍历的过程就可以通过循环

从第一个访问的结点开始

通过不断找访问序列后一个结点

同样可以实现二叉树的遍历

为了达成这样的目标

有效的办法是建立线索二叉树

线索二叉树的核心是所谓的线索

线索，本质上是一个指针

能建立线索二叉树的基础就是

n个结点的二叉链表中有n+1个空指针

这个特点前面说过

比如图1当中，有5个结点

可以看到有6个空的指针或者叫空链域

我们就是利用这样的空链域建立线索

让空链域发挥作用，指向访问序列的前驱和后继

如果结点的右链域为空的话

则让右指针指向访问序列的后继

如图2中，结点E右指针为空

中序序列中，E的后继是A，就在E右链域中

存指向它中序后继A结点的指针

图中是红色的虚箭头表示

若结点的左链域为空的话

则让左指针指向访问序列的前驱

图2中，观察F结点，它是一个叶子

左右指针皆为空，让F的左指针指向中序序列的前驱B

右指针指向中序序列的后继E

用这样的方法，就建立了所谓的线索

在这里，我们要注意到

因为对空链域的扩充应用

结点中的指针有了两种用途

一种是指向孩子，一种是指向访问序列的前驱或是后继

就指针本身来说，我们无法把它们区别开

所以线索二叉树的结点存储结构需要重新设计

我们把线索二叉树的结点设计为5个成员

其中包括原来的三个成员

增加了两个成员作为标志，LTaG和RTaG

规定，若结点有左子树，则其lChilD域指示其左孩子

否则令其lChilD域指示其前驱

若结点有右子树，则其rChilD域指示其右孩子

否则令其rChilD域指示其后继

为了区别两种指针

我们用LTaG和RTaG作标志

LTaG等于0的时候，标明左指针指的是左做孩子

等于1的时候，说明左指针指的是访问序列的前驱

RTaG的作用与之相同

下面我们以中序线索二叉树为例

看一下，一棵完整的中序线索二叉树是什么样子？

在线索二叉树中,我们增加了一个头结点

其作用类似于单链表中的头结点

头结点的左指针指向树的根结点

头结点的右指针指向中序遍历的最后一个结点

在例子中是结点C

同时，让二叉树中序遍历的第1个结点D的左指针指向头结点

中序遍历的最后一个结点C的右指针

也指向头结点

其他结点的指针如规定设置

样子如图所示

为了区别，把指向前驱的指针标为绿色

后继的指针标为红色

当然，我们的目标是希望在这样的一颗中序线索二叉树中

不用递归，基于建立的线索，能通过循环完成中序的遍历

下面讨论一下如何在中序线索二叉树中利用循环，实现中序的遍历

我们利用一个指针p，从第1个中序访问的结点出发

通过循环不断找后继的方式

实现对整棵二叉树的中序遍历

当指针p从最后访问的结点回到头结点的时候呢

循环结束，完成遍历

下面我们看一下具体的过程

通过头结点的左指针，可以让p指向根结点A

随后，p从树根结点出发，不断向左

找到最左下的结点

例子中是结点D，这是中序遍历第1个访问的结点，访问它

接着找它中序序列的后继

分两种情况：一种情况是目前访问结点的RtaG=1

说明右指针是线索，指向中序序列的后继

p=p->rchild即可让p指向它的后继

对下一个结点进行访问

第二种情况是，目前访问结点的RtaG=0

说明它有右子树，右指针指的是右孩子

从中旬策略我们知道，下一个要访问的结点

是右子树中中序遍历的第1个结点

p=p->rchild，让p指向右子树根

然后不断向左，找到右子树最左下的结点

这就是右子树中，中序遍历的第1个点

也就是下一个要访问的结点

通过循环不断找后继的方法

可以完成对整棵树的中序遍历

最后p指针回到头结点

遍历结束，教材上有相关程序的实现

同学们可以自己看一下

注意一下，基于中序线索二叉树

我们也可以从中序遍历的最后一个结点出发

通过不断找前驱的方法实现逆序的中序遍历

方法和找后继对称，同学们自己思考一下

有一点我们要明确一下，基于中序线索二叉树

只能实现中序的循环遍历

如果问题背景下需要的按其它策略遍历

比如先序或后序

那么我们就应该建立对应的先序线索二叉树或后序线索二叉树

他们的情况和中序线索二叉树类似

只不过线索指向的是先序访问序列或后序访问序列的前驱和后继

下面看一下后序线索二叉树的遍历

和中序线索二叉树类似

也是利用指针p，从后序遍历的第1个点开始

循环找后继遍历，有线索的情况

直接通过线索找后继即可

我们主要讨论没有线索的情况下，如何找后继

右图是给出了后序线索二叉树的一个简化的例子

主要用红色虚箭头画出后序的线索

设x是正在访问的结点，并且x结点没有线索

右指针指向右x右子树的根，分三种情况讨论

第一， 若结点x是二叉树的根，则没有后继

比如x如果是H，这已经是后序遍历的最后一个结点

第二， 若结点x是其双亲的右孩子

或者是其是双亲的左孩子，但是其双亲没有右孩子

那么其后继就是x的双亲结点，是下一个要访问的结点

p指向x的双亲就可以了

比如结点C，C是双亲D的右孩子

按照后序策略，C访问完了以后

D的右子树就遍历完了，下一个访问的应该是D

再看结点F，F是G的左孩子，但是G没有右孩子

所以访问F以后，下一个要访问的结点，就应该是G

第三， 若结点x是其双亲的左孩子

且其双亲有右子树

则其后继为双亲的右子树上按后序遍历的第一个结点

例如D是H的左孩子，并且H有右子树

那么D访问完了以后，下一个访问的结点就是H的右子树

以G为根的这棵树中

后序遍历的第1个结点，例子中是结点E

找一棵二叉树中后序遍历的第1个结点怎么做

请同学课后思考

另外，后序遍历中

要判断是上述三种情况的那一种

我们要知道当前访问结点x的双亲

所以，后序遍历中需要用到一个栈，记录x的双亲的是谁

这节课讨论了基于线索二叉树，利用循环实现遍历

提高遍历的效率

前面讨论的都是在已经建立的线索二叉树上

怎么进行遍历

那么，线索二叉树怎么建立的呢？

线索二叉树的建立，相对来说并不困难

可以通过一次递归的遍历

在递归的过程当中，依据访问次序

按两个结点前驱和后继的关系，建立起线索就可以了

好同学们，这节课就到这儿

我们下次课再见