6.4 遍历二叉树（2）在线视频

同学们大家好

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

这节课我们继续讨论遍历二叉树

关于二叉树的遍历，有一个问题是经常会遇到

就是已知二叉树的先序序列和中序序列

画出这棵二叉树

原问题就是要依据先序和中序序列画出这颗二叉树

这里仍然是利用递归分解的办法来做

把画二叉树的问题，分解为三个子问题

一是画出二叉树的根，随后画出二叉树的左子树

再画出二叉树的右子树

这三个子问题解决了

画二叉树的问题也就解决了

我们具体看一下怎么做

我们以前一张幻灯片中的二叉树为例

现在已知的条件是二叉树的先序ABDEGCF和中序DBGEAFC

在最上面的方框中

我在序列中加了几个空格

目的是让大家观察的清楚一些

空格不说序列的一部分

按照递归分解，先画根

从先序策略我们知道

先序序列中第1个被访问的

就是整棵树的根，依据先序序列

可以画出整棵二叉树的根A，如图1所示

随后在中序序列中找到整棵树的根A

A左边的4个结点是A左子树的中序序列

从中序策略我们知道

A左边的4个结点是A左子树的中序序列

这个左子树结点个数很重要

我们就是依据它

从先序序列中A后面找出4个结点

按先序策略，这是A左子树的先序序列

如A左子树的框中所示

我们得到了A左子树的先序序列是BDEG

中序序列是DBGE

同时对称的

可以知道A右子树的先序序列是CF

中序序列是FC

大家可能注意到，现在我们的问题递归了

变成依据A左右子树的先序和中序

画出左右子树两个同类型的子问题

例如，画出A的左子树

依据左子树的先序序列是BDEG

可以画出左子树的根B

如图2所示，在A左子树的中序序列DBGE找B

在A左子树的中序序列DBGE中，找B

利用同样的方法

可以确定B左右子树的中序和先序

递归过程可以继续下去

图3,4给出了画A左图，图3,4给出了左子树的后序过程

同学们自己考虑一下

画A右子树过程类似

如果已知二叉树的后序序列和中序序列

也可以用类似的方法画出二叉树

但是，同学们要注意，已知先序和后序序列

是无法画出二叉手的

举个反例，先序序列是AB

后序序列是BA。不管是通过先序还是后序

都可以画出整棵树的根是A

但是，无法确定B到底是A的左孩子还是右孩子

之所以我们重点讨论这个问题

主要目的是为了实现二叉树的存储

线性表输入计算机是很容易的

按照序列次序输入即可，即输入了元素

也蕴含了关系

二叉树的输入就麻烦些

通过输入先序和后序序列是一种有效的方法

两个序列中除了包含树中元素外

按上面的讨论，它们还蕴含了结点之间的关系

可以基于上面讨论的过程

设计算法建立二叉树的存储结构

下面看一下程序的实现

以先序遍历为例，函数的返回值是执行状态

表示遍历成功与否

涉及到的参数有两个

一个是指向要遍历二叉树根结点的指针T

标明遍历的对象

一个是指向函数的指针visit

目的是通过调用visit所指的函数

对正在访问的结点进行处理

进入函数，如果T为空

那么是空树，else直接返回ok

空操作，如果T非空，进入一个复合语句

有3个嵌套的标为红色的IF语句

第一个If的条件表达式中是通过调用visit所指函数

访问根结点，这是先序遍历

调用返回有两种情况，访问如果不成功

返回error，说明遍历已经失败

后续遍历没有意义了

从绿色块的return Error返回

访问如果成功，返回OK，则进入第2个if语句

第2个if语句条件表达式是递归先序遍历左子树

如果遍历左子树的时候失败，返回Error

同样通过绿色块的return Error返回

如果左子树遍历是成功的，返回OK

则执行第3个if语句

条件表达式是递归先序遍历右子树

右子树访问如果失败，返回Error

仍然通过绿色块的return Error返回

如果右子树的遍历是成功的

返回OK，此时我们才return OK

表示对整棵树的遍历成功完成

如果要实现中序遍历，只需要在先序遍历函数中

把第1个if语句的条件表达式和第2个if语句的条件表达式部分对调即可

要实现后序，只需要在先序遍历函数中

把第1个if语句的条件表达式和第3个if语句的条件表达式部分对调即可

这里就不具体讨论了

从上面的讨论当中，我们注意到

因为，树结构本身就有递归特点

所以用递归的方法处理起来比较简单

看一个例子

编写递归算法，计算二叉树中

叶子结点的数目。这个问题可以进行递归分解

原问题是计算二叉树中叶子结点的树木

这个问题可以分解为两个同类型的子问题

计算左子树叶子结点的数目

计算右子树叶子结点的数目

这两个问题解决后

把二者结果相加即为整棵树叶子结点的数目

看一下函数，函数的返回值是个整棵树叶子结点的数目

参数只有一个，就是指向二叉树根结点的指针bt

如果指针为空，这是一颗空树

没有叶子，返回0

否则，如果根结点的左右孩子指针为空

这是一个叶子，返回1

再否则，递归调用

计算根结点左右子树叶结点的数目

随后return二者相加的结果

作为整棵树叶子结点的数目

再看一个例子

二叉树的遍历，除了前面讨论的先序

中序和后序的遍历策略以外

还有一种遍历的策略是按层次顺序

也就是按照树的层次结构，自上而下

自左至右访问树中的结点

在第7章图中

我们会介绍图的一种遍历策略叫广度优先搜索策略

到时候大家再转回来看一下

会发现，二叉树的层序遍历

就是广度优先搜索策略的一个简化应用

好同学们

这节课我们就介绍到这儿

下次课再见