# include<iostream.h>
# include<new.h>
# include<stdlib.h>
struct tree
{
char date;
tree *lchild;
tree *rchild;
};
struct stack
{
tree *base;
tree *top;
int tacksize;
};
void Initstack(stack S)
{
S.base=new tree[50];
S.top=S.base;
S.tacksize=50;
}
bool Push(stack &S,tree *&e)
{
if(S.top-S.base>=S.tacksize)
return false;
else
{
*S.top=*e;
S.top++;
cout<<S.top->date<<endl;
cout<<"ri"<<endl;
return true;
}
}
bool Pop(stack &S,tree *&e)
{
if(S.base==S.top)
return false;
S.top--;
*e=*S.top;
return true;
}
void CreatTree(tree *&T)
{
char ch;
cin>>ch;
if(ch=='#')T=NULL;
else
{
if(!(T=new tree)) exit(-1);
T->date=ch;
CreatTree(T->lchild);
CreatTree(T->rchild);
}
}
void PreOrde(tree *&T)
{
if(T)
{
cout<<T->date<<endl;
PreOrde(T->lchild);
PreOrde(T->rchild);
}
}
void InOrder(tree*&T)
{
if(T)
{
InOrder(T->lchild);
cout<<T->date<<endl;
InOrder(T->rchild);
}
}
void InOrdetrave(tree *T)
{
stack S;
tree *p;
p=T;
Initstack(S);
if(T)
{
while(p||Empty(S)==0)
{
if(p)
{
Push(S,p);p=p->lchild;
}
else
{
Pop(S,p);
cout<<p->date<<endl;
p=p->rchild;
}
}
}
}
int main()
{
tree *T;
CreatTree(T);
//PreOrde(T);
cout<<endl;
//PreOrdetrave(T);
cout<<endl;
//InOrder(T);
InOrdetrave(T);
cout<<endl;
return 0;
}