🍕博客主页：️自信不孤单

🍬文章专栏：数据结构与算法

🍚代码仓库：破浪晓梦

🍭欢迎关注：欢迎大家点赞收藏+关注

文章目录

🍊树的概念及结构
- 1. 树的概念
- 2. 树的相关概念
- 3.树的性质
- 4. 树的存储结构
- - 4.1 双亲表示法
  - 4.2 孩子表示法
  - 4.3 孩子兄弟表示法
- 5. 树在实际中的应用
🍓二叉树概念及结构
- 1. 二叉树的概念
- 2. 特殊的二叉树
- - 2.1 斜树
  - 2.2 满二叉树
  - 2.3 完全二叉树
- 3. 二叉树的性质
- 4. 二叉树的存储结构
- - 1. 二叉树的顺序结构
  - 2. 二叉树的链式结构
🍒二叉树的顺序结构实现
- 1. 堆的概念及结构
- 2. 堆的性质
- 3. 堆的实现
- - 3.1 初始化堆
  - 3.2 🍚堆的向上调整算法
  - 3.3 🍚堆的向下调整算法
  - 3.4 堆的插入
  - 3.5 堆的删除
  - 3.6 获取堆顶数据
  - 3.7 获取堆中数据个数
  - 3.8 堆的判空
  - 3.9 堆的销毁
- 4. 堆的应用
- - 4.1 堆排序
  - 4.2 Top-K问题
🍥二叉树的链式结构实现
- 1. 遍历二叉树
- - 1.1 前序遍历二叉树
  - 1.2 中序遍历二叉树
  - 1.3 后序遍历二叉树
  - 1.4 层序遍历二叉树
- 2. 通过前序遍历的数组构建二叉树
- 3. 二叉树结点个数
- 4. 二叉树叶子结点个数
- 5. 二叉树第k层结点个数
- 6. 二叉树查找值为x的结点
- 7. 二叉树的深度
- 8. 判断二叉树是否是完全二叉树
- 9. 二叉树的销毁

🍊树的概念及结构

1. 树的概念

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

有且仅有一个特定的称为根的结点。
当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

因此，树是递归定义的。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
树中所有结点可以有零个或多个后继。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构了，因此n个结点的树中有n-1条边。

2. 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：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）棵互不相交的树的集合称为森林；

3.树的性质

树中的结点数等于所有结点的度数加 $1$ 。

度为 $m$ 的树中第 $i$ 层上至多有 $m^{(n-1)}$ 个结点（ $\geqslant 1$ ）。

高度为 $h$ 的 $m$ 叉树至多有 $m^h - 1)/(m - 1)$ 个结点。

具有 $n$ 个结点的 $m$ 叉树的最小高度为 $log_2 (n(m - 1) + 1)]$ 。

4. 树的存储结构

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里我们来介绍几种表示方法：

4.1 双亲表示法

这里以数组的方式为例，在每个结点中，存储该结点的数据信息 data 以及双亲的位置 parent。
以下是双亲表示法的结点结构定义代码：

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 10
typedef int TElemType; // 树结点的数据类型
/*结点结构*/
typedef struct PTNode
{
	TElemType data; // 结点数据
	int parent; // 双亲位置
}PTNode;
/*树结构*/
typedef struct
{
	PTNode nodes[MAX_TREE_SIZE]; // 结点数组
	int r, n; // 根的位置和结点数
}PTree;

这样的存储结构可以根据结点的 parent 的值很容易找到它的双亲结点，直到 parent 为 -1 时，表示找到了树结点的根。可如果我们要想知道，某结点的孩子是什么，需要遍历整个结构。

4.2 孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。如下图：

设计两个结点，一个孩子结点，一个表头结点。孩子结点中 child 是数据域，用来存储某个结点在表头数组中的下标。next 是指针域，用来存储指向某结点的下一个孩子结点的指针。表头结点中 data 是数据域，存储某结点的数据信息。firstchild 是头指针域，存储该结点的孩子链表的头指针。
以下是孩子表示法的结点结构定义代码：

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 10
typedef int TElemType; // 树结点的数据类型
/*孩子结点*/
typedef struct CTNode
{
	int child;
	struct CTNode* next;
}*ChildPtr;
/*表头结点*/
typedef struct
{
	TElemType data;
	ChildPtr firstchild;
}CTBox;
/*树结构*/
typedef struct
{
	CTBox nodes[MAX_TREE_SIZE]; // 结点数组
	int r, n; // 根的位置和结点数
}

这样的存储结构对于我们要查找某个结点的某个孩子，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。但是我们要想找到某个结点的双亲，还需要遍历整个结构。

4.3 孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和该结点的右兄弟。如下图：

以下是孩子表示法的结点结构定义代码：

/*树的孩子兄弟表示法结构定义*/
typedef int TElemType; //树结点的数据类型
typedef struct CSNode
{
	TElemtype data;
	struct CSNode* firstchild, * rightsib;
} CSNode, * CSTree;

5. 树在实际中的应用

在这里插入图片描述

🍓二叉树概念及结构

1. 二叉树的概念

二叉树是一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树是 n (n≥0) 个结点的有限集合:

或者为空二叉树，即n=0。
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树的5种基本形态如图所示：

2. 特殊的二叉树

2.1 斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

2.2 满二叉树

在这里插入图片描述

一棵高度为 $h$ ，且含有个 $2^h-1$ 结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 $2$ 。可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 $1$ ）起，自上而下，自左向右。这样，每个结点对应一个编号,对于编号为 i 的结点，若有双亲，则其双亲为 $i /2$ ，若有左孩子，则左孩子为 $2 i$ ；若有右孩子，则右孩子为 $2 i + 1$ 。

2.3 完全二叉树

在这里插入图片描述

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于高度为 $h$ 的，有 $n$ 个结点的二叉树，当且仅当其每一个结点都与高度为 $h$ 的满二叉树中编号从 $1$ 至 $n$ 的结点一一对应时称之为完全二叉树。满二叉树就是一种特殊的完全二叉树。

若 $\leqslant n/2$ ，则结点 $i$ 为分支结点，否则为叶子结点。

叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。

若有度为 $1$ 的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。

按层序编号后，一旦出现某结点（编号为 $i$ ）为叶子结点或只有左孩子，则编号大于 $i$ 的结点均为叶子结点。

若 $n$ 为奇数，则每个分支结点都有左孩子和右孩子；若为偶数，则编号最大的分支结点（编号为 $n /2$ ）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

3. 二叉树的性质

任意一棵树，若结点数量为 $n$ ，则边的数量为 $n - 1$ 。
非空二叉树上的叶子结点数等于度为 $2$ 的结点数加 $1$ ，即 $n_0=n_2+1$ 。
非空二叉树上第 $k$ 层上至多有 $2^{k-1}$ 个结点（ $\geqslant 1$ ）。
高度为 $h$ 的二叉树至多有 $2^h-1$ 个结点（ $\geqslant 1$ ）。
对完全二叉树按从上到下、从左到右的顺序依次编号 $0, 1, \dots, n$ ，则有以下关系：

$i > 0$ 时，结点 $i$ 的双亲的编号为 $(i - 1) /2$ ，即当 $i$ 为奇数时，它是双亲的左孩子；当 $i$ 为偶数时，它是双亲的右孩子。
当 $2 i + 1 < n$ 时，结点的左孩子编号为 $2 i + 1$ ，否则无左孩子。
当 $2 i + 2 < n$ 时，结点 $i$ 的右孩子编号为 $2 i + 2$ ，否则无右孩子。
结点 $i$ 所在层次（深度）为 $log_2 (i+1)]+1$ 。（方括号表示向下取整）

具有 $n$ （ $n > 0$ ）个结点的完全二叉树的高度为 $log_2 n]+1$ 。（方括号表示向下取整）
具有 $n$ （ $n > 0$ ）个结点的满二叉树的高度为 $log_2 (n+1)$ 。

4. 二叉树的存储结构

1. 二叉树的顺序结构

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 $i$ 的结点元素存储在一维数组下标为 $i - 1$ 的分量中。

依据二叉树的性质，使用顺序结构数组只适合表示完全二叉树和满二叉树，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。在实际应用中，堆的实现就很好的体现了这一结构。二叉树的顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2. 二叉树的链式结构

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。我们称这样的链表叫做二叉链表。

在含有 $n$ 个结点的二叉链表中，含有 $n + 1$ 个空链域。

/*二叉树的二叉链表结点构造定义*/
/*结点结构*/
typedef int TElemType;
typedef struct BTNode {
	TElemType data;	// 结点数据
	struct BTNode* lchild, * rchild;	// 左右孩子指针
} BTNode, * BTree;

🍒二叉树的顺序结构实现

1. 堆的概念及结构

如果有一个关键码的集合 $K=\{k_0，k_1， k_2，…，k_{n-1}\}$ ，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： $\leqslant K_{2*i+1}$ 且 $\leqslant K_{2*i+2}$ （ $\geqslant K_{2*i+1}$ 且 $\geqslant K_{2*i+2}$ ）（其中 $i = 0, 1, 2, \dots$ ），则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2. 堆的性质

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

堆总是一棵完全二叉树。

3. 堆的实现

首先创建两个文件来实现堆：

Heap.h（节点的声明、接口函数声明、头文件的包含）
Heap.c（堆接口函数的实现）

如图：

Heap.h 文件内容如下：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType*  a;
	int size;
	int capacity;
}Heap;

// 堆的初始化
void HeapInit(Heap* php);
// 堆的向上调整
void AdjustUp(HPDataType* a, int child);
// 堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 获取堆顶数据
HPDataType HeapTop(Heap* php);
// 获取堆中数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);

接下来我们在 Heap.c 文件中实现各个接口函数。

3.1 初始化堆

对堆进行置空。

void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

3.2 🍚堆的向上调整算法

当我们在堆尾插入数据时，需要进行调整使其仍然是堆，就要用到堆的向上调整算法。

以向上调整算法的基本思想（以建小堆为例）：

将目标结点与其父结点比较。

若目标结点的值比其父结点的值小，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是小堆了。

图解：

代码实现：

// 交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{
	assert(p1);
	assert(p2);
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType*  a, int child)
{
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}

拓展：

向上调整一次的时间复杂度为 $O(\log N)$ 。

向上调整建堆的思路：

从第一个结点开始，依次向上调整即可。

向上调整建堆的时间复杂度为 $O(N*\log N)$ 。

向上调整建堆的代码实现：

for (int i = 0; i < n; i++)
{
	AdjustUp(a, i);
}

3.3 🍚堆的向下调整算法

现在我们给出一个数组，逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

使用向下调整算法需要满足一个前提：

若想将其调整为小堆，那么根结点的左右子树必须都为小堆。

若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

向下调整算法的基本思想（以建小堆为例）：

从根结点处开始，选出左右孩子中值较小的孩子。
让小的孩子与其父亲进行比较。若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

图解：

代码实现：

// 交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{
	assert(p1);
	assert(p2);
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])	//右孩子存在且比左孩子小
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

拓展：

向下调整一次的时间复杂度为 $O(\log N)$ 。

使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意完全二叉树调整为堆呢？

答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

向下调整建堆的代码实现：

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    AdjustDown(a, n, i);
}

那么向下调整建堆的时间复杂度为多少呢？

当结点数无穷大时，完全二叉树与其层数相同的满二叉树相比较来说，它们相差的结点数可以忽略不计，所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。

建堆过程中最坏情况交换的次数：

$\times (h-1)+2 \times (h-2)+2^{h-2} \times 1$

通过求和我们得出

$T(n)=2^h-h-1$

由二叉树的性质得 $N=2^h-1$

则 $h=\log_2(N+1)$

所以 $T(n)=N-\log_2(N+1)$

用大O的渐近表示法：

$T (N) = O (N)$

最终推出向下调整建堆的时间复杂度为 $O (N)$ 。

3.4 堆的插入

先判断扩容，然后将结点插到堆数组的最后，再进行向上调整操作。

void HeapPush(Heap* php, HPDataType x)
{

	assert(php);
	if (php->capacity == php->size)
	{
		int NewCapacity = php->capacity == 0 ? 5 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, NewCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = NewCapacity;
	}
	php->size++;
	php->a[php->size - 1] = x;
	AdjustUp(php->a, php->size - 1);
}

3.5 堆的删除

堆的删除是指删除堆顶元素。

实现思路：

如果非空就将堆顶结点与最后一个结点交换，然后去掉最后一个结点，将堆顶结点进行向下调整操作。

void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

3.6 获取堆顶数据

断言判空，返回堆顶元素的值。

HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

3.7 获取堆中数据个数

返回堆中数据个数。

int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

3.8 堆的判空

堆非空返回ture，否则返回false。

int HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

3.9 堆的销毁

释放动态开辟好的内存，并对数据进行置空。

void HeapDestory(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

4. 堆的应用

堆的应用相对广泛，我们在此仅介绍堆排序和Top-K问题。

4.1 堆排序

堆排序是利用堆的思想进行的排序，是一种选择排序。时间复杂度为 $O(N*\log N)$ ，它也是一种不稳定排序。

实现分为两步：

建堆。

升序：建大堆
降序：建小堆

利用堆删除思想进行排序。

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

实现具体思路（以升序为例）：

将待排序的 $n$ 个元素构建成一个大堆。此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾元素为最大值。
然后将剩余 $n - 1$ 个元素通过向下调整的重新建成大堆，这样会得到 $n$ 个元素的次大值。如此反复执行，便能得到一个有序序列了。

堆排序动图演示网站

代码实现：

void HeapSort(HPDataType* a, int n)
{
    // 向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
    
	for (int i = n - 1; i >= 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

4.2 Top-K问题

求数据集合中前K个最大元素或最小元素，一般情况下数据量都比较大。

基本思路：

用数据集合中前 $K$ 个元素来建堆。
求前 $k$ 个最大的元素，则建小堆。
求前 $k$ 个最小的元素，则建大堆。

用剩余的 $N - K$ 个元素依次与堆顶元素来比较，不满足则替换堆顶元素。

剩余 $N - K$ 个元素依次与堆顶元素比完之后，堆中剩余的 $K$ 个元素就是所求的前 $K$ 个最小或者最大的元素。

接下来，我们通过文件操作的方式来实现。首先在文件中造10000个随机数据，然后再执行以上思路。

代码实现：

// 造数据
void CreateNDate()
{
	int n = 10000;
	srand((unsigned int)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
    
	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
    
	fclose(fin);
}

//打印最大的前K个数据
void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
    
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc error");
		return;
	}
    
    // 存入前k个数据
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}
    
	// 建小堆
	for (int i = (k-1-1)/2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
    
    // 比较
	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}
    
    // 打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}

🍥二叉树的链式结构实现

根据二叉树的概念，我们发现链式结构能更清晰地表示二叉树。二叉树每个结点最多有两个孩子，所以我们设计一个数据域和两个指针域，数据域存放该节点的数据，指针域存放左右孩子指针。

二叉树链式结构的结点定义代码：

/*二叉树的二叉链表结点构造定义*/
/*结点结构*/
typedef char TElemType;
typedef struct BTNode {
	TElemType data;	// 结点数据
	struct BTNode* lchild, * rchild;	// 左右孩子指针
} BTNode;

1. 遍历二叉树

动图演示点这里！！！

1.1 前序遍历二叉树

前序遍历：先根再左再右

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->lchild);
	BinaryTreePrevOrder(root->rchild);
}

1.2 中序遍历二叉树

中序遍历：先左再根再右

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreeInOrder(root->lchild);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->rchild);
}

1.3 后序遍历二叉树

后序遍历：先左再右再根

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreePostOrder(root->lchild);
	BinaryTreePostOrder(root->rchild);
	printf("%c ", root->data);
}

1.4 层序遍历二叉树

从上到下从左往右依次遍历

我们发现层序遍历的特点是根据根、左、右的顺序遍历每个结点。于是我们想到让根结点入队列，出队列时再将该节点的左右孩子依次入队列，直到队列为空则层序遍历结束。

队列结点及各接口函数定义

void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Queue* qu = (Queue*)malloc(sizeof(Queue));
	QueueInit(qu);
	QueuePush(qu, root);
	while (!QueueEmpty(qu))
	{
		BTNode* ret = QueueFront(qu);
		if (ret)
		{
			printf("%c ", ret->data);
			QueuePush(qu, ret->lchild);
			QueuePush(qu, ret->rchild);
		}
		else
			printf("N ");
		QueuePop(qu);
	}
	QueueDestroy(qu);
	free(qu);
	printf("\n");
}

2. 通过前序遍历的数组构建二叉树

给定前序数组（其中空节点用#表示），通过前序递归开辟并连接结点。

BTNode* BTBuyNode(TElemType x)
{
	BTNode* ret = (BTNode*)malloc(sizeof(BTNode));
	if (!ret)
	{
		perror("malloc fail");
		return NULL;
	}
	ret->lchild = NULL;
	ret->rchild = NULL;
	ret->data = x;
	return ret;
}

BTNode* BinaryTreeCreate(TElemType* a, int n, int* pi)
{
	if (*pi == n)
	{
		return NULL;
	}

	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = BTBuyNode(a[*pi]);
	(*pi)++;

	root->lchild = BinaryTreeCreate(a, n, pi);
	root->rchild = BinaryTreeCreate(a, n, pi);

	return root;
}

3. 二叉树结点个数

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->lchild) +
		BinaryTreeSize(root->rchild) + 1;
}

4. 二叉树叶子结点个数

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->lchild == NULL && root->rchild == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->lchild) +
		BinaryTreeLeafSize(root->rchild);
}

5. 二叉树第k层结点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->lchild, k - 1) +
		BinaryTreeLevelKSize(root->rchild, k - 1);
}

6. 二叉树查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, TElemType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* l = BinaryTreeFind(root->lchild, x);
	if (l)
	{
		return l;
	}

	BTNode* r = BinaryTreeFind(root->rchild, x);
	if (r)
	{
		return r;
	}

	return NULL;
}

7. 二叉树的深度

int BinaryTreeMaxDepth(BTNode* root) {
	if (root == NULL)
		return 0;
	int l = BinaryTreeMaxDepth(root->lchild);
	int r = BinaryTreeMaxDepth(root->rchild);
	return l > r ? l + 1 : r + 1;
}

8. 判断二叉树是否是完全二叉树

通过层序遍历的方式找到第一个空节点，如果后面还有非空结点就不是完全二叉树，否则为完全二叉树。

bool BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
		return true;
	Queue* qu = (Queue*)malloc(sizeof(Queue));
	QueueInit(qu);
	QueuePush(qu, root);
	while (!QueueEmpty(qu))
	{
		BTNode* ret = QueueFront(qu);
		QueuePop(qu);
		if (ret)
		{
			QueuePush(qu, ret->lchild);
			QueuePush(qu, ret->rchild);
		}
		else
			break;
	}
	int result = true;
	while (!QueueEmpty(qu))
	{
		BTNode* ret = QueueFront(qu);
		if (ret)
		{
			result = false;
			break;
		}
		QueuePop(qu);
	}
	QueueDestroy(qu);
	free(qu);
	return result;
}

9. 二叉树的销毁

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->lchild);
	BinaryTreeDestory(root->rchild);
	free(root);
}