# 二叉树的基本原理

	`树`是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;
	}

非线性,树,二叉树,二叉链表

# 二叉树的基本原理

# 二叉树的基本创建

由主路由DHCP的科学旁路由

自定义Openwrt固件的本地编译操作详解