二叉树的周游

1.什么是二叉树的周游

二叉树的周游是一种按某种方式系统地访问二叉树中所有节点的过程，使每个节点都被访问一次且只被访问一次。通过一次周游，可使二叉树中所有节点按照某种（线性）序列进行一次处理。

2.周游的分类

周游方法可以分为两大类：一类是深度优先周游，另一类是广度优先周游。下面分别对两种周游方式进行讨论。

深度优先周游

我们规定在二叉树的周游过程中只能先左后右，那么就存在三种周游次序，先根次序（前序）、中根次序（中序）、后根次序（后序）。

以下图的一颗二叉树为例：

二叉树

• 先根次序

若二叉树不空，则先访问根；然后按先根次序访问左子树；最后按先根次序访问又子树。

对于上图的二叉树采用先根次序周游产生的结点序列为：
A,B,D,C,E,G,F,H,I
通常将按照先根次序周游得到的结点序列称之为这棵二叉树的先根序列。

• 中根序列

若二叉树不空，则先按对称序周游左子树；然后访问根；最后按对称序周游右子树。

对于上图的二叉树采用中根次序周游产生的结点序列为：
D,B,A,E,G,C,H,F,I
通常按照中根次序周游得到的结点序列称之为这棵二叉树的中根（对称）序列。

• 后根序列

若二叉树不空，则先按后根次序周游左子树；然后按后根次序周游右子树；最后访问根。

对于上图的二叉树采用后根次序周游产生的结点序列为：
D,B,G,E,H,I,F,C,A
通常按照后根次序周游得到的结点序列称之为这棵二叉树的后根序列。

广度优先周游

根据广度优先周游的思想，我们可以想到用一个队列来实现二叉树的广度优先周游，其思想是：先将非空二叉树放入队列中然后从队首取出访问，每当从队首取出元素时，将队首的非空左右子树依次送入队尾，反复上述操作直至队列为空，则完成了一棵二叉树的广度优先周游。
以上述的例子采用广度优先算法产生的结点序列为：
A,B,C,D,E,F,G,H,I
下面给出算法的C语言伪代码：

void levelOrder(BinTree t)
{
    BinTree c,cc;//抽象二叉树类型
    Queue queue = createEmptyQueue();//创建一个空队列用来存放待周游的二叉树
    if(t==NULL)
    {
        return;
    }
    enQueue(t,queue);//将二叉树放入队列中
    while(!isEmptyQueue(queue))
    {
        c = frontQueue(queue);//取队首元素
        deleteQueue(queue);//删除队首元素
        visit(root(c));//访问队首二叉树的根结点
        cc = leftChild(c);//左子树
        if(cc!=NULL)
        {
            enQueue(cc);//左子树非空放入队尾
        }
        cc = rightChild(c);//右子树
        if(cc!=NULL)
        {
            enQueue(cc);//右子树非空放入队尾
        }
    }
}

3.根据周游产生的结点序列确定一棵二叉树

很多公司的笔试题中常考的一道题就是给出一棵二叉树的两种周游次序产生的结点序列（其中一定包含先根序列）然后让你求出第三种周游方式产生的结点序列。

• 一个例子：
  一棵二叉树的前序遍历的结点顺序为：ABDEGCF；中序遍历结点顺序为：DBEGAFC；那么后续遍历结点的顺序为：（B）
  A.DEGBCFA
  B.DGEBFCA
  C.DBEGFCA
  D.DGEBAFC

我们来看看这道题目，其中的考点就是二叉树深度优先的三种周游顺序，通过两种周游顺序产生的结点序列还原二叉树从而得到另外一种周游顺序产生的结点序列。

• 以下为解题过程：
  首选我们来看题目中给出了前序（先根）结点序列，通过这个结点序列可以知道这棵二叉树的根结点为A，那么由中序遍历得到的结点序列可知，在A左边的为左子树遍历序列，A右边的为右子树遍历序列。
  那么我们先看右子树，中序遍历得到的结点序列为FC那么我们可以得到一棵这样的右子树：
  右子树
  再看左子树，左子树中有四个结点，但是由先根序列可知左子树的根结点为B，那么我们有可以重复上面的步骤，将B得左右结点序列划分为左右子树结点。
  因为B的左子树为D，而且D为中序遍历的第一个结点，D为B的左孩子，此时二叉树的左右两边如下图：
  左右子树
  我们再来看B的右边，其中序遍历结点序列为EG，而从前序遍历的结果来看E在G之前，所以E是G的根，综上所述可以确定E是B的右子树且有一个右孩子。
  此时二叉树的左右子树如下图：
  加入E,G后的左右子树
  在结合上面所说A结点是整棵二叉树的根结点，所以还原以后的二叉树如下图：
  还原后的二叉树

通过对这棵二叉树的观察，我们可以知道，其后序遍历产生的结点序列为：DGEBFCA，所以题目的答案为B。

4.小结

数据结构与算法是开发类笔试中必考的内容，二叉树又是常考的知识点，其中的一些常见算法和概念非常重要，在此列举了一个小例子希望能帮到大家，如有出错请大家指正。