#include<iostream> 
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

struct Tree{
    int x;
    Tree *lchild, *rchild;
    Tree(){
        lchild = rchild = NULL;
    }
};

typedef Tree* pT;

void buildT(pT &T){
    int n;
    cin>>n;
    if(n==-1)
        return;
    T = new Tree();
    T->x = n;
    buildT(T->lchild);
    buildT(T->rchild);
}
/**************************************************************************/ 
/*
     非递归先序遍历: 对于任一结点P：

     1)访问结点P，并将结点P入栈;

     2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，
　　　　循环至1); 若不为空，则将P的左孩子置为当前的结点P;

     3)直到P为NULL并且栈为空，则遍历结束。
*/ 
void preOrderNorecursive(pT T){
    stack<pT> s;
    s.push(T);
    while(!s.empty()){
        while(T != NULL){//左子树走到尽头 
            cout<<T->x<<" ";
            T = T->lchild;
            s.push(T);
        }
        s.pop();//清除空指针
        if(!s.empty()) {
            T = s.top();
            s.pop();
            s.push(T=T->rchild);//右子树走起 
        }
    }
}

void preOrderOutT(pT T){
    if(T){
        cout<<T->x<<" ";
        preOrderOutT(T->lchild);
        preOrderOutT(T->rchild);
    }
}

/**************************************************************************/ 
/*
   非递归中序遍历：对于任一结点P，

  1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；

  2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；

  3)直到P为NULL并且栈为空则遍历结束
*/ 
void inOrderNorecursive(pT T){
    stack<pT> s;
    s.push(T);
    while(!s.empty()){
         while(T!=NULL)//左子树走到尽头 
             s.push(T=T->lchild);
         s.pop();//清除空指针
         if(!s.empty()) {
             T = s.top();
             s.pop();
             cout<<T->x<<" ";
             s.push(T = T->rchild);//访问右子树 
         }
    }
}

void inOrderOutT(pT T){
    if(T){
        inOrderOutT(T->lchild);
        cout<<T->x<<" ";
        inOrderOutT(T->rchild);
    }
}

/**************************************************************************/ 
/*
    非递归后序遍历： 
        要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
    如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子
    都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，
    这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
*/ 
void postOrderNorecursive(pT T){
    stack<pT> s;
    s.push(T);
    pT pre = NULL;//后序遍历之前输出的节点 
    while(!s.empty()){
        T = s.top();
        if(T->lchild==NULL && T->rchild==NULL ||
           (pre!=NULL && (T->lchild==pre || T->rchild==pre)) {
           cout<<T->x<<" ";
           pre = T;
           s.pop();
        } else {//依次将右子树和左子树放入栈中 
            if(T->rchild)
                s.push(T->rchild);
            if(T->lchild)
                s.push(T->lchild);
        }
    }
}

void postOrderOutT(pT T){
    if(T){
        postOrderOutT(T->lchild);
        postOrderOutT(T->rchild);
        cout<<T->x<<" ";
    }
}
/**************************************************************************/ 

int main(){
    pT T = NULL;
    buildT(T);
    /**************************************************************************/ 
    cout<<"递归先序遍历:"<<endl;
    preOrderOutT(T);
    cout<<endl;
    cout<<"非递归先序遍历:"<<endl;
    preOrderNorecursive(T);
    cout<<endl;
    /**************************************************************************/ 
    cout<<"递归中序遍历:"<<endl;
    inOrderOutT(T);
    cout<<endl;
    cout<<"非递归中序遍历:"<<endl;
    inOrderNorecursive(T);
    cout<<endl;
    /**************************************************************************/ 
    cout<<"递归后序遍历:"<<endl;
    postOrderOutT(T);
    cout<<endl;
    cout<<"非递归后序遍历:"<<endl;
    postOrderNorecursive(T);
    cout<<endl;
    /**************************************************************************/ 
    return 0;
}
/*

1 2 2 -1 -1 4 7 -1 -1 -1 3 4 -1 8 -1 -1 5 -1 -1
递归先序遍历:
1 2 2 4 7 3 4 8 5
非递归先序遍历:
1 2 2 4 7 3 4 8 5
递归中序遍历:
2 2 7 4 1 4 8 3 5
非递归中序遍历:
2 2 7 4 1 4 8 3 5
递归后序遍历:
2 7 4 2 8 4 5 3 1
非递归后序遍历:
2 7 4 2 8 4 5 3 1

*/