数据结构进阶——二叉树，红黑树

基本定义：一个根节点下分两个子节点的树结构称为二叉树。A为根节点，B、C分别为左孩子和右孩子，E这种无孩子的结点成为叶子结点，A，B，D，G共4层。二叉树存在的三种排序方式图中也说明的很清晰了。

先序：根->左->右；

中序：左->根->右；

后序：左->右->根；

#include <stdio.h>

typedef struct TREE {
	struct TREE* leftChild;
	struct TREE* rightChild;
	void* value;
}TREE;

void init(TREE** root, void* data);
void clear(TREE** root);
void makeLeftChild(TREE* root, void* data);
void makeRightChild(TREE* root, void* data);
void showTreeByFirst(TREE* root);
void showTreeBySecond(TREE* root);
void showTreeByThird(TREE* root);

void init(TREE** root, void* data) {
	TREE** head;
	TREE* tmp;
	if (NULL == root || NULL != *root) {
		printf("Wrong input init value!\n");
		return;
	}

	head = root;
	(*head) = (TREE*) calloc(sizeof(TREE), 1);
	// test
	*root = *head;
	tmp = *head;
	(tmp->value) = data;
	tmp->leftChild = NULL;
	tmp->rightChild = NULL;

	printf("data = %d\n", *(int *)data);
}

void clear(TREE** root) {
	TREE* tmp = *root;
	static int times = 0;

	if(tmp->leftChild != NULL) {
		clear(&(tmp->leftChild));
		printf("Left clear!\n");
		
	}
	if(tmp->rightChild != NULL) {
		clear(&(tmp->rightChild));
		printf("Right clear!\n");
	}
	free(tmp);
	*root = NULL;

	printf("Clear complete! time = %d\n", ++times);
}

void makeLeftChild(TREE* root, void* data) {
	TREE* left = NULL;
	init(&left, data);
	root->leftChild = left;

	printf("Make LeftChild complete! leftData = %d\n", *((int *)data));
}

void makeRightChild(TREE* root, void* data) {
	TREE* right = NULL;
	init(&right, data);
	root->rightChild = right;

	printf("Make rightChild complete! rightData = %d\n", *((int *)data));
}

void showTreeByFirst(TREE* root) {
	if(root != NULL) {
		printf("root->value = %d\n", *((int *)root->value));
		showTreeByFirst(root->leftChild);
		showTreeByFirst(root->rightChild);

		if(*((int *)root->value) == 1) {
			printf("First Show over!\n");
		}
	}
}

void showTreeBySecond(TREE* root) {
	if(root != NULL) {
		showTreeBySecond(root->leftChild);
		printf("root->value = %d\n", *((int *)root->value));
		showTreeBySecond(root->rightChild);

		if(*((int *)root->value) == 1) {
			printf("Second Show over!\n");
		}
	}
}

void showTreeByThird(TREE* root) {
	if(root != NULL) {
		showTreeByThird(root->leftChild);
		showTreeByThird(root->rightChild);
		printf("root->value = %d\n", *((int *)root->value));

		if(*((int *)root->value) == 1) {
			printf("Third Show over!\n");
		}
	}
}

void main(void) {
	TREE* root = NULL;
	int data = 1;
	int leftData = 2;
	int rightData = 3;
	int leftleftData = 4;
	int leftrightData = 5;

	init(&root, &data);
	makeLeftChild(root, &leftData);
	makeLeftChild(root->leftChild, &leftleftData);
	makeRightChild(root->leftChild, &leftrightData);
	makeRightChild(root, &rightData);

	showTreeByFirst(root);
	showTreeBySecond(root);
	printf("\n");
	showTreeByThird(root);
	printf("\n");
	clear(&root);

	printf("%d\n", root);
}