全屏显示专题章节

二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。

遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。

通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成，因此只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。

1.先序遍历（DLR）

先序遍历的递归过程为：若二叉树为空，遍历结束。否则，

（1）访问根结点；

（2）先序遍历根结点的左子树；

（3）先序遍历根结点的右子树。

先序遍历二叉树的递归算法如下。

算法6.5 先序遍历二叉树递归算法

对于图6－7（b）所示的二叉树，按先序遍历所得到的结点序列为：

2.中序遍历（LDR）

中序遍历的递归过程为：若二叉树为空，遍历结束。否则，

（1）中序遍历根结点的左子树；

（2）访问根结点；

（3）中序遍历根结点的右子树。

中序遍历二叉树的递归算法如下。

算法6.6 中序遍历二叉树递归算法

对于图6－7（b）所示的二叉树，按中序遍历所得到的结点序列为：

3.后序遍历（LRD）

后序遍历的递归过程为：若二叉树为空，遍历结束。否则，

（1）后序遍历根结点的左子树；

（2）后序遍历根结点的右子树；

（3）访问根结点。

后序遍历二叉树的递归算法如下。

算法6.7 后序遍历二叉树递归算法

对于图6－7（b）所示的二叉树，按先序遍历所得到的结点序列为：

所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于图6.7（b）所示的二叉树，按层次遍历所得到的结果序列为：

下面讨论层次遍历的算法。

由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：

（1）访问该元素所指结点；

（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。

此过程不断进行，当队列为空时，二叉树的层次遍历结束。

在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue［MAXNODE］用以实现队列，变量front和rear分别表示当前对首元素和队尾元素在数组中的位置。