#include <stdio.h>
#include <stdlib.h>
#define max 20
typedef struct node
{struct node *lc,*rc;
 char data;
}*btree,btreenode;
btree creat(btree r)
{char c;
 btree t;
 t=r;
 while(1)
 {t=(btreenode*)malloc(sizeof(btreenode));
  c=getchar();
  if(c=='#') return r;
  if(c=='*') t=NULL;
  else t->data=c;
  creat(t->lc);
  creat(t->rc);
 }
 return r; 
}
void prorder(btree t)
{btree s[max],p;
 int top;
 top=-1;
 if(t!=NULL)
 {top++;
  s[top]=t;
  while(top>-1)
  {p=s[top];
   printf("%c   ",p->data);
   while(p->lc)
    {s[top++]=p->lc;
     printf("%c  ",p->data);
     p=s[top];
    }
   while(p->rc==NULL)
     p=s[top--];
   p=s[top];
   s[top]=p->rc;
   if(p==t) s[top]=t->rc;
  }
 }
} 
main()
{btree r;
 creat(r);
 prorder(r);
}