#include<bits/stdc++.h>
using namespace std;
typedef struct binode{
    char data;
    struct binode *lchild,*rchild;
}binode,*bitree;
bitree T;
typedef struct stacknode{
    char data;
    struct stacknode *next;
}stacknode,*linkstack;
linkstack st,p;
void initstack(linkstack &st){
    st=NULL;
    return ;
}
void push(linkstack &st,char e)
{
    p=new stacknode;
    p->data=e;
    p->next=st;
    st=p;
    return ;
}
void pop(linkstack &st,char &e){
    if(st==NULL){
        cout<<"栈内元素为空,删除无效"<<endl;
        return ;
    }
    e=st->data;
    p=st;
    st=st->next;
    free(p);
    return;
}
char gettop(linkstack st){
    if(st!=NULL)    return st->data;
}
//ABD##E##CF#G###
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<<" ";
    }

}







int main()
{
    //创建二叉树
    creatbitree(T);
//    preorderdfs(T);
//    inorderdfs(T);
//    postorderdfs(T);



    return 0;
}
