二叉树的遍历-先序、中序、后序、层次_层次序列是先序序列吗

       二叉树的遍历，就是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

       遍历一棵二叉树便要决定对根结点N，左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序(NLR)、中序(LNR)、后序(LRN)三种遍历算法，其中的序是指根结点在何时被访问。

一、先序遍历

先序遍历(PreOrder)的操作过程如下：

若二叉树为空，则什么也不做；否则：

1）访问根结点；

2）先序遍历左子树；

3）先序遍历右子树。

 

对应的递归算法如下：      

void PreOrder(BiTree T)
{
    if(T!=NULL)
    {
        visit(T);                      //访问根结点
        PreOrder(T->lchild);           //递归遍历左子树
        PreOrder(T->rchild);           //递归遍历右子树
    }
}

 

上图先序遍历得到的结果为1,2,4,6,3,5。

注意：这里提供的是伪代码的形式，主要是明白遍历思想，具体要结合实际问题实际分析，下同。

 

二、中序遍历

中序遍历(InOrder)的操作过程如下：

若二叉树为空，则什么也不做；否则，

1）中序遍历左子树；

2）访问根结点；

3）中序遍历右子树。

 

对应的递归算法如下：    

void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);  //递归遍历左子树
        visit(T);            //访问根结点
        InOrder(T->rchild);  //递归遍历右子树
    }
}

又是这个图，其中序遍历得到的结果为2,6,4,1,3,5。

这里可能不太好理解，分步列一下：

（1）进入结点1左子树；

（2）进入结点2左子树，为空，结点2左子树访问完毕，返回结点2；

（3）访问结点2，访问顺序为2；

（4）进入结点2右子树；

（5）进入结点4左子树；

（6）进入结点6左子树，为空，返回结点6；

（7）访问结点6，访问顺序为2,6；

（8）进入结点6右子树，为空，返回结点6，结点4左子树访问完毕，返回结点4；

（9）访问结点4，访问顺序为2,6,4；

（10）进入结点4右子树，为空，返回结点4，结点2右子树访问完毕，返回结点1；

（11）访问根结点1，访问顺序为2,6,4,1；

右子树的访问思路同上。

 

三、后序遍历

后序遍历(PostOrder)的操作过程如下：

若二叉树为空，则什么也不做；否则，

1）后序遍历左子树；

2）后序遍历右子树；

3）访问根结点。

 

对应的递归算法如下：    

void PostOrder(BiTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->lchild);         //递归遍历左子树
        PostOrder(T->rchild);         //递归遍历右子树
        visit(T);                     //访问根结点
    }
}

还是这个图，后序遍历得到的结果为6,4,2,5,3,1

这个应该还是比较好理解的。

       三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。

 

四、递归算法和非递归算法的转换

       借助栈，我们可以将二叉树的递归遍历算法转换为非递归算法。以中序遍历为例，先扫描根结点的所有左结点并将它们一一进栈，然后出栈一个结点*p，访问它，然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。

       中序遍历的非递归算法如下：   

void InOrder2(BiTree T)
{                                //二叉树中序遍历的非递归算法需要借助一个栈
    InitStack(S);                       
    BiTree p=T;                  //初始化栈；p是遍历指针
    while(p||!IsEmpty(S))        //栈不空或p不空时循环
    {
        if(P)                    //根指针进栈，遍历左子树
        {
            Push(S,p);           //每遇到非空二叉树先向左走
            p=p->lchild;        
        }
        else                     //根指针退栈，访问根结点，遍历右子树
        {
            Pop(S,p);            //退栈，访问根结点
            visit(p);                
            p=p->rchild;         //再向右子树走
        }
    }
}

非递归算法的效率肯定比递归算法的效率高滴！

 

 

五、层次遍历

       层次遍历顾名思义就是对每一层都进行遍历，如下图所示：

 

       要进行层次遍历需要一个队列。先将二叉树根结点入队，然后出队，访问该结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列空。

       二叉树层次遍历算法如下：     

void LevelOrder(BiTree T)
{
    InitQueue(Q);                     //初始化辅助队列
    BiTree p;       
    EnQueue(Q,T);                     //将根结点入队
    while(!IsEmpty(Q))                //队列不空循环
    {
        DeQueue(Q,p);                 //队头元素出队
        visit(p);                     //访问当前p所指向结点
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);     //左子树不空，则左子树入队列
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);     //右子树不空，则右子树入队列
    }
}

 

六、由遍历序列构造二叉树

       由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。

       由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。

       由二叉树的层次序列和中序序列也可以唯一地确定一棵二叉树。

       这告诉我们一个道理：想要利用遍历序列构造二叉树，中序序列必不可少！！