二叉树的三种遍历(前序/中序/后序)

参考博客

/*
* 二叉树的先序遍历 --- 非递归版与递归版
*/


#include <iostream>
#include <stack>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left, *right;
    TreeNode(int v = 0) : val(v), left(NULL), right(NULL){}
};

void visit(TreeNode* p){ //访问函数,这里简单只设为是打印
    cout << p->val << " ";
}

/*******************************************
*               前序遍历
********************************************/
void BT_PreOrder(TreeNode* root){
    if(root == NULL) return;
    stack<TreeNode*> S;
    S.push(root);

    while(!S.empty()){
        TreeNode* cur = S.top();
        S.pop();
        visit(cur); //访问
        if(cur->right) S.push(cur->right);
        if(cur->left) S.push(cur->left);
    }
    return;
}


/*******************************************
*               中序遍历
********************************************/
void BT_InOrder(TreeNode *root){
    stack<TreeNode* > S;
    TreeNode *cur = root;
    while(true){
        while(cur){
            S.push(cur); cur = cur->left;
        }
        if(S.empty()) break;

        cur = S.top();
        visit(cur);
        S.pop();
        cur = cur->right;
    }
}

/*******************************************
*               后序遍历
********************************************/

void findFirst(stack<TreeNode*> &S); //找到以栈顶节点为根的子树其第一个应该输出的节点   
 //即按照自己-右节点-左节点的顺序压栈

void BT_PostOrder(TreeNode* root){
    if(root == NULL) return;
    
    stack<TreeNode *> S;
    TreeNode *cur = root;
    S.push(root);
    while(!S.empty()){
        if(S.top()->left != cur && S.top()->right != cur){ //当前节点不是栈顶节点的子节点
        //这里的当前节点指的是上一个输出的节点
        //这种关系表示上一个输出节点是左节点,而栈顶是右节点,因为右节点可能有未输出的子树,因此需要进行FindFirst的操作
            findFirst(S); 
        }
        visit(cur = S.top());
        S.pop();
    }
    
}
void findFirst(stack<TreeNode*> &S) {
    //找到以栈顶节点为根的子树其第一个应该输出的节点
    while (TreeNode* x = S.top()) {
        if (x->left) { //一句话总结,有左先右再左,无左只压右
            if (x->right) S.push(x->right);
            S.push(x->left);
        }
        else {
            S.push(x->right);
        }
    }
    S.pop(); //删掉栈顶的空指针
}

//前序遍历的递归定义：先根节点，后左子树，再右子树。
//首先，我们遍历左子树，边遍历边打印，并把根节点存入栈中，以后需借助这些节点进入右子树开启新一轮的循环。
void my_pre(TreeNode* root){
    if(root == NULL)
        return;
    TreeNode* p = root;
    stack<TreeNode*> s;
    while(p||!s.empty()){
        while(p){
            visit(p);
            s.push(p);
            p=p->left;
        }
        if(!s.empty()){
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

void my_in(TreeNode* root){
    if(root == NULL)
        return;
    TreeNode* p = root;
    stack<TreeNode*> s;
    while(p||!s.empty()){
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中 
        if(p){
            s.push(p);
            p=p->left;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        else{
            p = s.top();
            s.pop();
            visit(p);
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)  
            p = p->right;
        }
    }
}

/*
0
|
+ 2 ----- 6
|   +---- 5 ---- 10
|         + ---- 9
+ 1 ----- 4 ---- 8
          + ---- 7
    +---- 3       
*/

int main(){
    TreeNode n0(0), n1(1), n2(2), n3(3), n4(4),n5(5), n6(6), n7(7),n8(8), n9(9),n10(10);
    n0.left = &n1; n0.right = &n2;
    n1.left = &n3; n1.right = &n4;
    n2.left = &n5; n2.right = &n6;
    n4.left = &n7; n4.right = &n8;
    n5.left = &n9; n5.right = &n10;

    BT_PreOrder(&n0);
    cout << endl;
    my_pre(&n0);
    cout << endl;

    BT_InOrder(&n0);
    cout << endl;
    my_in(&n0);
    cout << endl;

    BT_PostOrder(&n0);
    cout << endl;
}

二叉树的非递归后续遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> result;
        TreeNode* p = root; 
        TreeNode* q = nullptr;  //用来保存刚访问过的节点
        do{
            while(p!=nullptr){    //往左下走到底
                s.push(p);
                p = p->left;
            }
            q = nullptr;
            while(!s.empty()){
                p = s.top();
                s.pop();
                if(p->right == q){    //p为左孩子或者说是可以访问的父节点（右子树已被访问）
                    result.push_back(p->val);
                    q = p;  // 保存刚刚访问过的节点
                }
                else {  //  当前节点不能访问，需要第二次进栈
                    s.push(p);
                    p = p->right; //先处理右子树
                    break;
                }
            }
            
            
        }while(!s.empty());
        return result;
    
    }
};