[数据结构]二叉树的前中后序遍历(递归+迭代实现)

主要的三种遍历方式

二叉树主要的遍历方式有前序遍历、中序遍历和后序遍历。
（1）前序遍历：根节点-->左子树-->右子树
（2）中序遍历：左子树-->根节点-->右子树
（3）后序遍历：左子树-->右子树-->根节点

其实还有一种比较基础的遍历方式是层次遍历，但是在本篇文章中不会涉及层次遍历的内容。

两种基础的实现方法

递归

以前序遍历为例，按照根节点-->左子树-->右子树的顺序遍历。先访问根节点，然后再分别对当前根节点的左子树和右子树重复同样的操作。中序遍历和后序遍历也都是类似的，由此可以看出二叉树遍历本身就具有递归的性质。

迭代

我们也可以用迭代的方式来实现递归的过程，递归本质上隐式地维护了一个栈，所以可以用栈这个结构来模拟整个二叉树遍历的过程。

---

前序遍历

前序遍历（递归）

递归实现前序遍历思路

我们只需要写一个递归函数来实现前序遍历。先考虑下递归函数停止递归的边界条件，很明显在遇到空指针NULL时，我们需要停止递归操作，此时直接return即可。
结合前序遍历的遍历顺序和上文中递归方法的图解，递归函数只需要先执行打印根节点数据的操作，然后再依次执行递归访问左子树、递归访问右子树就可以了。

假设递归函数名为 preorder，则顺序为:
（1）print(root->data)
（2）preorder(root->left)
（3）preorder(root->right)

递归实现前序遍历图解

以下为二叉树前序遍历实例的递归版图解

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

为了方便快速手写出二叉树前序遍历，我们可以形象地把前序遍历看作是一个小人以根节点为起点沿着二叉树的外围跑一圈，小人依次经过的节点就是前序遍历的结果。（重复经过的节点不再放入前序遍历结果序列中）

递归实现前序遍历代码

//前序 递归遍历二叉树
void Show_Pre_Order(BinaryTree root){
    if(root == NULL)
    	return;
    printf("%c ", root->data);
    Show_Pre_Order(root->leftchild);
    Show_Pre_Order(root->rightchild);
}

前序遍历（迭代）

迭代实现前序遍历思路

我们使用栈来模拟递归的过程，先定义一个遍历指针 t 并指向 root，栈用来存储当前遍历到的节点，整个过程用一个while循环来进行迭代。大致过程就是先打印当前节点数据，再一直往左走，边走边打印节点数据，同时将当前节点入栈，一直遍历到最左边的节点为止；然后取出栈顶节点，访问其右子树，再重复上述操作。
大致操作如下：
（1）打印节点数据；
（2）一直向左遍历，将节点入栈，并重复步骤（1），直到到达最左边；
（2）取栈顶节点，前往右子树，重复上述操作。

我们再来考虑停止迭代的边界条件，当 t 不为空指针NULL时，很显然需要访问当前 t 指向的节点；那么如果当前 t 为NULL，难道就可以退出循环吗？答案显然是否定的，例如当我们遍历到二叉树的某个叶子节点时，已经到达当前子树的最左边，转而前往右边，而此时右边也是NULL，那么此时 t 变为NULL，但是栈中还有节点未弹出，整个二叉树的前序遍历还没有完成。所以当栈不为空时，也要继续遍历。综上所述，停止迭代的边界条件为 t == NULL 并且 stack为空。

迭代实现前序遍历图解

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

（13）

（14）

（15）

迭代实现前序遍历代码

//利用栈前序遍历   STL stack
void Show_Pre_OrderII(BinaryTree root){
    stack<BinaryTree> s;
    BinaryTree t = root;
    while(t || !s.empty()){
        while(t){
	    printf("%c ", t->data);
	    s.push(t);
	    t = t->leftchild;	 //一直往左边走
        }
        t = s.top();
        s.pop();
        t = t->rightchild;	
    }
}

---

中序遍历

中序遍历（递归）

递归实现中序遍历思路

写一个递归函数，递归结束的边界条件很简单，也是遇到空指针NULL。
按照中序遍历的顺序，先递归访问左子树，再打印根节点数据，最后再递归访问右子树即可。

假设递归函数名为 infixorder，则顺序为:
（1）infixorder(root->left)
（2）print(root->data)
（3）infixorder(root->right)

递归实现中序遍历图解

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

中序遍历的结果同样也可以用一种方式来快速写出，将每个节点垂直下降至统一平面，得到的序列就是中序遍历的结果。

递归实现中序遍历代码

//中序 递归遍历二叉树
void Show_Infix_Order(BinaryTree root){
    if(root == NULL)
        return;
    Show_Infix_Order(root->leftchild);
    printf("%c ", root->data);
    Show_Infix_Order(root->rightchild);
}

中序遍历（迭代）

迭代实现中序遍历思路

同样使用栈来模拟递归的过程，先定义一个遍历指针 t 指向 root，栈用来存储当前遍历到的节点。大致过程就是先一直往左走，同时将当前节点入栈，一直遍历到最左边的节点为止；然后取出栈顶节点，打印节点数据，访问其右子树，再重复上述操作。可以看出迭代版中序遍历和前序遍历的思路只在打印数据的地方有一点差别。

大致操作如下：
（1）一直向左遍历，将节点入栈，直到到达最左边；
（2）取栈顶节点，打印节点数据；
（2）前往右子树，重复上述操作。

整个迭代的过程和前序遍历大致一致，只有打印数据位置不同，停止迭代的条件和前序遍历一样，也是 t == NULL 并且 stack为空。

迭代实现中序遍历图解

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

（13）

（14）

（15）

迭代实现中序遍历代码

//利用栈中序遍历   STL stack
void Show_Infix_OrderII(BinaryTree root){
    stack<BinaryTree> s;
    BinaryTree t = root;
    while(t || !s.empty()){
        while(t){
            s.push(t);
            t = t->leftchild;   //一直往左边走
        }
        t = s.top();	
        s.pop();  
        printf("%c ", t->data);         
        t = t->rightchild;       
    }
}

---

后序遍历

后序遍历（递归）

递归实现后序遍历思路

写一个递归函数，遇到空指针NULL结束递归。
按照后序遍历的顺序，先递归访问左子树，再递归访问右子树，最后打印根节点数据。

假设递归函数名为 postorder，则顺序为:
（1）postorder(root->left)
（2）postorder(root->right)
（3）print(root->data)

递归实现后序遍历图解

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

（11）

为了方便快速写出后序遍历的结果，可以将后序遍历看做是剪葡萄一样，将节点一个一个剪下。

递归实现后序遍历代码

//后序 递归遍历二叉树
void Show_Post_Order(BinaryTree root){
    if(root == NULL)
        return;
    Show_Post_Order(root->leftchild);
    Show_Post_Order(root->rightchild);
    printf("%c ", root->data);
}

后序遍历（迭代）

迭代实现后序遍历思路

后序遍历的迭代写法比前面的两种要稍微复杂一点，同样使用栈来模拟递归的过程，先定义一个遍历指针 t 指向 root，栈用来存储当前遍历到的节点。
同时还需要定义一个指针 last 标记上一次访问过的节点。
我们依旧需要先一直往左走，并且将走过的节点入栈，直到到达最左边。然后取出当前栈顶节点，讨论是否访问当前出栈节点。后序遍历的顺序是左子树-->右子树-->根节点，其实讨论的就是当前出栈的这个子树根节点是否能够被访问。当当前出栈节点的右子树为NULL时，则当前出栈节点可以访问，那么仅此一种情况吗？并不是，假如某个出栈子树的根节点，存在右子树，但是这个右子树已经遍历完毕了，那么也没有再访问右子树的需要，此时同样可以访问出栈节点。满足这个条件只会在左子树已经访问过并且右子树根节点为上一个访问过的节点情况下出现，所以我们只需要用一个 last 来记录当前访问过的节点就行了，为了防止出现死循环，还需要将 t 置NULL。如果这两个条件都不满足，那么当前出栈节点不能访问，需要重新入栈，并且转而访问右子树。

大致操作如下：
（1）一直向左遍历，将节点入栈，直到到达最左边；
（2）取栈顶节点，讨论是否可以访问当前出栈节点；
（3）如果 t == NULL 或者 t == last，则可以访问，并用 last 记录当前访问的节点，将 t 置NULL；
否则不能访问，将当前出栈节点重新入栈，转而前往右子树。

停止迭代的条件和前序遍历、中序遍历一样，也是 t == NULL 并且 stack为空。

迭代实现后序遍历图解

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

（13）

（14）

（15）

（16）

（17）

（18）

迭代实现后序遍历代码

//利用栈后序遍历   STL stack
void Show_Post_OrderII(BinaryTree root){
    stack<BinaryTree> s;
    BinaryTree t = root, last;
    while(t || !s.empty()){
        while(t){
            s.push(t);
            t = t->leftchild;    //先到达最左侧节点
        }
        t = s.top();
        s.pop();
        //如果当前节点无右子树或者右子树根节点为上一个访问过的节点
        if(!t->rightchild || t->rightchild == last){
            printf("%c ", t->data);
            last = t;            //记录当前访问过的节点
            t = NULL;
        }else{
            s.push(t);           //否则将当前节点重新入栈
            t = t->rightchild;   //转而前往其右子树
        }
    }
}

---

程序测试

完整程序代码

#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<iostream>
using namespace std;

typedef char Elemtype;
typedef struct BiNode{

    Elemtype data;
    struct BiNode *leftchild;       //左儿子
    struct BiNode *rightchild;      //右儿子

}Node, *BinaryTree;

//递归初始化二叉树 赋值二叉树
BinaryTree Create_BinaryTree(){
    Elemtype data;
    BinaryTree T;
    scanf("%c", &data);                     //输入节点数据
    getchar();

    if(data == '#')                         //输入#停止创建子树
        return NULL;  
    T = (BinaryTree)malloc(sizeof(Node));
    T->data = data;

    printf("输入 %c 的左子树数据: ", data);  //递归创建左子树
    T->leftchild = Create_BinaryTree();
    printf("输入 %c 的右子树数据: ", data);  //递归创建右子树
    T->rightchild = Create_BinaryTree();

    return T;
}

//前序 递归遍历二叉树
void Show_Pre_Order(BinaryTree root){
    if(root == NULL)
    	return;
    printf("%c ", root->data);
    Show_Pre_Order(root->leftchild);
    Show_Pre_Order(root->rightchild);
}

//中序 递归遍历二叉树
void Show_Infix_Order(BinaryTree root){
    if(root == NULL)
        return;
    Show_Infix_Order(root->leftchild);
    printf("%c ", root->data);
    Show_Infix_Order(root->rightchild);
}

//后序 递归遍历二叉树
void Show_Post_Order(BinaryTree root){
    if(root == NULL)
        return;
    Show_Post_Order(root->leftchild);
    Show_Post_Order(root->rightchild);
    printf("%c ", root->data);
}

//利用栈前序遍历   STL stack
void Show_Pre_OrderII(BinaryTree root){
    stack<BinaryTree> s;
    BinaryTree t = root;
    while(t || !s.empty()){
        while(t){
	    printf("%c ", t->data);
	    s.push(t);
	    t = t->leftchild;	 //一直往左边走
        }
        t = s.top();
        s.pop();
        t = t->rightchild;	
    }
}

//利用栈中序遍历   STL stack
void Show_Infix_OrderII(BinaryTree root){
    stack<BinaryTree> s;
    BinaryTree t = root;
    while(t || !s.empty()){
        while(t){
            s.push(t);
            t = t->leftchild;   //一直往左边走
        }
        t = s.top();	
        s.pop();  
        printf("%c ", t->data);         
        t = t->rightchild;       
    }
}

//利用栈后序遍历   STL stack
void Show_Post_OrderII(BinaryTree root){
    stack<BinaryTree> s;
    BinaryTree t = root, last;
    while(t || !s.empty()){
        while(t){
            s.push(t);
            t = t->leftchild;    //先到达最左侧节点
        }
        t = s.top();
        s.pop();
        //如果当前节点无右子树或者右子树根节点为上一个访问过的节点
        if(!t->rightchild || t->rightchild == last){
            printf("%c ", t->data);
            last = t;            //记录当前访问过的节点
            t = NULL;
        }else{
            s.push(t);           //否则将当前节点重新入栈
            t = t->rightchild;   //转而前往其右子树
        }
    }
}

int main(){
    BinaryTree T;
    printf("输入二叉树根节点数据: ");
    T = Create_BinaryTree();

    printf("\n先序遍历二叉树:\n");
    Show_Pre_Order(T);
    printf("\n");

    printf("\n中序遍历二叉树:\n");
    Show_Infix_Order(T);
    printf("\n");

    printf("\n后序遍历二叉树:\n");
    Show_Post_Order(T);
    printf("\n");

    printf("\n利用栈非递归前序遍历二叉树:\n");
    Show_Pre_OrderII(T);
    printf("\n");

    printf("\n利用栈非递归中序遍历二叉树:\n");
    Show_Infix_OrderII(T);
    printf("\n");

    printf("\n利用栈非递归后序遍历二叉树:\n");
    Show_Post_OrderII(T);
    printf("\n");
}

程序运行测试结果