#include <stdio.h>

#include <stdlib.h>



#define MAX 20



typedef struct _BiTree{

	char data;

	struct _BiTree *left;

	struct _BiTree *right;

}BiTree;



int PreOrderTraverseCreate(BiTree **T)

{

	char c;

	scanf(" %c",&c); 

	printf(" %c", c);

	if(c == '$'){

		*T = NULL;

	}else{

		*T = (BiTree *)malloc(sizeof(BiTree));

		(*T)->data = c;

		(*T)->left = (*T)->right = NULL;



		PreOrderTraverseCreate(&(*T)->left);

		PreOrderTraverseCreate(&(*T)->right);

	}

}



int PreOrderTraverse(BiTree *T)

{

	if(T != NULL){

		printf(" %c", T->data);

		PreOrderTraverse(T->left);

		PreOrderTraverse(T->right);

	}

}



void InOrderTraverse(BiTree *T)

{

	BiTree *stack[MAX];

	int top = -1;



	BiTree *p;



	stack[++top] = T;

	while(top>=0){

		while(p = stack[top]){

			stack[++top] = p->left;	

		};

		top--;



		if(top>=0){

			p = stack[top--];

			printf(" %c", p->data); 

			stack[++top] = p->right;

		}

	}

}



void InOrderTraverse2(BiTree *T)

{

	BiTree *stack[MAX];

	int top = -1;



	BiTree *p;	

	p = T;

	while(p || top>=0){

		if(p){

			stack[++top] = p;

			p = p->left;

		}else{

			p = stack[top--];

			printf(" %c", p->data);

			p = p->right;

		}

	}

}



void main()

{

	BiTree *T;	



	printf("log.anycle.com\n\n");

	printf("Pre order traverse create binary tree:\n");

	PreOrderTraverseCreate(&T);

	printf("\n");



	printf("Pre order traverse:\n");

	PreOrderTraverse(T);

	printf("\n");



	printf("In order traverse:\n");

	InOrderTraverse(T);

	printf("\n");



	printf("In order traverse:\n");

	InOrderTraverse2(T);

	printf("\n");



}