#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{         
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T){
    char ch;
    ch=getchar();
    if(ch=='#')
T=NULL;
    else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
    printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
    }
    return T;
}
void Preorder(BiTree T){       
     if(T){
 printf("%c",T->data);
 Preorder(T->lchild);
 Preorder(T->rchild);
}
}

void zhongxu(BiTree T){     
    if(T){
zhongxu(T->lchild);
printf("%c",T->data);
zhongxu(T->rchild);
}
}
void houxu(BiTree T){      
    if(T){
houxu(T->lchild);
houxu(T->rchild);
printf("%c",T->data);
}
}

void conver(BiTree T)  
{BiTree p;
if(T)
{
    p=T->lchild;
    T->lchild=T->rchild;
    T->rchild=p;
    printf("%c",T->data);
    conver(T->lchild);
    conver(T->rchild);
}
}

main(){
    BiTree T;
    int sum,dep;
    T=Create(T);
    Preorder(T);
    printf("\n");
    zhongxu(T);
    printf("\n");
    houxu(T);
    printf("\n");
    conver(T);
    printf("\n");
    
}