#include <iostream>
using namespace std;
struct bitree
{
char data;
bitree *lchild;
bitree *rchild;
};

bitree *create()      //构造树
{
char ch;
cout<<"请输入节点(结束时用#表示):"<<endl;
cin>>ch;
bitree *root,*p,*s[100];
int front=1;
   
while(ch!='#')
{
      p=NULL;
   
  
    p=new bitree;
    p->data=ch;
       p->lchild=NULL;
    p->rchild=NULL;
   

   s[front]=p;
   if(front==1) {root=s[front];front++;}
        else
   {  
   
     if(front%2==0) {s[front/2]->lchild=s[front];front++;}
     else if(front%2==1)
     {s[(front-1)/2]->rchild=s[front];front++;}
  
   }
   cin>>ch;
  
}
return root;
}

void preorder(bitree *root)       //先序遍历
{
bitree *p;
p=root;
if(p!=NULL)
{
   cout<<p->data<<" ";
   preorder(p->lchild);
   preorder(p->rchild);
}
}
void inorder(bitree *root)      // 中序遍历
{
   bitree *p;
   p=root;
   if(p!=NULL)
   {inorder(p->lchild);
   cout<<p->data<<" ";
   inorder(p->rchild);
   }

}

void postorder(bitree *root)      //后序遍历
{
bitree *p;
p=root;
if(p!=NULL)
{
   postorder(p->lchild);
   postorder(p->rchild);
   cout<<p->data<<" ";
}
}

void main()
{
   bitree *root;
   root=create();
   preorder(root);
   cout<<endl;
   inorder(root);
   cout<<endl;
   postorder(root);
   cout<<endl;
  
}