#include<bits/stdc++.h>
using namespace std;
typedef struct binode{
    char data;
    struct binode *lchild,*rchild;
}binode,*bitree;
bitree T;
typedef struct stacknode{
    bitree data;
    struct stacknode *next;
}stacknode,*linkstack;
linkstack st,p;
//ABD##E##CF#G###
void initstack(linkstack &st){
    st=NULL;
    return ;
}
void push(linkstack &st,bitree e)
{
    p=new stacknode;
    p->data=e;
    p->next=st;
    st=p;
    return ;
}
void pop(linkstack &st,bitree &e){
    if(st==NULL){
        cout<<"栈内元素为空,删除无效"<<endl;
        return ;
    }
    e=st->data;
    p=st;
    st=st->next;
    free(p);
    return;
}
bitree gettop(linkstack st){
    if(st!=NULL)    return st->data;
}
bool stack_empty(linkstack st){
    if(st==NULL) return 1;
    return 0;
}
void creatbitree(bitree &T){
    char c;
    cin>>c;
    if(c=='#') T=NULL;
    else {
        T=new binode;
        T->data=c;
        creatbitree(T->lchild);
        creatbitree(T->rchild);
    }
}
void preorderdfs(bitree T){
    if(T==NULL) return ;
    else {
        cout<<T->data<<" ";
        preorderdfs(T->lchild);
        preorderdfs(T->rchild);
    }
}
void inorderdfs(bitree T){
    if(T==NULL) return ;
    else {
        inorderdfs(T->lchild);
        cout<<T->data<<" ";
        inorderdfs(T->rchild);
    }
}
void postorderdfs(bitree T){
    if(T==NULL) return ;
    else {
        postorderdfs(T->lchild);
        postorderdfs(T->rchild);
        cout<<T->data<<" ";
    }

}
void preorder(bitree T){
    linkstack stpre;
    initstack(stpre);
    bitree t1,q;
    t1=T;
    q=new binode;
    while(t1||!stack_empty(stpre)){
        if(t1){
            push(stpre,t1);
            cout<<t1->data<<" ";
            t1=t1->lchild;
        }
        else {
            pop(stpre,q);
            t1=q->rchild;
        }
    }
}

void inorder(bitree T){
    linkstack stin;
    initstack(stin);
    bitree p,q;
    p=T;
    q=new binode;
    while(p||!stack_empty(stin)){
        if(p){
            push(stin,p);
            p=p->lchild;
        }
        else {
            pop(stin,q);
            cout<<q->data<<" ";
            p=q->rchild;
        }
    }
}

void postorder(bitree T){//只有当一个根节点的左右孩子节点都访问过后才能访问当前根节点
    linkstack stpost;
    initstack(stpost);
    bitree p,q,mark;
    p=T;
    q=new binode;
    while(p||!stack_empty(stpost)){
        mark=NULL;
		if(p){//一直往下搜索，直到全部的左端点入栈 
            push(stpost,p);
            p=p->lchild;
        }
        else {
        	while(!stack_empty(stpost)){
        		pop(stpost,q);
				if(q->rchild==mark){//判断当前的节点的右孩子是否为空或者是否访问过，为空的话直接访问并且记录一下
				//如果说上次访问的节点是当前节点的右孩子，那么当前节点的左右孩子都被访问过了，可以访问当前节点。 
					cout<<q->data<<" ";
					mark=q;
				}
				else {//否则的话不能访问当前节点，再依当前节点为根节点去找访问当前节点的左孩子。 
					push(stpost,q);
					p=q->rchild;
					break;
				}
			}
        	
		}
        
    }   
}
int main()
{
    //创建二叉树
    creatbitree(T);
    int x;
    cin>>x;
    if(x==0){	
	    cout<<"递归先序遍历"<<endl;
		preorderdfs(T);
		cout<<endl<<endl;;
	    cout<<"递归中序遍历"<<endl;
		inorderdfs(T);
		cout<<endl<<endl;
		cout<<"递归后序遍历"<<endl;
	    postorderdfs(T);
	}
	else {
		cout<<"非递归先序遍历"<<endl;
		preorder(T);
		cout<<endl<<endl;
		cout<<"非递归中序遍历"<<endl;
		inorder(T);
		cout<<endl<<endl;
		cout<<"非递归后序遍历"<<endl;
		postorder(T);
	}
    return 0;
}