二叉树的 前中后序的非递归遍历

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct Tree{
    int a[50]={0, 1, 2, 3, 4, -1, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1};
    void BT(int u=1){
        cout<<a[u]<<endl;
        if(a[u*2]!=-1){
            BT(u*2);
        }
        if(a[u*2+1]!=-1){
            BT(u*2+1);
        }
    }
    void DFS1(int root){
        cout<<"前序遍历:"<<endl;
        stack<int> st;
        while(a[root]!=-1||!st.empty()){
            while(a[root]!=-1){
                cout<<a[root]<<endl;
                st.push(root);
                root*=2;
            }
            if(st.size()){
                root=st.top(); st.pop();
                root=root*2+1;
            }
        }
    }
    void DFS2(int root){
        cout<<"中序遍历:"<<endl;
        stack<int> st;
        while(a[root]!=-1||!st.empty()){
            while(a[root]!=-1){
                st.push(root);
                root*=2;
            }
            if(st.size()){
                root=st.top(); st.pop();
                cout<<a[root]<<endl;
                root=root*2+1;
            }
        }
    }
    /*
    而二叉树的后序非递归遍历就比较难写，因为涉及到判断节点的访问状态…

    现在有个很巧妙的方法：

    前序：根->左->右
    后序：左->右->根

    那么可以把后序当作：根->右->左，然后再反转一下即可。
    */
    void DFS3(int root){
        cout<<"后序遍历:"<<endl;
        stack<int> st;
        list<int> lst;
        while(a[root]!=-1||!st.empty()){
            while(a[root]!=-1){
                lst.push_back(a[root]);
                st.push(root);
                root=root*2+1;
            }
            if(st.size()){
                root=st.top(); st.pop();
                root*=2;
            }
        }
        lst.reverse();
        for(auto x: lst){
            cout<<x<<endl;
        }
    }
};

stack<int> st;
int main(){

    //BT(1);
    Tree b;
    b.DFS1(1);
    b.DFS2(1);
    b.DFS3(1);

    return 0;
}