【二叉树的遍历】

二叉树的遍历

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

二叉树的遍历一般分为先序遍历，中序遍历，后序遍历和层次遍历。我们先来讲讲什么是先序遍历。

1. 先序遍历（PreOrder）: 若二叉树为空，则什么都不做，否则：

   （1）访问根节点；

   （2）先序遍历左子树；

   （3）先序遍历右子树。

   递归算法如下：

   void PreOrder(BiTree T){
       if(T!=NULL){
           visit(T); //访问根节点
           PreOrder(T->lchild);//递归遍历左子树
           PreOrder(T->rchild);//递归遍历右子树
       }
   }
   1
   2
   3
   4
   5
   6
   7

2. 中序遍历（InOrder）：若二叉树为空，则什么也不做；否则，

   （1）中序遍历左子树；

   （2）访问根节点；

   （3）中序遍历右子树。

   相应的递归算法如下：

   void InOrder(BiTree T){
       if (T!=NULL){
           InOrder(T->lchild);
           visit(T);
           InOrder(T->rchild);
       }
   }
   1
   2
   3
   4
   5
   6
   7

3. 后序遍历（PostOrder）:若二叉树为空，则什么也不做；否则，

   （1）后序遍历左子树；

   （2）后序遍历右子树；

   （3）访问根节点；

后序遍历递归算法如下：

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);//访问左子树
        PostOrder(T->rchild);//访问右子树
        visit(T);//访问根节点
    }
}
1
2
3
4
5
6
7

上面三种遍历算法中，递归遍历左子树、右子树的顺序是固定的，只是访问根节点的顺序不同。上述三种遍历算法的时间复杂度都为O(n)。

在递归遍历中，递归工作栈的深度为二叉树的深度，因此在最坏的情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)。

4. 层次遍历

   层次遍历的规则是若树为空，则什么也不做，否则从树的第一层，也就是根结点开始访问，从上到下逐层遍历，在同一层中，按照从左到右的顺序对每个结点依次访问。

5. 由遍历序列构造二叉树

   • 由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
   • 由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
   • 由二叉树的层次序列和中序序列也可以唯一地确定一棵二叉树。
   • 只知道二叉树的先序序列和后序序列则无法唯一地确定一棵二叉树。