二叉树初阶

- 树的概念及结构
- - - 概念
    - 结构
- 树的专有名词
- 树的表示与应用
- - - 树的表示
    - 树的应用
- 二叉树概念及结构
- - - 概念
    - 结构
- 二叉树性质
- 二叉树的顺序结构的实现
- - - 二叉树的顺序结构
    - 堆的概念及结构
    - 堆的实现
- 二叉树链式结构的实现
- - - 概念
    - 遍历
    - 实现
- 二叉树算法题

树的概念及结构

概念

树是一种非线性的数据结构，它是由 n(n>=0) 个有限结点组成的一个具有层次关系的集合。

结构

树的结构正如它的名字一样，有根有枝叶，具有很多层次结构：

1、有一个特殊的结点，称为根结点，根节点没有前驱结点。

2、除根节点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti(1<= i<= m) 又是一棵结构与树类似的子树。

3、每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，因此，树是递归定义的。
下面给出树的几种常见结构：
在这里插入图片描述

非树的结构，列举出来，避免入坑：
在这里插入图片描述

简单来说，满足下面的结构特性，才算是树结构：

1、子树是不相交的；

2、除了根节点外，其余的结点有且只有一个父结点；

3、一颗 N 个结点的树总共有 N - 1 条边；

树的专有名词

在这里插入图片描述

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A 的为 6
叶节点或终端节点：度为 0 的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点：度不为 0 的节点；如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A 是 B 的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B 是 A 的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C 是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为 6
节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为 4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I 互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A 是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙；如上图：所有节点都是 A 的子孙
森林：由 m（m>0）棵互不相交的树的集合称为森林；

树的表示与应用

树的表示

由于树的分叉有各种各样，所以结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子兄弟表示法等等，下面给出一个代码来简单地介绍一下孩子兄弟表示法：

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

具体的展示结构如下：
在这里插入图片描述

树的应用

在我前面的一篇博客中提到了 Linux 的操作指令以及一些简单的基础概念，比如说在 Linux 下的目录结构，就是使用了树结构来表示，并且表示方法为孩子兄弟法表示的；
那么将目录用孩子兄弟法表示的好处有什么？这样子做我们就可以确定一个结构体类型来表示每一个结点，该结构体中有三个成员变量，一个 date 存放数据，一个 first_child 指向第一个孩子结点，一个 next_brother 指向下一个兄弟结点，如果不使用这种方法，那么将会创建很多种结构体来表示每一个结点；
不具体展示，这其中的思想自行体会。

二叉树概念及结构

概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。(递归思想)

二叉树的特点：

1.每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

2.二叉树的子树有左右之分，其子树的次序不能颠倒。

结构

如下图的都是二叉树：
在这里插入图片描述

特殊的二叉树：

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是 2 ^k - 1，则它就是满二叉树。

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

二叉树性质

若规定根节点的层数为 1，则一棵非空二叉树的第i层上最多有 2^i-1 个结点；
若规定根节点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h-1；
对任何一棵二叉树，如果其叶结点个数为 n₀，度为 2 的分支结点个数为 n₂，则有n₀＝n₂ ＋1；具体算法如下：
若规定根节点的层数为 1，具有 n 个结点的满二叉树的深度，h = Log₂(n+1).；(ps：Log₂(n+1) 是 log 以 2 为底，n+1 为对数)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：
1.若 i > 0，i 位置节点的双亲序号：(i-1) / 2；i = 0，i 为根节点编号，无双亲节点
2.若 2i + 1 < n，左孩子序号：2i + 1，2i + 1 >= n 否则无左孩子
3.若 2i + 2 < n，右孩子序号：2i + 2，2i + 2 >= n否则无右孩子

二叉树的顺序结构的实现

二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树是非常适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
在这里插入图片描述

堆的概念及结构

如果有一个关键码的集合 K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
在这里插入图片描述

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

堆的实现

以下部分为堆创建的代码，在其中涉及到了几个比较重要的操作：

1.堆的向下调整：在保证左右子树都是大(小)堆的情况下，将堆顶元素向下调整到合适的位置，主要做法就是和左右孩子中最小(大)的比较，如果比其小(大)，那么交换，否则就说明调整完毕；

2.堆的插入：主要是先尾插，然后向上调整；向上调整就是和父结点比较，如果比父结点大，那就交换，继续向上调整，如果比父结点小，那么结束调整；

3.堆的创建：对于给定数组，要使其变成堆结构，那么只需从最后一个非叶子结点开始向下调整，直到堆顶元素即可；

4.堆的删除：从堆顶开始删除，但是数组删除堆顶元素时间复杂度为 O(N)，所以我们先和尾元素互换，然后删除尾元素，再对堆顶元素做向下调整即可；

//这是 .h 部分的代码
#pragma once

//使用这种方式来重命名数据类型，这样可以很方便的修改后续数据的数据类型，相当于#define的作用
typedef int HeapType;

//创建堆结构体，也就是动态顺序表
typedef struct Heap
{
	//动态开辟数组有来存放数据
	HeapType* _date;
	//堆的有效元素个数
	int _size;
	//堆的容量
	int _capacity;
}Heap;

//所有函数的声明

//向下调整
void AdjustDown(HeapType* a, int n, int root);
//向上调整
void AdjustUp(HeapType* a, int n, int root);
//交换函数
void swap(HeapType* x, HeapType* y);
//堆的初始化
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HeapType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
//检查容量
void CheckCapacity(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HeapType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HeapType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//打印函数
void HeapPrint(Heap* hp);
// 对数组进行堆排序>堆排序
void HeapSort(HeapType* a, int n);
//打印n个数中，前k个最小的数
void PrintTopK(int* a, int n, int k);

//这是 .c 部分的代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"heap.h"

//向下调整
void AdjustDown(HeapType* a, int n, int i) {
	//此函数是在其他函数内部调用的，所以此处不需检查
	//下面做循环，以建小堆为例；
	//从给定结点开始，如果该父结点比孩子结点中最小的大，那么就交换这两个结点，接着向下走，否则跳出循环
	//循环一直到最后一个非叶子节点
	while (i <= (n - 2) / 2) {
		int cur = 0;
		//下面的 if 是判断如果走到最后一个非叶子节点，那么有两种情况，那就是该父结点的度是 1 还是 2
		if (2 * i + 2 < n) {
			//如果有右孩子，那么就找出左右孩子中最小的，与其比较
			cur = (a[2 * i + 1] < a[2 * i + 2] ? 2 * i + 1 : 2 * i + 2);
		}
		else {
			//如果没有右孩子，那么就只和左孩子比较
			cur = 2 * i + 1;
		}
		//判断父结点和比孩子结点大小关系
		if (a[i] > a[cur]) {
			//父结点大于孩子结点，就交换
			swap(&a[i], &a[cur]);
			//更新节点位置
			i = cur;
		}
		else {
			//父结点比孩子结点小，就结束循环
			return;
		}
	}
}

//向上调整
void AdjustUp(HeapType* a, int n, int i) {
	//此函数是在其他函数内部调用的，所以此处不需检查
	//下面循环是以创建好的小堆来进行向上调整的
	while (i) {
		//比较当前位置元素和父结点元素大小
		if (a[i] < a[(i - 1) / 2]) {
			//如果父结点大于当前结点，那就交换
			swap(&a[i], &a[(i - 1) / 2]);
			//并更新待比较位置
			i = (i - 1) / 2;
		}
		//如果父结点小于当前节点就直接结束
		else {
			return;
		}
	}
}

//交换函数
void swap(HeapType* x, HeapType* y) {
	int temp = 0;
	temp = *x;
	*x = *y;
	*y = temp;
}

//堆的初始化
void HeapInit(Heap* hp) {
	//参数合法性检验
	if (hp == NULL) {
		return;
	}
	hp->_date = NULL;
	hp->_capacity = hp->_size = 0;
}

// 堆的构建，将已有数组构建成堆
void HeapCreate(Heap* hp, HeapType* a, int n) {
	//参数合法性检验
	if (hp == NULL) {
		return;
	}
	//动态开辟数组大小空间
	hp->_date = (HeapType*)malloc(sizeof(HeapType) * n);
	//循环将数据放入堆中
	for (int i = 0; i < n; i++) {
		hp->_date[i] = a[i];
	}
	hp->_capacity = hp->_size = n;
	//循环向下调整,使堆变成小堆
	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdjustDown(hp->_date, n, i);
	}
}

// 堆的销毁
void HeapDestory(Heap* hp) {
	//参数合法性检验
	if (hp == NULL) {
		return;
	}
	//释放空间
	free(hp->_date);
	//令其等于NULL,防止成为野指针
	hp->_date == NULL;
}

//检查容量
void CheckCapacity(Heap* hp) {
	//此函数是在其他函数内部调用的，所以此处不需检查
	//有效元素等于容量，则说明满了，需要增容
	if (hp->_capacity == hp->_size) {
		hp->_capacity = hp->_capacity == 0 ? 1 : 2 * hp->_capacity;
		//使用 realloc 函数进行空间增容
		hp->_date = (HeapType*)realloc(hp->_date,sizeof(HeapType) * hp->_capacity);
	}
}

// 堆的插入；方法为先尾插入，再向上调整
void HeapPush(Heap* hp, HeapType x) {
	//参数合法性检验
	if (hp == NULL) {
		return;
	}
	//容量检查
	CheckCapacity(hp);
	//尾插
	hp->_date[hp->_size] = x;
	hp->_size++;
	//向上调整
	AdjustUp(hp->_date, hp->_size, hp->_size - 1);
}

// 堆的删除；方法为先将堆顶元素和堆尾元素互换，然后尾删，再堆顶向下调整
void HeapPop(Heap* hp){
	//参数合法性检验，如果为空堆，那么直接返回
	if (hp == NULL || hp->_size == 0) {
		return;
	}
	//堆顶堆尾元素互换
	swap(&hp->_date[0], &hp->_date[hp->_size - 1]);
	//尾删
	hp->_size--;
	//堆顶向下调整
	AdjustDown(hp->_date, hp->_size, 0);
}

// 取堆顶的数据
HeapType HeapTop(Heap* hp) {
	//此处无法进行参数合法性检验，因为没有任何值可以作为出错的返回值
	return hp->_date[0];
}

// 堆的数据个数
int HeapSize(Heap* hp) {
	//参数合法性检验
	if (hp == NULL || hp->_size == 0) {
		return 0;
	}
	return hp->_size;
}

// 堆的判空,为空返回非零值，非空返回零
int HeapEmpty(Heap* hp) {
	//参数合法性检验
	if (hp == NULL || hp->_size == 0) {
		return 1;
	}
	return 0;
}

//打印函数
void HeapPrint(Heap* hp) {
	//参数合法性检验
	if (hp == NULL) {
		return;
	}
	//循环打印
	for (int i = 0; i < hp->_size; i++) {
		printf("%d ", hp->_date[i]);
	}
	printf("\n");
}

// 对数组进行堆排序>堆排序，降序排序（如果是小堆就排降序，如果是大堆就排升序，本代码中是小堆，所以排降序）
void HeapSort(HeapType* a, int n) {
	//对数组的数据进行向下调整,建成小堆
	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	int cur = n;
	//进行循环，每次将对顶元素和当前堆的最后一个位置互换，然后堆的个数减一，然后进行向下调整重新变成小堆
	//上面的操作就是在将堆的最小值放到最后，然后对剩下的元素再次进行向下调整，这样循环下去
	while (--cur) {
		swap(&a[0], &a[cur]);
		AdjustDown(a, cur, 0);
	}
}

//打印n个数中，前k个最小的数
void PrintTopK(int* a, int n, int k) {
	Heap hp;
	HeapInit(&hp);
	//将数据插入堆中
	for (int i = 0; i < n; i++) {
		HeapPush(&hp, a[i]);
	}
	//拿堆顶元素，然后删除堆顶元素
	for (int i = 0; i < k; i++) {
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}
}

void TestTopk(){
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	//随机生成10000个数存入数组，保证元素都小于1000000
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000 + 11;
	}
	//确定10个最大的数
	a[5] = 1;
	a[1231] = 2;
	a[531] = 3;
	a[5121] = 4;
	a[115] = 5;
	a[2335] = 6;
	a[9999] = 7;
	a[76] = 7;
	a[423] = 9;
	a[3144] = 10;

	PrintTopK(a, n, 10);
}

int main() {
	TestTopk();
	return 0;
}

二叉树链式结构的实现

概念

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个成员变量组成，数据变量和左右孩子指针变量，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
链式结构又分为二叉链和三叉链，当前我接触到的一般都是二叉链，二者的具体结构如下：
在这里插入图片描述

遍历

在二叉树中，所谓遍历就是指沿着某条搜索路线，依次对树中每个结点均做且仅一次的访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是最常规的操作，并且是在二叉树上进行其它运算的基础。这其中最重要的操作有如下几种：

1. 前序遍历（先序）：前序遍历可以记为根左右，若二叉树为空，则结束返回。前序遍历的规则：
（1）访问根节点
（2）前序遍历左子树
（3）前序遍历右子树

2. 中序遍历：中序遍历可以记为左根右，也就是说在二叉树的遍历过程中，首先要遍历二叉树的左子树，接着遍历根节点，最后遍历右子树。同样，在二叉树为空的时候，结束返回。中序遍历的规则：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树

3. 后序遍历：后序遍历可以记为左右根，也就是说在二叉树的遍历过程中，首先按照后序遍历的规则遍历左子树，接着按照后序遍历的规则遍历右子树，最后访问根节点。在二叉树为空的时候，结束返回。后序遍历二叉树的规则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点

4. 层序遍历
：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现

//.h 部分的代码
#pragma once

//使用这种方式来重命名数据类型，这样可以很方便的修改后续数据的数据类型，相当于#define的作用
typedef char BTreeType;

//创建二叉树结构体
typedef struct BTree {
	//二叉树保存的数据
	BTreeType _date;
	//指向左孩子的指针
	struct BTree* _left;
	//指向右孩子的指针
	struct BTree* _right;
}BTree;

//所有函数的声明

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTree* BTreeCreate(BTreeType* a, int* idx);
// 二叉树销毁
void BTreeDestory(BTree** root);
// 二叉树节点个数
int BTreeSize(BTree* root);
// 二叉树叶子节点个数
int BTreeLeafSize(BTree* root);
// 二叉树第k层节点个数
int BTreeLevelKSize(BTree* root, int k);
// 二叉树查找值为x的节点
BTree* BTreeFind(BTree* root, BTreeType x);
// 二叉树前序遍历
void BTreePrevOrder(BTree* root);
// 二叉树中序遍历
void BTreeInOrder(BTree* root);
// 二叉树后序遍历
void BTreePostOrder(BTree* root);
// 层序遍历
void BTreeLevelOrder(BTree* root);
// 判断二叉树是否是完全二叉树
int BTreeComplete(BTree* root);

//.c 部分的代码
#include<stdio.h>
#include<stdlib.h>
#include"btree.h"

//递归法创建，若想创建一颗完整的二叉树，那么在当前节点为根结点的情况下，只要创建好左右子树，就可以完成创建二叉树，
//同理根的左右孩子创建方法如上一样，以根的左右孩子为当前子树的根结点，那么只要他们的左右子树创建好，就可以完成创建二叉树，
//按照这种思想就很简单的实现了二叉树创建的代码；通过前序遍历的数组来构建二叉树
//传入一个待创建序列和一个计数器，该计数器以全局形式存在，这样才能在一次次递归的过程中始终改变为正确的值
BTree* BTreeCreate(BTreeType* arr, int* idx) {
	//递归结束的条件，遇到 # 就会返回
	if (arr[*idx] == '#') {
		(*idx)++;
		return NULL;
	}
	//因为是先序遍历的序列，所以先创建结点保留当前元素
	BTree* root = (BTree*)malloc(sizeof(BTree));
	root->_date = arr[*idx];
	(*idx)++;
	//根节点赋值之后，按照根的左孩子，根的右孩子的顺序来赋值
	root->_left = BTreeCreate(arr, idx);
	root->_right = BTreeCreate(arr, idx);
	//返回当前结点作为上一次调用的左/右孩子，直到退回一开始的调用，那么就返回根结点
	return root;
}

//二叉树销毁，这里使用二级指针是为了让修改的是实参而不会是形参，也就是在释放了某个节点之后我们将其置位NULL，防止野指针
void BTreeDestory(BTree** root) {
	//参数合法性检验
	if (*root == NULL) {
		return;
	}
	//因为创建的时候从上至下创建出来的，那么删除的时候就要从下至上，如果先删除了父结点而没有释放子节点
	//那么子节点就会拿不到，释放不了了，所以必须从最下面开始释放，直到根结点
	//也就是要释放某节点，那就先释放它的孩子结点，直到左右孩子结点都为空
	if ((*root)->_left == NULL && (*root)->_right == NULL) {
		free(*root);
		*root = NULL;
		return;
	}
	BTreeDestory(&((*root)->_left));
	BTreeDestory(&((*root)->_right));


	//这是一个简单的写法，一开始没想出来，后来搜了一下学会了
	//原理就是要销毁某个树，先销毁它的左右子树，然后再销毁当前节点
	/*if (*root) {
		BTreeDestory(&((*root)->_left));
		BTreeDestory(&((*root)->_right));
		free(*root);
		*root = NULL;
	}*/
}

//二叉树节点个数，方法为递归法，要统计所有结点个数，那么只要知道了左右子树共有多少个结点，就可以算出总共有多少
//而左右子树又可以看成是一个二叉树，那么就可以递归下去，直到左右子树都为空即可
int BTreeSize(BTree* root) {
	//参数合法性检验，也是递归结束的条件
	if (root == NULL) {
		return 0;
	}
	//以当前节点为根的子树有多少个节点是由左右子树结点个数和当前的 1 个之和组成的
	return BTreeSize(root->_left) + BTreeSize(root->_right) + 1;
}

//二叉树叶子节点个数,方法一为递归直接返回，从根开始遍历，如果遇到某个节点的左右孩子均为 NULL，则说明是叶子结点，就返回 1
//如果当前不是叶子结点，那么就继续向下递归，最终返回左右子树叶子结点个数的和就是总的叶子结点个数
int BTreeLeafSize1(BTree* root) {
	//参数合法性检验
	if (root == NULL) {
		return 0;
	}
	//如果左右孩子均为 NULL，那么就返回 1
	if (root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	//返回左右子树中所有叶子结点个数的和
	return BTreeLeafSize1(root->_left) + BTreeLeafSize1(root->_right);
}

//二叉树叶子结点个数，方法二递归计数法，计数器为外部的一个全局变量，以指针形式传入
//如果遇到了左右孩子均为空，那么计数器加一
void BTreeLeafSize2(BTree* root,int* count) {
	//参数合法性检验
	if (root == NULL) {
		return;
	}
	//找到一个左右孩子均为空的结点，那么计数器就加一
	if (root->_left == NULL && root->_right == NULL) {
		(*count)++;
		return;
	}
	//然后向下遍历当前节点的左右孩子
	BTreeLeafSize2(root->_left, count);
	BTreeLeafSize2(root->_right, count);
}

//二叉树第k层节点个数
int BTreeLevelKSize(BTree* root, int k) {
	//参数合法性检验，在递归的过程中，如果某一结点为空则返回 0
	if (root == NULL) {
		return 0;
	}
	//递归结束的条件；因为一开始 k 是相对于根节点来说的，那么每向下递归一层，就 k-1，直到 k==1 就说明是要找的层数
	if (k == 1) {
		return 1;
	}
	//左右子树所有的第 k 层结点个数之和为总的结点个数
	return BTreeLevelKSize(root->_left, k - 1) + BTreeLevelKSize(root->_right, k - 1);
} 

//二叉树查找值为x的节点
BTree* BTreeFind(BTree* root, BTreeType x) {
	//参数合法性检验
	if (root == NULL) {
		return NULL;
	}
	if (root->_date == x) {
		return root;
	}
	if (BTreeFind(root->_left, x)) {
		return root;
	}
	return BTreeFind(root->_right, x);
}

//二叉树前序遍历
void BTreePrevOrder(BTree* root) {
	//参数合法性检验,也可作为递归结束的条件
	if (root == NULL) {
		return;
	}
	//打印当前结点元素
	printf("%c ", root->_date);
	//去寻找以当前节点作为根结点的左右子树
	BTreePrevOrder(root->_left);
	BTreePrevOrder(root->_right);
}

//二叉树中序遍历
void BTreeInOrder(BTree* root) {
	//参数合法性检验,也可作为递归结束的条件
	if (root == NULL) {
		return;
	}
	//去寻找以当前节点作为根结点的左子树
	BTreePrevOrder(root->_left);
	//打印当前结点元素
	printf("%c ", root->_date);
	//去寻找以当前节点作为根结点的右子树
	BTreePrevOrder(root->_right);
}

//二叉树后序遍历
void BTreePostOrder(BTree* root) {
	//参数合法性检验,也可作为递归结束的条件
	if (root == NULL) {
		return;
	}
	//去寻找以当前节点作为根结点的左右子树
	BTreePrevOrder(root->_left);
	BTreePrevOrder(root->_right);
	//打印当前结点元素
	printf("%c ", root->_date);
}

//层序遍历，最优的方法为利用队列先将根结点入队，然后取队头元素拿到根结点，再出队，接着入队根的左右孩子
//然后再拿出对头元素，出队之后将他的左右孩子进队，依次走下去，直到队列为空即可，在这过程中，遇到空节点直接跳过
//由于使用队列需要包含之前的队列实现的代码，这样会有很多代码，所以我决定使用数组来代替队列，进出数组的操作只需设置两个标记下标即可
void BTreeLevelOrder(BTree* root) {
	//参数合法性检验
	if (root == NULL) {
		return;
	}
	//动态开辟二叉树结点个数大小的空间
	BTree** arr = (BTree**)malloc(sizeof(int) * BTreeSize(root));
	//表示当前所在的位置，也表示容量
	int size = 0;
	//表示出数组，需要拿到的元素的位置
	int idx = 0;
	//先将根节点放入
	arr[size++] = root;
	//循环遍历，结束条件就是要拿到的位置不小于容量大小
	while (size > idx) {
		//取出数组中当前位置的结点，并将其数据打印出来
		BTree* node = arr[idx++];
		printf("%c", node->_date);
		//然后将当前节点的左右孩子写入，若为空就不写入
		if (node->_left) {
			arr[size++] = node->_left;
		}
		if (node->_right) {
			arr[size++] = node->_right;
		}
	}
	printf("\n");
}

//判断二叉树是否是完全二叉树，做法和层序遍历差不多，只是不将其打印出来而已，并且如果当前节点的左右孩子为空节点也写入数组中
//在遇到了第一个空节点就停止循环，如果此树是完全二叉树，那么数组后面的元素就不会存在非空节点了，否则就会有非空结点（完全二叉树性质可得）
int BTreeComplete(BTree* root) {
	//参数合法性检验
	if (root == NULL) {
		return 1;
	}
	//动态开辟二叉树结点个数大小的空间
	BTree** arr = (BTree**)malloc(sizeof(int) * BTreeSize(root) * 3);
	//表示当前所在的位置，也表示容量
	int size = 0;
	//表示出数组，需要拿到的元素的位置
	int idx = 0;
	//先将根节点放入
	arr[size++] = root;
	//循环遍历，结束条件就是要拿到的位置不小于容量大小
	while (size > idx) {
		//取出数组中当前位置的结点
		BTree* node = arr[idx++];
		//然后将当前节点的左右孩子写入
		if (node) {
			arr[size++] = node->_left;
			arr[size++] = node->_right;
		}
		//若当前节点为空那么就结束循环
		else {
			break;
		}
	}
	//该循环是为了判断数组剩余元素(这里的剩余元素是指 idx 位置到 size 位置的元素)是否存在非空结点，若果有则返回假(0)，否则返回真(非零值)
	while (size > idx) {
		if (arr[idx++]) {
			return 0;
		}
	}
	//如果循环结束都没有返回任何元素，那么就说明是完全二叉树，返回真(非零值)
	return 1;
}

void test() {
	BTreeType arr[] = { 'A','B','D','L','#','#','#','E','#','#','C','F','#','#','G','#','#' };
	int idx = 0;
	BTree* root = BTreeCreate(arr, &idx);

	BTreePrevOrder(root);
	printf("\n");

	BTreeInOrder(root);
	printf("\n");

	BTreePostOrder(root);
	printf("\n");

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

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

	int count = 0;
	BTreeLeafSize2(root, &count);
	printf("%d\n", count);

	int k = 4;
	printf("%d\n", BTreeLevelKSize(root, k));

	BTreeLevelOrder(root);

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

	BTreeDestory(&root);
}

int main() {
	test();
	return 0;
}

二叉树算法题

965. 单值二叉树
104. 二叉树的最大深度
226. 翻转二叉树
100. 相同的树
101. 对称二叉树
572. 另一个树的子树
110. 平衡二叉树
102. 二叉树的层序遍历
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历