# 二叉树的基本原理

`树`是n个节点的`有限`集。
在任意一棵非空树中:
1.只有`一个`被称为根的节点
2.当节点大于1时,其余节点又可分为m个`互不相交``有限`集,
  每一个有限集又是一棵树,并被称为根的`子树`
  
对于`二叉树`,其为一种树形结构,其每个节点最多只有两颗子树,
并且,二叉树的子树有左右之分,次序不能任意颠倒。

# 二叉树的基本创建

Binary_Tree_.h(头文件)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define EleType char
#define EleSign "%c"
struct Tree_Node
{
	EleType data;
	struct Tree_Node* Left_Tree_Node;
	struct Tree_Node* Right_Tree_Node;
};
struct Tree_Node_Pointer
{
	char EndSign;
	struct Tree_Node* root;
};
void Init_Tree(struct Tree_Node_Pointer* TN_Pointer,const char EndSign);
void TreeShow_Menu();
void Create_Tree(struct Tree_Node_Pointer* TN_Pointer);
void Show_Tree_PreMode(const struct Tree_Node_Pointer* TN_Pointer);
void Show_Tree_PostMode(const struct Tree_Node_Pointer* TN_Pointer);
void Show_Tree_CenterMode(const struct Tree_Node_Pointer* TN_Pointer);
void Show_Tree_LayerMode(const struct Tree_Node_Pointer* TN_Pointer);
int Tree_Size(const struct Tree_Node_Pointer* TN_Pointer);
int Tree_Height(const struct Tree_Node_Pointer* TN_Pointer);
struct Tree_Node* TreeSub_Search(const struct Tree_Node_Pointer* TN_Pointer,const  EleType value);
struct Tree_Node* TreeSub_Parent(const struct Tree_Node_Pointer* TN_Pointer,const struct Tree_Node* TN_Sub);
struct Tree_Node* TreeSub_LeftChild(const struct Tree_Node_Pointer* TN_Pointer,const struct Tree_Node* TN_Sub);
struct Tree_Node* TreeSub_RightChild(const struct Tree_Node_Pointer* TN_Pointer,const struct Tree_Node* TN_Sub);
char IsEmpty_Tree(const struct Tree_Node_Pointer* TN_Pointer);
void Tree_Copy(const struct Tree_Node_Pointer* TN_Pointer, struct Tree_Node_Pointer* Copied_TN_Pointer);
void Tree_Clean(struct Tree_Node_Pointer* TN_Pointer);
void Tree_Destroy(struct Tree_Node_Pointer* TN_Pointer);
Link_Queues_.h(自定义队列库头文件)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//#define DEBUG
//typedef int Element;
#define Element struct Tree_Node*
struct Link_Node
{
	Element element;
	struct Link_Node* next;
};
struct Link_Queues_Pointer
{
	struct Link_Node* head;
	struct Link_Node* tail;
	int space;
};
void Init_Queues(struct Link_Queues_Pointer* LQ_P);
void Show_Menu();
void Join_Queues(struct Link_Queues_Pointer* LQ_P, Element element);
void Out_Queues(struct Link_Queues_Pointer* LQ_P);
void Show_Queues(struct Link_Queues_Pointer* LQ_P);
int get_length(struct Link_Queues_Pointer* LQ_P);
void Clean_Queues(struct Link_Queues_Pointer* LQ_P);
void destroy_Space(struct Link_Queues_Pointer* LQ_P);
char IsEmpty_Queues(struct Link_Queues_Pointer* LQ_P);
void GetHead_Queues(struct Link_Queues_Pointer* LQ_P,struct Tree_Node** TN);
Binary_Tree_functions.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Binary_Tree_.h"
#include "./Link_Queues/Link_Queues_.h"
void Init_Tree(struct Tree_Node_Pointer* TN_Pointer,const char EndSign)
{
	TN_Pointer->EndSign = EndSign;
	TN_Pointer->root = NULL;
}
void TreeShow_Menu()
{
	printf("\n***************************************************************\n");
	printf("* [1]  Create_Tree         ******* [2]  Show_Tree_PreMode   ***\n");
	printf("* [3]  Show_Tree_PostMode  ******* [4]  Show_Tree_CenterMode***\n");
	printf("* [5]  Show_Tree_LayerMode ******* [6]  Tree_Size           ***\n");
	printf("* [7]  Tree_Height         ******* [8]  TreeSub_Search      ***\n");
	printf("* [9]  TreeSub_Parent      ******* [10]  TreeSub_LeftChild   ***\n");
	printf("* [11] TreeSub_RightChild  ******* [12] IsEmpty_Tree        ***\n");
	printf("* [13] Tree_Copy           ******* [14] Tree_Clean          ***\n");
	printf("* [15] Tree_Destroy        ************************************\n");
	printf("* [0]  EixtSystem          ************************************\n");
	printf("***************************************************************\n");
}
static void Create_Tree_(struct Tree_Node_Pointer* TN_Pointer, struct Tree_Node** TN)
{
	EleType element;
	scanf(EleSign, &element);
	if (TN_Pointer->EndSign == element)
		*TN = NULL;
	else
	{
		*TN = (struct Tree_Node*)malloc(sizeof(struct Tree_Node));
		assert(NULL != *TN);
		(*TN)->data = element;
		Create_Tree_(TN_Pointer, &((*TN)->Left_Tree_Node));
		Create_Tree_(TN_Pointer, &((*TN)->Right_Tree_Node));
	}
}
static struct Tree_Node* _Create_Tree_(struct Tree_Node_Pointer* TN_Pointer)
{
	EleType element;
	scanf(EleSign, &element);
	if (TN_Pointer->EndSign == element)
		return NULL;
	else
	{
		struct Tree_Node* TN = (struct Tree_Node*)malloc(sizeof(struct Tree_Node));
		assert(NULL != TN);
		TN->data = element;
		TN->Left_Tree_Node = _Create_Tree_(TN_Pointer);
		TN->Right_Tree_Node = _Create_Tree_(TN_Pointer);
		return TN;
	}
}
void Create_Tree(struct Tree_Node_Pointer* TN_Pointer)
{
	//Create_Tree_(TN_Pointer, &(TN_Pointer->root));
	TN_Pointer->root = _Create_Tree_(TN_Pointer);
}
static void Show_Tree_PreMode_(const struct Tree_Node** TN)
{
	if (NULL != (*TN))
	{
		printf(EleSign, (*TN)->data);
		Show_Tree_PreMode_(&((*TN)->Left_Tree_Node));
		Show_Tree_PreMode_(&((*TN)->Right_Tree_Node));
	}
}
void Show_Tree_PreMode(const struct Tree_Node_Pointer* TN_Pointer)
{
	Show_Tree_PreMode_(&(TN_Pointer->root));
}
static void Show_Tree_PostMode_(const struct Tree_Node** TN)
{
	if (NULL != (*TN))
	{
		Show_Tree_PostMode_(&((*TN)->Right_Tree_Node));
		Show_Tree_PostMode_(&((*TN)->Left_Tree_Node));
		printf(EleSign, (*TN)->data);
	}
}
void Show_Tree_PostMode(const struct Tree_Node_Pointer* TN_Pointer)
{
	Show_Tree_PostMode_(&(TN_Pointer->root));
}
static void Show_Tree_CenterMode_(const struct Tree_Node** TN)
{
	if (NULL != (*TN))
	{
		Show_Tree_CenterMode_(&((*TN)->Left_Tree_Node));
		printf(EleSign, (*TN)->data);
		Show_Tree_CenterMode_(&((*TN)->Right_Tree_Node));
	}
}
void Show_Tree_CenterMode(const struct Tree_Node_Pointer* TN_Pointer)
{
	Show_Tree_CenterMode_(&(TN_Pointer->root));
}
static void Show_Tree_LayerMode_(const struct Tree_Node_Pointer* TN_Pointer)
{
	assert(NULL != TN_Pointer);
	struct Link_Queues_Pointer LQ_P;
	struct Tree_Node* Head = NULL;
	Init_Queues(&LQ_P);
	Join_Queues(&LQ_P, TN_Pointer->root);
	while(!IsEmpty_Queues(&LQ_P))
	{
		GetHead_Queues(&LQ_P,&Head);
		Out_Queues(&LQ_P);
		printf(EleSign, Head->data);
		if (NULL != Head->Left_Tree_Node)
			Join_Queues(&LQ_P, Head->Left_Tree_Node);
		if (NULL != Head->Right_Tree_Node)
			Join_Queues(&LQ_P, Head->Right_Tree_Node);
	}
}
void Show_Tree_LayerMode(const struct Tree_Node_Pointer* TN_Pointer)
{
	Show_Tree_LayerMode_(TN_Pointer);
}
int Get_Tree_Size_(const struct Tree_Node* TN)
{
	if (NULL == TN)
		return 0;
	else
		return Get_Tree_Size_(TN->Left_Tree_Node) + Get_Tree_Size_(TN->Right_Tree_Node) + 1;
}
int Tree_Size(const struct Tree_Node_Pointer* TN_Pointer)
{
	return Get_Tree_Size_(TN_Pointer->root);
}
int Get_Tree_Height_(const struct Tree_Node* TN)
{
	if (NULL == TN)
		return 0;
	else
	{
		int L_Tree = Get_Tree_Height_(TN->Left_Tree_Node);
		int R_Tree = Get_Tree_Height_(TN->Right_Tree_Node);
		return (L_Tree > R_Tree ? L_Tree : R_Tree) + 1;
	}
}
int Tree_Height(const struct Tree_Node_Pointer* TN_Pointer)
{
	return Get_Tree_Height_(TN_Pointer->root);
}
static struct Tree_Node* TreeSub_Search_(const struct Tree_Node* TN,const EleType value)
{
	if (NULL == TN)
		return NULL;
	else if (value == TN->data)
		return TN;
	else
	{
		struct Tree_Node* TN_L = NULL;
		if (NULL != TN->Left_Tree_Node)
			TN_L = TreeSub_Search_(TN->Left_Tree_Node, value);
		if (NULL != TN_L)
			return TN_L;
		return TreeSub_Search_(TN->Right_Tree_Node, value);
	}
}
struct Tree_Node* TreeSub_Search(const struct Tree_Node_Pointer* TN_Pointer,const EleType value)
{
	return TreeSub_Search_(TN_Pointer->root,value);
}
static struct Tree_Node* TreeSub_Parent_(const struct Tree_Node* TN, const struct Tree_Node* TN_Sub)
{
	if (NULL == TN)
		return NULL;
	if (TN == TN_Sub)
		return NULL;
	else
	{
		if ((NULL != TN->Left_Tree_Node && TN_Sub == TN->Left_Tree_Node) || 
			(NULL != TN->Right_Tree_Node && TN_Sub == TN->Right_Tree_Node))
			return TN;
		else
		{
			struct Tree_Node* TN_L = NULL;
			TN_L = TreeSub_Parent_(TN->Left_Tree_Node, TN_Sub);
			if (NULL != TN_L)
				return TN_L;
			
			return TreeSub_Parent_(TN->Right_Tree_Node, TN_Sub);
		}
	}
}
struct Tree_Node* TreeSub_Parent(const struct Tree_Node_Pointer* TN_Pointer, const struct Tree_Node* TN_Sub)
{
	return TreeSub_Parent_(TN_Pointer->root, TN_Sub);
}
struct Tree_Node* TreeSub_LeftChild_(const struct Tree_Node* TN, const struct Tree_Node* TN_Sub)
{
	if (NULL == TN)
		return NULL;
	if (TN == TN_Sub)
	{
		if (NULL != TN->Left_Tree_Node)
			return TN->Left_Tree_Node;
		return NULL;
	}
	else
	{
		struct Tree_Node* TN_L = NULL;
		TN_L = TreeSub_LeftChild_(TN->Left_Tree_Node, TN_Sub);
		if (NULL != TN_L)
			return TN_L;
		return TreeSub_LeftChild_(TN->Right_Tree_Node, TN_Sub);
	}
}
struct Tree_Node* TreeSub_LeftChild(const struct Tree_Node_Pointer* TN_Pointer, const struct Tree_Node* TN_Sub)
{
	return TreeSub_LeftChild_(TN_Pointer->root, TN_Sub);
}
struct Tree_Node* TreeSub_RightChild_(const struct Tree_Node* TN,const struct Tree_Node* TN_Sub)
{
	if (NULL == TN)
		return NULL;
	if (TN == TN_Sub)
	{
		if (NULL != TN->Right_Tree_Node)
			return TN->Right_Tree_Node;
		return NULL;
	}
	else
	{
		struct Tree_Node* TN_L = NULL;
		TN_L = TreeSub_RightChild_(TN->Left_Tree_Node, TN_Sub);
		if (NULL != TN_L)
			return TN_L;
		return TreeSub_LeftChild_(TN->Right_Tree_Node, TN_Sub);
	}
}
struct Tree_Node* TreeSub_RightChild(const struct Tree_Node_Pointer* TN_Pointer,const struct Tree_Node* TN_Sub)
{
	return TreeSub_RightChild_(TN_Pointer->root, TN_Sub);
}
char IsEmpty_Tree(const struct Tree_Node_Pointer* TN_Pointer)
{
	return (NULL == TN_Pointer->root ? 1 : 0);
}
static void Tree_Copy_(const struct Tree_Node* TN, struct Tree_Node** Copied_TN)
{
	if (NULL == TN)
		*Copied_TN = NULL;
	else
	{
		*Copied_TN = (struct Tree_Node*)malloc(sizeof(struct Tree_Node));
		assert(NULL != Copied_TN);
		(*Copied_TN)->data = TN->data;
		Tree_Copy_(TN->Left_Tree_Node, &((*Copied_TN)->Left_Tree_Node));
		Tree_Copy_(TN->Right_Tree_Node, &((*Copied_TN)->Right_Tree_Node));
	}
}
void Tree_Copy(const struct Tree_Node_Pointer* TN_Pointer, struct Tree_Node_Pointer* Copied_TN_Pointer)
{
	Tree_Copy_(TN_Pointer->root, &Copied_TN_Pointer->root);
}
static void Tree_Clean_(struct Tree_Node* TN)
{
	if (NULL == TN)
		return;
	else
	{
		Tree_Clean_(TN->Left_Tree_Node);
		Tree_Clean_(TN->Right_Tree_Node);
		free(TN);
		TN = NULL;
	}
}
void Tree_Clean(struct Tree_Node_Pointer* TN_Pointer)
{
	Tree_Clean_(TN_Pointer->root);
	TN_Pointer->root = NULL;
}
void Tree_Destroy(struct Tree_Node_Pointer* TN_Pointer)
{
	Tree_Clean(TN_Pointer);
}
Link_Queues_functions.c(附加库实现函数)
#include"Link_Queues_.h"
void Init_Queues(struct Link_Queues_Pointer* LQ_P)
{
	LQ_P->head = NULL;
	LQ_P->tail = NULL;
	LQ_P->space = 0;
}
void Show_Menu()
{
	printf("\n********************************************\n");
	printf(" [1]Join_Queues ***********[2]Out_Queues   *\n");
	printf(" [3]Show_Queues ***********[4]get_length   *\n");
	printf(" [5]Clean_Queues***********[6]destroy_Space*\n");
	printf(" [0]Exit_system ***********                *");
	printf("\n********************************************\n");
}
void Join_Queues(struct Link_Queues_Pointer* LQ_P, Element element)
{
	struct Link_Node* P_Node = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	P_Node->element = element;
	P_Node->next = NULL;
	if (!(LQ_P->space))
	{
		LQ_P->head = P_Node;
		LQ_P->tail = P_Node;
	}
	else
	{
		LQ_P->tail->next = P_Node;
		LQ_P->tail = P_Node;
	}
#ifdef DEBUG
	printf("%d入队\n", element);
#endif
	++LQ_P->space;
}
void Out_Queues(struct Link_Queues_Pointer* LQ_P)
{
	if (LQ_P->space)
	{
		struct Link_Node* P_Node = LQ_P->head->next;
#ifdef DEBUG
		printf("%d出队\n", LQ_P->head->element);
#endif
		free(LQ_P->head);
		LQ_P->head = P_Node;
		--LQ_P->space;
	}
}
void Show_Queues(struct Link_Queues_Pointer* LQ_P)
{
	if (!(LQ_P->space))
		return;
	else
	{
		struct Link_Node* P_Node = LQ_P->head;
		
		while (P_Node->next)
		{
#ifdef DEBUG
			printf("%d ", P_Node->element);
#endif
			P_Node = P_Node->next;
		}
#ifdef DEBUG
		printf("%d ", P_Node->element);
#endif
	}
}
int get_length(struct Link_Queues_Pointer* LQ_P)
{
	printf("当前存储空间长度为%d\n", LQ_P->space);
	return LQ_P->space;
}
void Clean_Queues(struct Link_Queues_Pointer* LQ_P)
{
	int i = LQ_P->space;
	while (i)
	{
		Out_Queues(LQ_P);
		i--;
	}
}
void destroy_Space(struct Link_Queues_Pointer* LQ_P)
{
	Clean_Queues(LQ_P);
	LQ_P->head = NULL;
	LQ_P->head->next = NULL;
	LQ_P->tail = NULL;
}
char IsEmpty_Queues(struct Link_Queues_Pointer* LQ_P)
{
	return (0 != LQ_P->space ? 0 : 1);
}
void GetHead_Queues(struct Link_Queues_Pointer* LQ_P,struct Tree_Node** TN)
{
	if(NULL != LQ_P->head->element)
		*TN = LQ_P->head->element;
}
Binary_Tree_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Binary_Tree_.h"
int main()
{
	int option = 0;
	EleType value = 0;
	struct Tree_Node_Pointer TN_Pointer;
	struct Tree_Node_Pointer CTN_Pointer;
	struct Tree_Node* TN_Parent = NULL;
	struct Tree_Node* TN = NULL;
	struct Tree_Node* TN_L = NULL;
	struct Tree_Node* TN_R = NULL;
	Init_Tree(&TN_Pointer,'#');
	TreeShow_Menu();
	while (printf("选择为> "), scanf("%d", &option), option)
	{
		getchar();
		switch (option)
		{
		case 1: 
			printf("输入为> ");
			Create_Tree(&TN_Pointer);
			break;
		case 2: 
			Show_Tree_PreMode(&TN_Pointer);
			break;
		case 3: 
			Show_Tree_PostMode(&TN_Pointer);
			break;
		case 4: 
			Show_Tree_CenterMode(&TN_Pointer);
			break;
		case 5:
			Show_Tree_LayerMode(&TN_Pointer);
			break;
		case 6:
			printf("Tree Size:%d\n",Tree_Size(&TN_Pointer));
			break;
		case 7:
			printf("Tree Height:%d\n",Tree_Height(&TN_Pointer));
			break;
		case 8:
			printf("Search value is> ");
			scanf(EleSign, &value);
			TN = TreeSub_Search(&TN_Pointer, value);
			if (NULL != TN)
				printf("Get " EleSign, value);
			break;
		case 9:
			printf("TreeSub value is> ");
			scanf(EleSign, &value);
			TN = TreeSub_Search(&TN_Pointer, value);
			if (NULL != TN)
			{
				TN_Parent = TreeSub_Parent(&TN_Pointer, TN);
				printf("TreeSub Parent is " EleSign, TN_Parent->data);
			}
			else
				printf("TreeSub Parent is NULL");
			break;
		case 10:
			printf("TreeSub value is> ");
			scanf(EleSign, &value);
			TN = TreeSub_Search(&TN_Pointer, value);
			if (NULL != TN)
			{
				TN_L = TreeSub_LeftChild(&TN_Pointer, TN);
				printf("TreeSub LeftChild is " EleSign, TN_L->data);
			}
			else
				printf("TreeSub LeftChild is NULL");
			break;
		case 11:
			printf("TreeSub value is> ");
			scanf(EleSign, &value);
			TN = TreeSub_Search(&TN_Pointer, value);
			if (NULL != TN)
			{
				TN_R = TreeSub_RightChild(&TN_Pointer, TN);
				printf("TreeSub LeftChild is " EleSign, TN_R->data);
			}
			else
				printf("TreeSub LeftChild is NULL");
			break;
		case 12:
			if (!IsEmpty_Tree(&TN_Pointer))
				printf("Tree is Not Empty\n");
			else
				printf("Tree is Empty\n");
			break;
		case 13:
			Init_Tree(&CTN_Pointer, '#');
			Tree_Copy(&TN_Pointer, &CTN_Pointer);
			printf("Copied Tree> ");
			Show_Tree_LayerMode(&CTN_Pointer);
			break;
		case 14:
			Tree_Clean(&TN_Pointer);
			IsEmpty_Tree(&TN_Pointer);
			if (!IsEmpty_Tree(&TN_Pointer))
				printf("Tree is Not Empty\n");
			else
				printf("Tree is Empty\n");
			break;
		case 15:
			Tree_Destroy(&TN_Pointer);
			break;
		default: 
			printf("不在选择范围之内\n");
		}
		TreeShow_Menu();
	}
	Tree_Destroy(&TN_Pointer);
	printf("已退出\n");
	return 0;
}