数据结构二叉树遍历.pdf

-

6.3二叉树遍历

二叉树遍历的定义

所谓二叉树遍历，就是按*种规则访问二叉树的每个结点，且每个结点仅被访

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

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

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

〔1〕打印每个学生的**、**、成绩等信息；

〔2〕将每个学生的成绩由百分制记分改为五级制记分；

〔3〕统计优、良、中、及格和不及格各档次的人数。

在〔1〕中访问〞的含义是打印每个结点的信息；对于〔2〕，访问〞是对成

绩进展修改的操作；〔3〕中访问〞是统计操作。不管访问的具体操作是什么，都

必须做到既无重复，又无遗漏。

一棵二叉树由根结点、左子树、右子树三个根本单元组成，根结点处于一个分

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

设以N〔Node〕、L(Left)、R(Right)分别代表访问根结点、遍历左子树、遍历右

子树，则访问二叉树结点的规则可有NLR、LNR、LRN三种遍历和NRL、RNL、RLN三

种逆遍历方式。一般限定先左后右，仅讨论前三种遍历，分别称之为前序遍历

〔PreorderTraversal〕、中序遍历〔InorderTraversal〕和后序遍历〔Postorder

Traversal〕。基于二叉树的递归定义，可得三种遍历二叉树的递归定义：

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

1根2根3根

23

1312

左子树右子树

左子树右子树左子树右子树

假设二叉树为空，则空操假设二叉树为空，则空操假设二叉树为空，则空操

作；作；作；

否则〔1〕访问根结点；否则〔1〕中序遍历左子否则〔1〕后序遍历左子

树；树；

〔2〕前序遍历左子树；

〔2〕访问根结点；〔2〕后序遍历右子树。

〔3〕前序遍历右子树。

-

〔3〕中序遍历右子〔3〕访问根结点；

树。

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

树的先后次序不同。前序〞是指最先访问根结点；中序〞是指根结点在访问左、

右子树之间被访问；后序〞是指根结点在左、右子树访问之后被访问。对于如图

6.15所示的二叉树，前序遍历该二叉树时的结点访问序列为：ABDEGCFHI；

中序访问序列为：DBGEACHFI；后序访问序列为：DGEBHIFCA。

A

BC

DEF

GHI

图6.16二叉树遍历

前序遍历算法描述

1．递归算法

由前序遍历二叉树的递归定义，容易得到相应的递归算法。前序遍历首先访

问根结点，再访问左子树，然后访问右子树。对左子树的访问，也是先访问其根结

点，再访问左其子树，