#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
 int data;
 struct node *lchild, *rchild;
}bitree;
bitree *Q[100];
bitree *creat_tree()
{
 int front=1, rear=0;
 char ch;
 bitree *root, *s;
 printf("creat bitree!\n");
 printf("for ex");
 while((ch=getchar())!=10)
 {
  s=NULL;
  if(ch!='@')
  {
   s=(bitree *)malloc(sizeof(bitree));
   s->data=ch;
   s->lchild=NULL;
   s->rchild=NULL;
  }
  rear++;
  Q[rear]=s;
  if(rear==1)
   root=s;
  else
  {
   if( s && Q[front])
    if(rear%2==0)
     Q[front]->lchild=s;
    else
     Q[front]->rchild=s;
   if(rear%2==1)
   {
    front++;
   }
  } 
 }
 return root;

}
void PerOrder(bitree *T)
{
 if(T)
 {
  printf(" %c\t", T->data);
  PerOrder(T->lchild);
  PerOrder(T->rchild);
 }
 
}
void InOrder(bitree *T)
{
 if(T)
 {
  
  InOrder(T->lchild);
  printf(" %c\t", T->data);
  InOrder(T->rchild);
 }
}
void LastOrder(bitree *T)
{
 if(T)
 {
  
  LastOrder(T->lchild);
  LastOrder(T->rchild);
  printf(" %c\t", T->data);
 }
 
}
void main()
{
 char in;
 bitree *t;
 t=creat_tree();
 while(true)
 {
  printf("1 前续排列 2 中序排列 3 后序排列 4 退出\n");
  in=getchar();
  getchar();
  if(in=='1')
  {
   PerOrder(t);
   printf("\n");
  }
  else if(in=='2')
  {
   InOrder(t);
   printf("\n");
  }
  else if(in=='3')
  {
   LastOrder(t);
   printf("\n");
  }
  else if(in=='4')
  {
   exit(0);
  }
  else
   printf("error!!!\n");
 }
}