#include<stdio.h>
#include<malloc.h>

struct TNode{
	char data;
	struct TNode *lchild;
	struct TNode *rchild;
};

typedef struct TNode Node;

void init(Node **node)
{
	*node = (Node *)malloc(sizeof(Node));
	(*node)->lchild = (*node)->rchild = NULL;
	(*node)->data = 0;
}

void construct(char data, Node **node)
{
	Node *temp_node = *node;
	while(temp_node)
	{
		if(!temp_node->data)
		{
			temp_node->data = data;
			break;
		}
		else if(data <= temp_node->data)
		{
			if(!temp_node->lchild)
			{
				init(&temp_node->lchild);
				temp_node->lchild->data = data;
				break;
			}
			else
			{
				temp_node = temp_node->lchild;
				continue;
			}
		}
		else if(data > temp_node->data)
		{
			if(!temp_node->rchild)
			{
				init(&temp_node->rchild);
				temp_node->rchild->data = data;
				break;
			}
			else
			{
				temp_node = temp_node->rchild;
				continue;
			}
		}
	}
	return;
}

int PreOrderTraverse(Node *tree_node)
{
	if(tree_node)
	{
		if(printf("%c  ", tree_node->data))
			if(PreOrderTraverse(tree_node->lchild))
				if(PreOrderTraverse(tree_node->rchild))
					return 1;
		return 0;
	}
	else
		return 1;
}

int PostOrderTraverse(Node *tree_node)
{
	if(tree_node)
	{	
		if(PostOrderTraverse(tree_node->lchild))
			if(PostOrderTraverse(tree_node->rchild))
				if(printf("%c  ", tree_node->data))
					return 1;
		return 0;
	}
	else
		return 1;
}

int InOrderTraverse(Node *tree_node)
{
	if(tree_node)
	{
		if(InOrderTraverse(tree_node->lchild))
			if(printf("%c  ", tree_node->data))
				if(InOrderTraverse(tree_node->rchild))
					return 1;
		return 0;
	}
	else
		return 1;
}

int leaf_num(Node *tree_node, int *count)
{
	if(tree_node)
	{
		if(!tree_node->lchild && !tree_node->rchild)
			(*count)++;
		if(leaf_num(tree_node->lchild, count))
			if(leaf_num(tree_node->rchild, count))
				return 1;
		return 0;	
	}
	else
		return 1;
}

int tree_height(Node *tree_node)
{
	int h1, h2;
	if(!tree_node)
		return -1;
	else
	{
		h1 = tree_height(tree_node->lchild);
		h2 = tree_height(tree_node->rchild);
		return h1>h2? (h1+1): (h2+1);
	}
}
int main()
{
	int i, count = 0;
	Node *root;
	char data[10] = {'e','f','h','g', 'a','c','b','d'};
	init(&root);
	for(i = 0; i < 8; i++)
		construct(data[i], &root);
	printf("PreOrder..................\n");
	PreOrderTraverse(root);
	printf("\nAftOrder..................\n");
	PostOrderTraverse(root);
	printf("\nInOrder..................\n");
	InOrderTraverse(root);
	printf("\ncounting leaf_number\n");
	leaf_num(root, &count);
	printf("leaf number is %d\n", count);
	printf("the height of tree is %d\n", tree_height(root));
	return 0;
}