#include <stdio.h>

#include <stdlib.h>



#define MAX 20



typedef struct _BiTree{

	char data;

	struct _BiTree *left;

	struct _BiTree *right;

	int lTag;

	int rTag;

}BiTree;



BiTree *pre;



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;

		(*T)->lTag = (*T)->rTag = 0;



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

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

	}

}



void InOrderTraverseThreaded(BiTree *T)

{

	BiTree *p = T->left;

	while(p != T){

		while(p->lTag == 0){

			p = p->left;

		}

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

		while(p->rTag == 1 && p->right != T){

			p = p->right;

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

		}

		p = p->right;

	}

}



void InThreading(BiTree *p)

{

	if(p){

		InThreading(p->left);

		if(!p->left){

			p->left = pre;

			p->lTag = 1;

		}

		if(!pre->right){

			pre->right = p;

			pre->rTag = 1;

		}

		pre = p;

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

		InThreading(p->right);

	}

}



void InOrderThreading(BiTree **head, BiTree *T)

{

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



	(*head)->lTag = 0;

	(*head)->rTag = 1;

	(*head)->right = *head;

	if(!T){

		(*head)->left = *head;

	}else{

		(*head)->left = T;

		pre = *head;



		InThreading(T);



		pre->right = *head;

		pre->rTag = 1;



		(*head)->right = pre;

	}



}



void main()

{

	BiTree *T;	

	BiTree *head;



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

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

	PreOrderTraverseCreate(&T);

	printf("\n");



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

	InOrderThreading(&head, T);

	printf("\n");



	printf("In order traverse threaded binary tree:\n");

	InOrderTraverseThreaded(head);

	printf("\n");

}