数据结构二叉树遍历.doc

. .

6.3 二叉树遍历

6.3.1 二叉树遍历的定义

所谓二叉树遍历，就是按某种规那么访问二叉树的每个结点，且每个结点仅

被访问一次。“访问〞的含义十分广泛，包括对结点所作的各种操作与处理，如有

关学生考试成绩的信息存储在一棵二叉树中，每个结点含有学号、、成绩等信

息，在对这些信息进展管理时常常需要做这样的工作：

〔〕RRRRRRR打印每个学生的学号、、成绩等信息；

子树和右子树的位置，假设能遍历这三局部，那么完成对一棵二叉树的遍历。假设以

〔〕、、分别代表访问根结点、遍历左子树、遍历右子树，那么

访问二叉树结点的规那么可有 、、 三种遍历和 、、 三种逆遍

历方式。一般限定先左后右，仅讨论前三种遍历，分别称之为前序遍历〔

〕、中序遍历〔〕和后序遍历〔

〕。基于二叉树的递归定义，可得三种遍历二叉树的递归定义：

前序遍历二叉树 中序遍历二叉树 后序遍历二叉树

根RRRRRRRR





假设二叉树为空，那么

空操作；

否那么〔〕访问根结

点；

〔〕前序遍历左子树；

〔〕前序遍历右子树。

假设二叉树为空，那么

空操作；

否那么〔〕中序遍历左

子树；R

〔〕访问根结点；

树。

. .



从上述定义可以看出，三种遍历的不同之处仅在于访问根结点、遍历左、右



!%



"#&



$'

图 二叉树遍历



6.3.2 前序遍历算法描述



算法 6.1

!

()前序遍历二叉树的递归算法)(

*



* +,〞-./0((访问根结点

./10((遍历左子树

./10((遍历右子树

2

. .

2

如图 4 所示为前序遍历二叉树的过程示意图。带箭头的包围虚线表示前序



"#&""#&



!"#%&



〔〕前序遍历二叉树— !"#%&〔5〕前序遍历过程示意图

图  二叉树前序遍历过程示意图



2.非递归算法

下面，我们来讨论前序遍历算法的非递归实现。一个具有递归特点的问题，

如果用非递归的程序实现，通常可以借助于栈来实现递归层次调用时的参数传

678 #99

:!

()前序遍历二叉树的递归算法)(

* !;1<=8 #>-:0

:?90

:?0



*

@:A?B