1，概述

树：

树是一个n个结点的有限集，如果n=0称之为空树。
树的定义是递归的，树中又调用了自身。
树的根节点没有前驱，除了根节点，其他所有节点有且只有一个前驱
树中所有节点可以有0个或者多个后驱。

二叉树：

特殊的树结构
每个结点至多只有两个子树

遍历方式：

前中后根节点遍历

前序：根->左->右

中序：左->根->右

后序：左->右->根

如图所示：

在这里需要注意的是，根是相对的，左右也是相对的，以A为根，左右为B,C。以B为根，左右为D，F。

前序时，开始根为A然后是A-B-D,此时根为B，所以退出D进入E。
中序时，开始从D开始，然后根为B，所以是D-B-E,然后退出E进入A。
后序时，开始从D开始，然后去E，再去根B，然后进入F-G-C最后到A。

2. 树的创建

树的创建中我们每次都会调用相同的结构体，所以我们使用递归来重复定义和写入预设代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <time.h>
#include <Windows.h>
#include <string.h>
#include <malloc.h>

//二叉树的结构定义
typedef struct TREECREAT {
	char name;
	struct TREECREAT* LEFT;
	struct TREECREAT* RIGHT;
}TREE;

//二叉树的逻辑
void TREERE(TREE** t) {
	char name;
	//name = getchar();
	scanf(" %c",&name);
	if (name=='#') {
		//此时为空节点
		*t = NULL;
		return;
	}
	else
	{
		//此时不为空
		*t = (TREE*)malloc(sizeof(TREE));
		(*t)->name = name;
		//左子树
		TREERE(&((*t)->LEFT));
		//右子树
		TREERE(&((*t)->RIGHT));
	}
}

int main() {
	TREE* t ;
	TREERE(&t);
	system("pause");
	return 0;
}

再上述过程中，我们将结构重复使用，避免了每次定义的繁杂过程。我们传入二级指针来修改指向。这时我们的录入得到顺序为根->左->右，并且是层级递增。如果需要先录入右侧，只需要更改两条代码的位置即可。

3.树的遍历

3.1普通遍历

树的遍历有前序，中序，后续三种。其区别并不大==仅仅需要改变代码优先执行的顺序即可==

前序如下：

//树的遍历
void printtree1(TREE* p) {
	if (p == NULL) {
		return;
	}
	else {
		//前序
		printf("%c\n", p->name);
		printtree1(p->LEFT);
		printtree1(p->RIGHT);
	}
}

中序如下：

//树的遍历
void printtree2(TREE* p) {
	if (p == NULL) {
		return;
	}
	else {
		//中序
		printtree2(p->LEFT);
		printf("%c\n", p->name);
		printtree2(p->RIGHT);
	}
}

后序如下：

//树的遍历
void printtree3(TREE* p) {
	if (p == NULL) {
		return;
	}
	else {
		//后序
		printtree3(p->LEFT);
		printtree3(p->RIGHT);
		printf("%c\n", p->name);
	}
}

其本质在于printf的位置，即根的输出与左右分枝的执行顺序。

3.2 层次遍历

层次遍历相当于树的同级结构的遍历，如图：

层次遍历就相当于是A->B->C->D->E->F->G的顺序进行遍历，这里b和c是同一级，defg为同一级。这里由于我们用递归定义的树结构，这里层级遍历就需要用到队的结构去实现。

由于层次遍历，我们可以改变一下录入规则去使用它


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <time.h>
#include <Windows.h>
#include <string.h>
#include <malloc.h>

//树模块
typedef struct TREE {
	int data;
	struct TREE* left;
	struct TREE* right;
}TREE;

//队列模块
typedef struct QUEUE {
	TREE* arr[10];
	int front;
	int bottom;//用整形计数
}QUEUE;

void initqueue(QUEUE* q) {
	(*q).front = (*q).bottom = 0;
}

void put(QUEUE* q1, TREE* p2) {
	(*q1).arr[(*q1).front++] = p2;
}

TREE* pop(QUEUE* q) {
	if ((*q).front == (*q).bottom)
		return NULL;
	return ((*q).arr[(*q).bottom++]);
}

//匹配是否符合条件
TREE* search(TREE* tr) {
	QUEUE* q;
	TREE* p;
	initqueue(&q);
	if (tr->left == NULL || tr->right == NULL) {
		return tr;
	}
	put(&q, tr);
	while (1) {
		p = pop(&q);
		if (p->left != NULL) {
			put(&q, p->left);
		}
		else {
			return p;
		}
		if (p->right != NULL) {
			putqueue(&q, p->right);
		}
		else {
			return p;
		}
	}
}

//初始化树
TREE* inittree(TREE**p) {
	TREE* pp = *p;
	char data;
	scanf("%c", &data);
	pp = (TREE*)malloc(sizeof(TREE));
	pp->left = NULL;
	pp->right = NULL;
	pp->data = data;
	*p = pp;
	return *p;
}

//插入
void insert() {
	TREE* p, * q;
	char ch;
	q = (TREE*)malloc(sizeof(TREE));
	q->left = NULL;
	q->right = NULL;
	printf("请输入节点字母：\n");
	ch = getchar();
	q->data = ch;
	p = search(&q);
	if (p->left) {
		p->left = q;
	}
	else {
		p->right = q;
	}
}

int main() {
	TREE* p;
	inittree(&p);
	system("pause");
	return 0;
}