#include<stdio.h>
#define maxsize 100
typedef struct node{
  char data;
  struct node *lchild,*rchild;
 }bt;
createbt(bt **T)
 {
  char ch;
  scanf("%c",&ch);
  if(ch==' ')*T=NULL;
   else{
   *T=(bt *)malloc(sizeof(bt));
   (*T)->data=ch;
   createbt(&((*T)->lchild));
   createbt(&((*T)->rchild));
   }
 }
exchange(bt **t)
{
 bt *temp;
 if(!(*t))return 0;
  else
   {
   temp=(*t)->lchild;
   (*t)->lchild=(*t)->rchild;
   (*t)->rchild=temp;
    if((*t)->lchild)
      exchange(&((*t)->lchild));
    if((*t)->rchild)
      exchange(&((*t)->rchild));
   }
}
 preorder(bt *t)
 {
  if(t){
  printf("%c ",t->data);
  preorder(t->lchild);
  preorder(t->rchild);
  }
 }
main()
{
 bt *h;
 createbt(&h);
 exchange(&h);
 preorder(h);
}