#include <stdio.h>

#include <stdlib.h>



#define MAX 20



typedef struct _BiTree{

	char data;

	struct _BiTree *left;

	struct _BiTree *right;

}BiTree;



void CreateByPreInOrder(BiTree **T, char *pre, int pre_begin, int pre_end, char *in, int in_begin, int in_end)

{

	int len;

	int i;



	if(pre_begin > pre_end){

		return;

	}



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

	(*T)->data = pre[pre_begin];

	

	for(i=in_begin; i<=in_end; i++){

		if((*T)->data == in[i]){

			break;

		}

	}

	len = i - in_begin;



	CreateByPreInOrder(&(*T)->left, pre, pre_begin+1, pre_begin+len, in, in_begin, i-1);

	CreateByPreInOrder(&(*T)->right, pre, pre_begin+1+len, pre_end, in, i+1, in_end);



}





void PreOrderTranvers(BiTree *T)

{

	if(T){

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

		PreOrderTranvers(T->left);

		printf(",");

		PreOrderTranvers(T->right);

		printf(")");

	}

}



void main()

{

	BiTree *T;	

	char pre[] = {'A','B','C','D','E','F','G'};

	char in[]  = {'C','B','E','D','A','F','G'};

	int n = sizeof(pre)/sizeof(char);

	int i;



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

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

	for(i=0; i<n; i++){

		printf(" %c", pre[i]);

	}

	printf("\n");

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

	for(i=0; i<n; i++){

		printf(" %c", in[i]);

	}

	printf("\n");





	printf("Create binary tree by pre and in order:\n");

	CreateByPreInOrder(&T, pre, 0, n-1, in, 0, n-1);

	printf("\n");



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

	PreOrderTranvers(T);

	printf("\n");

}