二叉树的遍历

2.6.4　二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有节点。

由于二叉树是一种非线性结构。因此，对二叉树的遍历要比线性表的遍历复杂得多。在遍历二叉树的过程中，当访问到某个节点时，再往下访问可能有两个分支，那么先访问哪一个分支呢？对于二叉树来说，需要访问根节点、左子树上的所有节点、右子树上的所有节点，在这三者中，究竟先访问哪一个？也就是说，遍历二叉树的方法实际上是要确定访问各节点的顺序，以便不重不漏地访问到二叉树中的所有节点。

在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根节点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法：

1．前序遍历（DLR）

所谓前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。

下面是二叉树前序遍历的简单描述：

若二叉树为空，则结束返回。

否则：（1）访问根节点；

（2）前序遍历左子树；

（3）前序遍历右子树。

在此特别要注意的是，在遍历左右子树时仍然采用前序遍历的方法。

如果对如图2-34(a)所示中的二叉树进行前序遍历。则遍历的结果为F，C，A，D，B，E，G，H，P（称为该二叉树的前序序列）。

2．中序遍历（LDR）

所谓中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。

下面是二叉树中序遍历的简单描述：

若二叉树为空，则结束返回。

否则：（1）中序遍历左子树；

（2）访问根节点；

（3）中序遍历右子树。

在此也要特别注意的是，在遍历左右子树时仍然采用中序遍历的方法。

如果对如图2-34(a)所示树进行中序遍历，则遍历结果为A，C，B，D，F，E，H，G，P（称为该二叉树的中序序列）。

3．后序遍历（LRD）

所谓后序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问右子树，最后访问根节点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。因此，后序遍历二叉树的过程也是一个递归的过程。

下面是二叉树后序遍历的简单描述：

若二叉树为空，则结束返回。

否则：（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根节点。

在此也要特别注意的是，在遍历左右子树时仍然采用后序遍历的方法。

如果对图2-34(a)中的二叉树进行后序遍历，则遍历结果为A，B，D，C，H，P，G，E，F（称为该二叉树的后序序列）。