6.8　遍历二叉树

6.8.1　二叉树遍历原理

假设，我手头有20张100元的和2000张1元的奖券，同时洒向了空中，大家比赛看谁最终捡的最多。如果是你，你会怎么做？

相信所有同学都会说，一定先捡100元的。道理非常简单，因为捡一张100元等于1元的捡100张，效率好得不是一点点。所以可以得到这样的结论，同样是捡奖券，在有限时间内，要达到最高效率，次序非常重要。对于二叉树的遍历来讲，次序同样显得很重要。

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

这里有两个关键词：访问和次序。

访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。

二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。就像你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由于选择方式的不同，遍历的次序就完全不同了。

图6-8-1

6.8.2　二叉树遍历方法

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：

1．前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图6-8-2所示，遍历的顺序为：ABDGHCEIF。

图6-8-2

2．中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图6-8-3所示，遍历的顺序为：GDHBAEICF。

图6-8-3

3．后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图6-8-4所示，遍历的顺序为：GHDBIEFCA。

图6-8-4

4．层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图6-8-5所示，遍历的顺序为：ABCDEFGHI。

图6-8-5
有同学会说，研究这么多遍历的方法干什么呢？

我们用图形的方式来表现树的结构，应该说是非常直观和容易理解，但是对于计算机来说，它只有循环、判断等方式来处理，也就是说，它只会处理线性序列，而我们刚才提到的四种遍历方法，其实都是在把树中的结点变成某种意义的线性序列，这就给程序的实现带来了好处。

另外不同的遍历提供了对结点依次处理的不同方式，可以在遍历过程中对结点进行各种处理。

6.8.3　前序遍历算法

二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了。先来看看二叉树的前序遍历算法。代码如下：

    /* 二叉树的前序遍历递归算法 */void PreOrderTraverse（BiTree T）{if（T==NULL）return;printf（"%c",T->data）;/* 显示结点数据，可以更改为其他对结点操作 */PreOrderTraverse（T->lchild）; /* 再先序遍历左子树 */PreOrderTraverse（T->rchild）; /* 最后先序遍历右子树 */}

假设我们现在有如图6-8-6这样一棵二叉树T。这树已经用二叉链表结构存储在内存当中。

图6-8-6

那么当调用PreOrderTraverse（T）函数时，我们来看看程序是如何运行的。

1．调用PreOrderTraverse（T），T根结点不为null，所以执行printf，打印字母A，如图6-8-7所示。

图6-8-7
2．调用PreOrderTraverse（T->lchild）;访问了A结点的左孩子，不为null，执行printf显示字母B，如图6-8-8所示。

图6-8-8

3．此时再次递归调用PreOrderTraverse（T->lchild）;访问了B结点的左孩子，执行printf显示字母D，如图6-8-9所示。

图6-8-9

4．再次递归调用PreOrderTraverse（T->lchild）;访问了D结点的左孩子，执行printf显示字母H，如图6-8-10所示。

图6-8-10

5．再次递归调用PreOrderTraverse（T->lchild）;访问了H结点的左孩子，此时因为H结点无左孩子，所以T==null，返回此函数，此时递归调用PreOrderTraverse（T->rchild）;访问了H结点的右孩子，printf显示字母K，如图6-8-11所示。

图6-8-11

6．再次递归调用PreOrderTraverse（T->lchild）;访问了K结点的左孩子，K结点无左孩子，返回，调用PreOrderTraverse（T->rchild）;访问了K结点的右孩子，也是null，返回。于是此函数执行完毕，返回到上一级递归的函数（即打印H结点时的函数），也执行完毕，返回到打印结点D时的函数，调用PreOrderTraverse（T->rchild）;访问了D结点的右孩子，不存在，返回到B结点，调用PreOrderTraverse（T->rchild）;找到了结点E，打印字母E，如图6-8-12所示。

图6-8-12

7．由于结点E没有左右孩子，返回打印结点B时的递归函数，递归执行完毕，返回到最初的PreOrderTraverse，调用PreOrderTraverse（T->rchild）;访问结点A的右孩子，打印字母C，如图6-8-13所示。

图6-8-13

8．之后类似前面的递归调用，依次继续打印F、I、G、J，步骤略。

综上，前序遍历这棵二叉树的节点顺序是：ABDHKECFIGJ。

6.8.4　中序遍历算法

那么二叉树的中序遍历算法是如何呢？哈哈，别以为很复杂，它和前序遍历算法仅仅只是代码的顺序上的差异。

    /* 二叉树的中序遍历递归算法 */void InOrderTraverse（BiTree T）{if（T==NULL）return;InOrderTraverse（T->lchild）; /* 中序遍历左子树 */printf（"%c",T->data）;/* 显示结点数据，可以更改为其他对结点操作 */InOrderTraverse（T->rchild）; /* 最后中序遍历右子树 */}

换句话说，它等于是把调用左孩子的递归函数提前了，就这么简单。我们来看看当调用InOrderTraverse（T）函数时，程序是如何运行的。

1．调用InOrderTraverse（T），T的根结点不为null，于是调用InOrderTraverse（T->lchild）;访问结点B。当前指针不为null，继续调用InOrderTraverse（T-> lchild）;访问结点D。不为null，继续调用InOrderTraverse（T->lchild）;访问结点H。继续调用InOrderTraverse（T->lchild）;访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H，如图6-8-14所示。

图6-8-14

2．然后调用InOrderTraverse（T->rchild）;访问结点H的右孩子K，因结点K无左孩子，所以打印K，如图6-8-15所示。

图6-8-15

3．因为结点K没有右孩子，所以返回。打印结点H函数执行完毕，返回。打印字母D，如图6-8-16所示。

图6-8-16

4．结点D无右孩子，此函数执行完毕，返回。打印字母B，如图6-8-17所示。

图6-8-17

5．调用InOrderTraverse（T->rchild）;访问结点B的右孩子E，因结点E无左孩子，所以打印E，如图6-8-18所示。

图6-8-18

6．结点E无右孩子，返回。结点B的递归函数执行完毕，返回到了最初我们调用InOrderTraverse的地方，打印字母A，如图6-8-19所示。

图6-8-19

7．再调用InOrderTraverse（T->rchild）;访问结点A的右孩子C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印F、C、G、J。步骤省略。

综上，中序遍历这棵二叉树的节点顺序是：HKDBEAIFCGJ。

6.8.5　后序遍历算法

那么同样的，后序遍历也就很容易想到应该如何写代码了。

    /* 二叉树的后序遍历递归算法 */void PostOrderTraverse（BiTree T）{if（T==NULL）return;PostOrderTraverse（T->lchild）; /* 先后序遍历左子树 */PostOrderTraverse（T->rchild）; /* 再后序遍历右子树 */printf（"%c",T->data）;/* 显示结点数据，可以更改为其他对结点操作 */}

如图6-8-20所示，后序遍历是先递归左子树，由根结点A→B→D→H，结点H无左孩子，再查看结点H的右孩子K，因为结点K无左右孩子，所以打印K，返回。

图6-8-20

最终，后序遍历的结点的顺序就是：KHDEBIFJGCA。同学们可以自己按照刚才的办法得出这个结果。

6.8.6　推导遍历结果

有一种题目为了考查你对二叉树遍历的掌握程度，是这样出题的。已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少？

对于这样的题目，如果真的完全理解了前中后序的原理，是不难的。

三种遍历都是从根结点开始，前序遍历是先打印再递归左和右。所以前序遍历序列为A BCDEF，第一个字母是A被打印出来，就说明A是根结点的数据。再由中序遍历序列是CBAEDF，可以知道C和B是A的左子树的结点，E、D、F是A的右子树的结点，如图6-8-21所示。

图6-8-21

然后我们看前序中的C和B，它的顺序是ABCDEF，是先打印B后打印C，所以B应该是A的左孩子，而C就只能是B的孩子，此时是左还是右孩子还不确定。再看中序序列是CBAEDF，C是在B的前面打印，这就说明C是B的左孩子，否则就是右孩子了，如图6-8-22所示。

图6-8-22

再看前序中的E、D、F，它的顺序是ABCDEF，那就意味着D是A结点的右孩子，E和F是D的子孙，注意，它们中有一个不一定是孩子，还有可能是孙子的。再来看中序序列是CBAEDF，由于E在D的左侧，而F在右侧，所以可以确定E是D的左孩子，F是D的右孩子。因此最终得到的二叉树是图6-8-23所示。

图6-8-23

为了避免推导中的失误，你最好在心中递归遍历，检查一下这棵树的前序和中序遍历序列是否与题目中的相同。

已经复原了二叉树，要获得它的后序遍历结果就是易如反掌，结果是CBEFDA。

但其实，如果同学们足够熟练，不用画这棵二叉树，也可以得到后序的结果，因为刚才判断了A结点是根结点，那么它在后序序列中，一定是最后一个。刚才推导出C是B的左孩子，而B是A的左孩子，那就意味着后序序列的前两位一定是CB。同样的办法也可以得到EFD这样的后序顺序，最终就自然的得到CBEFDA这样的序列，不用在草稿上画树状图了。

反过来，如果我们的题目是这样：二叉树的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。

这次简单点，由后序的BDCAFGE，得到E是根结点，因此前序首字母是E。

于是根据中序序列分为两棵树ABCD和FG，由后序序列的BDCAFGE，知道A是E的左孩子，前序序列目前分析为EA。

再由中序序列的ABCDEFG，知道BCD是A结点的右子孙，再由后序序列的BDCAFGE知道C结点是A结点的右孩子，前序序列目前分析得到EAC。

中序序列ABCDEFG，得到B是C的左孩子，D是C的右孩子，所以前序序列目前分析结果为EACBD。

由后序序列BDCAFGE，得到G是E的右孩子，于是F就是G的孩子。如果你是在考试时做这道题目，时间就是分数、名次、学历，那么你根本不需关心F是G的左还是右孩子，前序遍历序列的最终结果就是EACBDGF。

不过细细分析，根据中序序列ABCDEFG，是可以得出F是G的左孩子。

从这里我们也得到两个二叉树遍历的性质。

■　已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

■　已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

但要注意了，已知前序和后序遍历，是不能确定一棵二叉树的， 原因也很简单，比如前序序列是ABC，后序序列是CBA。我们可以确定A一定是根结点，但接下来，我们无法知道，哪个结点是左子树，哪个是右子树。这棵树可能有如图6-8-24所示的四种可能。

图6-8-24