#include <iostream>
#include <stack>
using namespace std;
struct Node{
char data;
Node * left;
Node * right;
};
void Create(Node * &root)
{
//qian xu jian li
char ch;
cin>>ch;
if(ch=='#')
{
root=NULL;
return;
}
root =new Node;
root->data=ch;
Create(root->left);
Create(root->right);
}
void PreOrder(Node * root)
{
if(root==NULL) return;
stack<Node * > s;
cout<<root->data;
s.push(root);
Node * p;
while(!s.empty())
{
while(s.top()->left)
{
s.push(s.top()->left);
cout<<s.top()->data;
}
while(!s.empty()&&!s.top()->right)
{
s.pop();
}
if(!s.empty())
{
p=s.top()->right;
s.pop();
cout<<p->data;
s.push(p);
}
}
}
void InOrder(Node * root)
{
if(root==NULL) return ;
stack<Node *> s;
s.push(root);Node * p;
while(!s.empty())
{
while(s.top()->left)
s.push(s.top()->left);
while(!s.empty()&&!s.top()->right)
{
cout<<s.top()->data;
s.pop();
}
if(!s.empty())
{
cout<<s.top()->data;
p=s.top()->right;
s.pop();
s.push(p);
}
}
}
struct A{
int tag;
Node * p;
};
void PostOrder(Node * root)
{
if(root==NULL) return;
A temp;
stack<A> s;
temp.tag=0;
temp.p=root;
s.push(temp);
while(!s.empty())
{
while(s.top().p->left)
{
temp.p=s.top().p->left;
s.push(temp);
}
while(!s.empty()&&(s.top().tag==1||s.top().p->right==NULL))
{
cout<<s.top().p->data;
s.pop();
}
if(!s.empty())
{
s.top().tag=1;
temp.p=s.top().p->right;
s.push(temp);
}
}
}
void main()
{
Node * root;
Create(root);
cout<<"PreOrder:\n";
PreOrder(root);
cout<<endl;
cout<<"InOrder:\n";
InOrder(root);
cout<<endl;
cout<<"PostOrder:\n";
PostOrder(root);
cout<<endl;
::system("pause");
}
