数据结构——二叉树问题中的前序，中序，后序排列_二叉树顺序存储结构的先序序列中序序列和后序序列

先序遍历：就是先访问树的根节点，再访问树的左子节点，再访问右子节点。

中序遍历：就是先访问树的左子节点，再访问树的根节点，再访问右子节点。

先序遍历：就是先访问树的左子节点，再访问树的右子节点，再访问根节点。

 

解题方式：已知先序和中序；已知后序和中序都可以确定唯一的一个二叉树

已知先序的时候由先序来确定根节点的位置；由中序的来确定左右子树的位置       （后序和中序同理来确定各自的位置）

1. 先序遍历

　　在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左子树子-右子树。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下：

void PreOrderTraversal(BinTree BT)
{
    if( BT ) 
    {
        printf(“%d\n”, BT->Data);        //对节点的数据进行打印          
        PreOrderTraversal(BT->Left);     //访问左子树
        PreOrderTraversal(BT->Right);    //访问右子树
    }
}

由递归代码可以看出，该递归为尾递归（在函数末尾或者说在函数即将返回前）。尾递归的递归调用需要用栈存储调用的信息，当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归，但是即使如此，我们不妨自己去除。非递归先序遍历算法基本思路：使用堆栈

　　a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；

　　b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右子树，继续a步骤；

　　c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。

　　实现代码如下：

void PreOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreatStack(MAX_SIZE);    //创建并初始化堆栈S
    while(T || !IsEmpty(S))
    {
        while(T)        //向左执行且沿途节点打印进入栈中 
        {
            printf("%d\n", T->Data);
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);    //节点弹出堆栈
            T = T->Right;  //转向右子树
        }
    }
}

2. 中序遍历

　　中序遍历的遍历路径与先序遍历完全一样。思路与先序遍历相似，其主要的不同点是访问节点顺序不同：中序遍历是访问完所有左子数后再访问根节点，最后访问右子树，即为左子树-根节点-右子树。

　　递归实现的代码如下:

void InOrderTraversal(BinTree BT)
{
    if(BT)
    {
        InOrderTraversal(BT->Left);
        printf("%d\n", BT->Data);
        InOrderTraversal(BT->Right);
    }
}

非递归形式代码如下：

void InOrderTraversal(BinTree BT)
{ 
    BinTree T = BT;
    Stack S = CreatStack(MaxSize); //创建并初始化堆栈S
    while(T || !IsEmpty(S))
　　{
    　　while(T)    //向左并将沿途节点压入堆栈
    　　{ 
       　　 Push(S,T);
        　　T = T->Left;
    　　}
    　　if(!IsEmpty(S))
    　　{
       　　 T = Pop(S);                //节点弹出堆栈
       　　 printf("%d\n", T->Data);    // 打印结点
      　　  T = T->Right;              //转向右子树
    　　}
　　}
}

3. 后序遍历

　　后序遍历与中序遍历，先序遍历的路径也完全一样。主要的不同点是后序遍历访问节点的顺序是先访问左子树和右子树，最后访问节点，即左子树-右子树-根节点。

　　递归实现思路与中序遍历和先序遍历相似，代码如下：

void PostOrderTraversal(BinTree BT)
{
    if (BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d\n", BT->Data);
    }
}

　

后序遍历的非递归实现

　　思路一：

　　　　对于一个节点而言，要实现访问顺序为左子树-右子树-根节点，可以利用先进后出的栈，在节点不为空的前提下，依次将根节点，右子树，左子树压栈。故我们需要按照根节点-右子树-左子树的顺序遍历树，而我们已经知道先序遍历的顺序是根节点-左子树-右子树，故只需将先序遍历的左右调换并把访问方式打印改为压入另一个栈即可。最后一起打印栈中的元素。代码如下：

void PostOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S1 = CreatStack(MAX_SIZE);    //创建并初始化堆栈S1
    Stack S2 = CreatStack(MAX_SIZE);    //创建并初始化堆栈S2   
    while(T || !IsEmpty(S1))
    {
        while(T)        //沿途节点访问（压入S2）后压入堆栈S1 
        {
            Push(S2, T);
            Push(S1, T);
            T = T->Right;
        }
        if (!IsEmpty(S1))
        {
            T = Pop(S1);    //弹出堆栈
            T = T->Left;  //转向左子树
        }
    }
    while(!IsEmpty(S2))    //打印S2中元素
    {
        T = Pop(S2);
        printf("%d\n", T->Data);
    }          
}

优点：利用了先序遍历的思想，代码较简洁，思路较清晰。缺点是需要用一个栈来存储树的所有节点，空间占用较大。

 

思路二：

　　　　要访问一个节点的条件上一个访问的节点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作。

　若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；

　若Prev是Curr的左儿子，则将Curr的右儿子压入栈；

　否则Prev是Curr的右儿子，访问Curr;

　　　　代码如下:

void PostOrderTraversal(BinTree BT)
{
    if(BT == NULL)
        return ;
    Stack S = CreatStack(MAX_SIZE);        
    BinTree Prev = NULL , Curr = NULL;     //初始化
    s.push(BT);
    while(!IsEmpty(S))
    {
        Curr = Top(S);        //将栈顶元素赋给Curr
        if(Prev == NULL  || Prev->Left == Curr || Prev->Right == Curr) 
                                       //若Prev为NULL或是Curr的父节点
        {
            if(Curr->Left != NULL)
                Push(S, Curr->Left);
            else if(Curr->Right != NULL)
                Push(S, Curr->Right);
        }
        else if(Curr->Left == Prev)    //若Prev是Curr的左子树
        {
            if(Curr->Right != NULL)
                Push(S, Curr->Right);
        }
        else
        {
            printf("%d\n", Curr->Data);    //访问当前节点
            Pop(S);    //访问后弹出
        }
        Prev = Curr;    //处理完当前节点后将Curr节点变为Prev节点
    }
}