#include <stdio.h>
#include <stdlib.h>

typedef char elemtype;

typedef struct node {
        elemtype data;
        struct node *lchild;
       struct node *rchild;
}BinTNode,*BinTree;

 void CreatBinTree(BinTree *t)
{
        char ch;
       
        scanf ("%c", &ch);
        if (ch == ' ')
           t = NULL;
        else {
               *t = malloc (sizeof (BinTNode));
               (*t)->data=ch;
                CreatBinTree(&((*t)->lchild));
                CreatBinTree(&((*t)->rchild));
        }        
}

 

void exchange(BinTree t)

{

    BinTNode *temp;

    BinTNode *s[20];

    int top=0;

    while(t||top)

    {

        if(t)

        {

            s[top++]=t;

            temp=t->lchild;

            t->lchild=t->rchild;

            t->rchild=temp;

            t=t->lchild;

        }

        else

        {

            t=s[--top]->rchild;

        }

 

    }


}
void preorder(BinTree t)
{
        if (t!=NULL){
                printf("%c",t->data);
                preorder(t->lchild);
                preorder(t->rchild);
        }

}
void main ()
{  BinTree t;
        CreatBinTree(&t);
        exchange(t);
        printf ("Print Previous Order:\n");
        preorder(t);getch();

}