当前课程知识点：数据结构 > 第6章 树和二叉树 > 6.4 遍历二叉树 > 6.4 遍历二叉树（1）
同学们大家好
我是云南大学信息学院教师孔兵
这节课我们讨论遍历二叉树。
先引入遍历二叉树的概念
在二叉树的一些应用中
常常要求在树中查找具有某种特征的结点
或者对树中全部结点逐一进行某种处理
这就引入了遍历二叉树的问题
也就是如何按照某条搜索的路径
寻访树中每一个结点
使得每一个结点均被访问一次
而且仅被访问一次
简单的说
遍历就是访问树中每个结点一次
而且仅一次
遍历问题
对任何数据结构都是非常重要的
在前面讨论线性表的时候
我们并没有很特别的讨论线性表的遍历
主要原因是，遍历对线性结构是很容易解决的问题
不管是顺序存储的线性表
还是单链表，其遍历的策略都是一样的
通过循环从第1个结点开始依次找后继
访问整个系列即可
二叉树虽然是最简单的树
但是二叉树任然是非线性的
那么要按照什么样的次序来遍历呢？
这就需要寻找一种规律
以便能按照这种规律遍历二叉树
根据访问树中结点的先后次序
可以得到二叉树的访问序列
当然，这个访问序列是线性的
遍历二叉树的主要问题就是
需要按照某条搜索路径
或者可以称为策略
去寻访树中每个结点
使得树中每个结点均被访问一次，而且仅一次
针对二叉树的遍历问题
我们是这样来考虑的
首先，对这个问题进行递归分解
原问题是遍历二叉树
我们把它分解为三个子问题
一个是访问根，一个是遍历左子树
一个是遍历右子树。从图中我们可以看到
如果根被访问了，左右子树也都遍历了
那么，自然就解决了遍历二叉树的这个原问题
并且注意到，遍历左子树
和遍历右子树，它们都是对二叉树的遍历问题
和原问题相比较，这是两个同类型相同
规模缩小的问题，这是典型的递归分解
基于上述的递归分解
根据访问根的时机的不同
形成了三种遍历的策略
若二叉树为空，则进行一个空操作
如果在遍历左右子树之前先访问根
随后先去遍历左子树
再遍历右子树，这是所谓先序策略
如果在遍历了左子树之后
访问根，随后再遍历右子树
这是中序策略。如果左右子树都遍历
再来访问根，这是后序策略
三种策略递归分解的过程是一样的
区别是访问根的时机不同
下面结合图中的二叉树
我们分析一下，不同策略下的获得的访问序列
先看一下先序策略
先序策略是首先访问根
随后遍历左子树，再遍历右子树
第1个访问的结点是A，它是访问序列的第一个结点
根据策略，访问根以后
递归调用，遍历左子树
也就是以B为这根的这颗子树
在这棵子树当中仍然采用先序策略
首先访问根结点B
这是先序序列中第2个被访问的结点
随后，递归调用，遍历B的左子树
就是以D为根的这棵子树树
也是访问D，递归遍历D低的左子树
D的左子树是空树，空操作
返回D为根的这层调用
随后递归遍历D的右子树
也是空树空操作，从D的右子树返回以后
以D为根这个子树就算完全被遍历了
返回上一层，以B为根的这棵子树
现在以B为根的这棵树中
根和左子树已经遍历，随后递归
遍历B的右子树，以E为根的这棵树
先访问E，递归遍历E的左子树
访问G，遍历G左右空树，返回E
遍历E的右子树，从E右子树
空树空操作返回后
以E为根这棵树也就被访问完了
返回上一层，以B为根这个子树而言
现在根和左右子树都被遍历了
也就是整棵子树的遍历已经完成
那么返回上一层，以A为根的这层调用
对A为根的这棵树来说
根和左子树已经遍历完随后应该遍历A的右子树
递归过程类似，就不重复了
按照先序策略
先序访问序列是：ABDEGCF。
下面说一下中序策略
中序遍历递归分解的过程和先序是一样的
只不过访问根的时机不同
中序是在遍历了左子树以后访问根
随后遍历右子树。中序遍历以A为根的这棵树
递归，遍历A的左子树
以B为根这棵树，同样递归
遍历B的左子树，以D为根的这棵树
递归遍历D的左子树，空树空操作返回
返回后，D的左子树已经遍历
根据中序策略遍历左子树后访问根
所以应该访问D
D也是中序访问序列中第1个被访问的树中结点
访问D后，遍历D的右子树
空树空操作返回
到此，完成对D为根这棵子树的中序遍历
随后返回上一层，B为根的这一层
对B为根的子树来说
左子树已经遍历完了，那么应该访问根
B是整棵树中第2个被访问的结点
访问B以后，递归遍历B的右子树
以E为根的子树，详细递归过程就不说了
根据中序策略，先访问G，随后是E
从B这颗子树返回以后，返回到A为根这层
A左子树的4个结点已经被访问过了
已经被遍历完了
按照中序策略，应该访问A
访问A以后，递归遍历右子树
最后的中序访问序列是：DBGEAFC。
观察一下中序序列，注意A的位置
A是整棵树的根，按中序策略
先遍历左子树，访问根，再遍历右子树
它的前部就是A左子树的中序序列
包含左子树的4个结点DBGE
它的后部是右子树的两个结点FC
后序遍历是在左右子树都遍历完了以后
再来访问根，大家可以看到
后序序列最后一个访问的结点是A
后序遍历，同学们可以自己尝试一下
递归过程是一样的
就是访问根时机是遍历了左右子树之后
好同学们，这节课我们就介绍到这儿
下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
