#include<stdio.h>
#include<malloc.h>
#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
typedef struct node{
    int data;
    node *lchild;
    node *rchild;

}bitree;
bitree *create1(){
    bitree *T;
    int c;
    scanf("%d",&c);
    if(c==0){
        T=NULL;
    }
    else{
        T=(bitree*)malloc(sizeof(bitree));
        T->data=c;
        T->lchild=create1();
        T->rchild=create1();
    }
    return T;
}
bitree *percreateTree(){
    bitree *T;
    int c;
    scanf("%d",&c);
    if(c==0){
        T=NULL;
    }
    else{
        T=(bitree*)malloc(sizeof(bitree));
        T->data=c;
        T->lchild=percreateTree();
        T->rchild=percreateTree();
    }
    return T;
}
void mid(bitree *T){//递归
    if(T!=NULL){
        mid(T->lchild);
        printf("%d",T->data);
        mid(T->rchild);
    }
}
void mid2(bitree *T){//非递归中序
    stack<bitree*> s;
    while(T!=NULL||!s.empty()){
        while(T){
            s.push(T);
            T=T->lchild;
        }
        if(!s.empty()){
            T=s.top();
            printf("%d",T->data);
            s.pop();
            T=T->rchild;
        }
    }

}
void  main(){
    bitree *T=create1();
    
    mid(T);
    mid2(T);
}