二叉树迭代遍历(使用栈)

// 前序：根左右 1 2 4 5 3 6 7 
// 中序：左根右 4 2 5 1 6 3 7
// 后序：左右根 4 5 2 6 7 3 1
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {};
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};
};

void preTraversal(TreeNode *root) {
    if(!root) {
        return;
    }

    stack<TreeNode*> st;
    TreeNode *p = root;

    // 这里一定要判断堆是否为空，不然重复压入压出
    while(p || !st.empty()) {
        while (p)    
        {
            cout << p->val << " ";      // 中
            st.push(p);
            p = p->left;                // 左
        }

        if(!st.empty()) 
        {
            p = st.top();            
            st.pop();
            p = p->right;               // 右
        }    
    }
}

void InTraversal(TreeNode *root) {
    if(!root) {
        return;
    }

    TreeNode* p = root;
    stack<TreeNode*> st;

    while(p || !st.empty()) {
        while (p)    
        {
            st.push(p);
            p = p->left;                // 左
        }

        if(!st.empty()) 
        {
            p = st.top();
            st.pop();
            cout << p->val << " ";      // 中
            p = p->right;               // 右
            }    
    }
}

void BehTraversal(TreeNode *root) {
    if(!root) {
        return;
    }

    TreeNode* p = root;
    TreeNode* pre = nullptr;
    stack<TreeNode*> st;


    while(p || !st.empty()) {
        while(p)
        {
            st.push(p);
            p = p->left;                                // 左
        }

        if (!st.empty()) {
            p = st.top();                               // 右
            if (!p->right || pre == p->right) {
                cout << p->val << " ";
                st.pop();
                pre = p;
                p = nullptr;
            } else {
                p = p->right;
            }
        }    
    }
}


int main() {
    
    // 一种列表的初始化方式
    TreeNode* root = new TreeNode{1,
                                new TreeNode{2,
                                            new TreeNode{4,
                                                        new TreeNode{8},
                                                        new TreeNode{9},
                                            },
                                            new TreeNode{5,
                                                        new TreeNode{10},
                                                        new TreeNode{11},                                            
                                            },
                                },
                                new TreeNode{3,
                                            new TreeNode{6},
                                            new TreeNode{7},
                                },
    };

    std::cout << "前序遍历" << endl;
    preTraversal(root);
    cout << endl;
    
    cout << "中序遍历" << endl;
    InTraversal(root);
    cout << endl;

    cout << "后序遍历" << endl;
    BehTraversal(root);
    cout << endl;

    return 0;
}