【数据结构】【版本2.0】【树形深渊】—

引言

一、树的概念与结构

1.1 树的概念

1.2 树的相关概念

1.3 树的表示

1.4 树在实际中的运用

二、二叉树的概念与结构

2.1 二叉树的概念

2.2 特殊二叉树

满二叉树

完全二叉树

2.3 现实中的二叉树

2.4 二叉树的性质

2.5 二叉树的存储结构

顺序存储

链式存储

三、二叉树的顺序结构及实现

3.1 堆的概念与结构

3.2 堆的实现

3.2.1 定义

3.2.2 初始化

3.2.3 销毁

3.2.4 判断堆是否为空

3.2.5 获取堆顶元素

3.2.6 获取堆的元素个数

3.2.7 入堆

3.2.8 出堆（删除堆顶元素）

3.3 堆排序

3.4 堆排序的应用（Top-K问题）

四、二叉树的链式结构及实现

4.1 前序、中序、后序遍历

4.1.1 前序遍历

4.1.2 中序遍历

4.1.3 后序遍历

4.2 节点个数及高度

4.2.1 二叉树节点个数

4.2.2 二叉树叶节点个数

4.2.3 二叉树的高度

4.2.4 二叉树第k层节点个数

4.2.5 二叉树查找值为x的节点

4.3 层序遍历

4.4 二叉树的创建及销毁

4.4.1 二叉树的销毁

4.4.2 二叉树的创建

4.4.3 判断是否为完全二叉树

五、二叉树oj题

个人专栏：《数据结构世界》

引言

数据结构世界暂时告别了线性大陆，来到了树形的天堂，首先迎来最经典的树——二叉树（Binary Tree）

数据结构世界中本只开辟了线性大陆，在其中不断迭代进化线性的力量，其余区域均为重重迷雾。但是，这一天，迷雾散开一角，露出深不见底的树形深渊，盘根杂枝，树影迷蒙。首先，二叉树入侵世界，它们拥有着与线性截然不同的力量，天生可以一心多用，同时还有一种强大的神通——空间递归。一时间，数据结构世界迎来了树形的恐惧，人人谈“树”色变

一、树的概念与结构

1.1 树的概念

树是一种 非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来 像一棵倒挂的树 ，也就是说它是根朝上，而叶朝下的 。

有一个特殊的结点，称为根结点，根节点没有前驱结点
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构 （有交集，就变成图了，更加复杂的数据结构，后面会讲）

每一个树，都是由双亲节点和N个子树构成的，所以可以递归定义

1.2 树的相关概念

概念：树+人类亲缘关系描述

这里高度有两种表示方法，，一种是直接看成1，另一种是把第一层看成0，这里推荐前者。

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

并查集中会用到森林

学好这些概念，后续才能进一步学习其他更复杂的树。比如：

AVL树

红黑树

B树系列（B树，B+树，B*树）

1.3 树的表示

树结构 相对线性表就比较复杂了，要存储表示起来就比较麻烦了， 既然保存值域，也要保存结点和结点之间的关系 ，实际中树有很 多种表示方式 如：

如果明确了树的度，那么可以直接定义
顺序表存储孩子
双亲表示法

当我们定义树节点的结构体时，如果知道树的度，可以直接定义指针的个数，但如果不知道呢？

有一种方法，那就是用顺序表来存储孩子节点的地址，也就是指针数组

也可以用顺序表来存储孩子节点的下标，如下图

除此之外，还有人想出来一些奇特的定义方法。比如双亲表示法，树节点中只存储双亲结点的地址（因为每个节点只有一个双亲结点），所以也可以从下往上找。还有一种方法，树节点中既存储双亲结点，也存储孩子节点……

当然，最后我们还是详细了解一种最常用的王者表示法——左孩子右兄弟表示法

相当于一个负责宽度（同层找兄弟），一个负责深度（同分支找孩子）

这样，我们就可以表示整个树的结构

1.4 树在实际中的运用

其实我们常用的Windows文件系统，就是一个森林。同级目录下的文件互为兄弟，上下级目录则为父子。还有后面准备学的Linux文件系统，就是一棵目录树。

二、二叉树的概念与结构

那么，对树有了基本的概念以后，我们来看一下一种特殊的树——二叉树

2.1 二叉树的概念

一棵二叉树 是结点的一个有限集合，该集合 :

或者为空
由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2 特殊二叉树

满二叉树

每一层都是满的，节点个数为2^h - 1（利用等比数列求和公式）

完全二叉树

前h-1层都是满的，最后一层可以不满，但从左到右是连续的
节点范围是 [ 2^(h-1) , 2^h - 1 ]（前h-1层个数再加一，就为2^(h-1)）

要注意的是满二叉树是一种特殊的完全二叉树。

2.3 现实中的二叉树

程序员看到肯定要去膜拜一下，多么标准的（满）二叉树啊！

2.4 二叉树的性质

tips：这里的性质不用强行记忆，随着后面刷题和对二叉树认知加深慢慢就融会贯通了。

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 m, 度为2的分支结点个数为 n,则有 m=n+1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1)（以2为底）

5. 对于具有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否则无右孩子

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。
二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

父子间下标关系：

1.父亲找孩子：leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

2.孩子找父亲：parent = (child - 1) / 2

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

三、二叉树的顺序结构及实现

3.1 堆的概念与结构

现实中我们通常把 堆(一种二叉树) 使用 顺序结构的数组来存储

注意： 这里的堆和 操作系统虚拟进程地址空间中的堆 是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段

堆的性质：

完全二叉树
堆中某个节点的值总是不大于或者不小于其父节点的值

好好理解这句话：堆的逻辑结构是二叉树，物理结构是数组！

3.2 堆的实现

3.2.1 定义

3.2.2 初始化

3.2.3 销毁

这里注意，不要对整个堆进行空间释放，因为堆这个结构体不是动态开辟的，只能对堆里的数组进行空间释放。

3.2.4 判断堆是否为空

3.2.5 获取堆顶元素

3.2.6 获取堆的元素个数

3.2.7 入堆

前面几个都非常简单，所以不多做介绍了（详情请看往期--线性时代）。现在来到了关键点——入堆。首先和往常一样，先判断是否需要扩容，再将入堆元素插入数组末尾。

做完这一切，我们才真正来到入堆的精华。将数组想象成一棵二叉树，那么刚刚插入的元素就在树的最底层。因为要保持任意一个元素都大于父节点（假设这里是小堆），所以我们就要根据父子间的下标关系进行调整，这种算法称为向上调整算法。

具体做法：

判断该节点（孩子）与其父节点的大小，如果孩子小于父亲，则交换。
再让原本的孩子（如今变成了父亲）继续向上比较，直到孩子大于等于父亲，则跳出循环
循环的条件是孩子节点的下标大于0（注意，这里不能写成父节点下标大于等于0，因为父亲下标永远大于0。孩子为0后，父亲也为0，还是会进循环，然后break，所以逻辑不合理）

AdjustUp(php->a, php->size-1);

所以push最后加上向上调整，将数组和尾部元素下标传过去，调整完保持还是一个堆。

3.2.8 出堆（删除堆顶元素）

入堆讲完了，我们再来将另一个重点——出堆。大家觉得出堆应该从哪出，队尾？不，那没有任何意义。出堆应该从堆顶出，也就是二叉树的根节点。

但是，如果直接向前挪动覆盖，那父子关系就全乱了，堆也就不存在了，需要重新建堆，代价太大了。所以，如果我们要保持原有的堆的结构，那要怎么删除呢？

有一种做法可以达到目的，那就是先把首尾元素交换，再size--。这时就保持除了根节点，其余两棵子树都是堆，这时我们只要利用父子间下标关系进行调整即可，这种算法称为向下调整算法

具体做法：

先假设我们要比较的孩子是左孩子，再进行判断比较左孩子和右孩子的大小，如果右孩子更小，则child++，下标再改为右孩子；如果左孩子小，则保持不变
然后再用当前的节点（父节点）与更小的孩子进行比较，如果孩子比父亲更小，则父子交换
再让原本的父亲（如今的孩子）继续向下进行比较调整，直到孩子大于等于父亲，则跳出循环
注意，循环的条件是孩子下标小于数组长度；同时，因为左孩子存在时，右孩子不一定存在，所以1中的条件判断还要补上child+1<n，保证右孩子在数组时才进行比较

堆的测试及运行结果

这样，我们先将数组元素入堆，再不断获取堆顶元素，再删除，就可以实现升序打印（小堆实现）

源代码

heap.h

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

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

//初始化
void HPInit(HP* php);
//销毁
void HPDestroy(HP* php);
//入堆
void HPPush(HP* php, HPDataType x);
//删除堆顶元素
void HPPop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
//获取堆顶元素
HPDataType HPTop(HP* php);
//获取堆的元素个数
int HPSize(HP* php);

void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);

heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

void HPInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->capacity = php->size = 0;
}

void HPDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

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

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size++] = x;

	AdjustUp(php->a, php->size-1);
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}

int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

void TestHeap1()
{
	HP hp;
	HPInit(&hp);
	int arr[] = { 4,3,2,50,65,44,12,78,95,35 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	for (i = 0; i < sz; i++)
	{
		HPPush(&hp, arr[i]);
	}

	while (!HPEmpty(&hp))
	{
		printf("%d\n", HPTop(&hp));
		HPPop(&hp);
	}

	HPDestroy(&hp);
}

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

3.3 堆排序

沿用刚刚的思路，那堆排序是不是就是这样呢？请看下面代码：

先将待排序数组元素全部入堆，再不断取堆顶元素放入数组中。好像很有道理，对吧？

但是这样排序有很多缺点：

需要先实现一个堆（想想我们为了实现一个堆写了多少代码？）
空间复杂度高+来回拷贝数据

所以，有没有一种更简单的方法实现堆排序呢？有！

具体做法：

既然我们不想要实现一个堆，那么我们可以直接操作原数组，将其变成堆即可。将数组调整成堆，我们用向上调整算法（这里建小堆）
建好小堆后，利用堆删除思路，再首尾元素交换，选出最小的放在末尾
再将前n-1个元素进行向下调整算法，选出次小的
不断循环重复以上步骤，则最后将所有的元素排序完毕

堆排序的大体思路是这样的，但是，其实堆的创建除了向上调整算法，也可以用向下调整算法，而且速度更快，可以达到优化的效果。

但是，这里用向下调整算法，和堆删除时不同，因为用向下调整算法的前提，是左右子树都为堆。这里一般肯定都不符合，因为要排序的数组肯定是杂乱无章的，所以怎么办呢？

实现思路：

我们可以从下往上，因为可以把叶节点看作是堆，所以从倒数第二层（最后一个节点的父亲）开始用向下调整算法
因此逐渐从下往上把一个个小子树排成堆，最后直到根节点，这样就可以一直满足左右子树都为堆

时间复杂度分析与对比

向上调整算法

简单的运用错位相减法化简即可

向下调整算法

所以我们就通过精确的计算来得到向下调整算法比向上调整算法更快，时间复杂度更优——O(N)。因此，以后我们在写堆排序时，就只用写向下调整算法！（三个愿望一次满足）

其实我们还可以发现，创建好堆后，第二部分排序用向下调整算法时，时间复杂度与创建堆时向上调整算法相同，为O(N*logN)

所以，堆排序整体时间复杂度为O(N+N*logN)，忽略小量来说就是O(N*logN)

这样，我们就实现了真正简单实用的堆排序。运行结果如下：

值得注意的是

小堆排序——排序结果为降序
相反，大堆排序——升序

代码如下：

void HeapSort(int* a, int n)
{
	//降序--建小堆
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);//向上调整--建小堆
	//}
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);//向下调整--建小堆
	}

	int end = n - 1;//尾部元素下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//首尾交换,选出最小的
		AdjustDown(a, end, 0);//隔绝尾部元素，向下调整，选出次小的
		end--;
	}
 }

void HeapSort(int* arr, int sz)
{
	HP hp;
	HPInit(&hp);

	int i = 0;
	for (i = 0; i < sz; i++)
	{
		HPPush(&hp, arr[i]);
	}

	i = 0;
	while (!HPEmpty(&hp))
	{
		arr[i++] = HPTop(&hp);
		HPPop(&hp);
	}

	HPDestroy(&hp);
}

void TestHeap2()
{
	int arr[] = { 4,3,2,50,65,44,12,78,95,35 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, sz);
}

3.4 堆排序的应用（Top-K问题）

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，正常思路：

把N个数据建成堆
再pop K次

但是，如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，改进思路如下：

用数据集合中前K个元素来建堆 （前k个最大的元素，则建小堆；前k个最小的元素，则建大堆）
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素，将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

那让我们来实战一下，先造出N个数据

配合使用srand和rand函数创造100w以内的随机数
使用文件操作的形式，将数据写入到文件中

创造好数据后，再来实现topk的筛选

首先打开文件，并读取k个数据创建小堆

其次，循环读取剩下的N-K个数据，与堆顶元素进行比较，如果大于它，则覆盖入堆，再进行向下调整算法
最后，打印堆中数据（最大的前K个），顺便释放动态开辟的堆空间

那这些数都是随机的，怎么检验自己的程序对不对呢？很简单，只要手动更改，让数值大于100w即可。

运行结果

代码如下：

void CreateNData()
{
	int n = 10000;
	srand((unsigned int)time(NULL));
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}

	int x = 0;
	for (int i = 0; i < n; i++)
	{
		x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopk(int k)
{
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

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

	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minheap[0])
		{
			minheap[0] = val;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int j = 0; j < k; j++)
	{
		printf("%d\n", minheap[j]);
	}

	free(minheap);
}

int main()
{
	CreateNData();
	PrintTopk(5);
	return 0;
}

四、二叉树的链式结构及实现

终于来到链式二叉树的部分，也是真正有难度的精华部分。关于链式二叉树的学习，我们不会像往期的数据结构一样，讲解它的增删查改，因为对于普通的链式二叉树并没有什么意义。只有到了后期的搜索二叉树，以及更高阶的AVL树，红黑树等等，对它们增删查改才有意义。

所以，现在学习的链式二叉树有两个目的：

掌握前序，中序，后序和层序遍历，为后期搜索二叉树的学习打基础
与单链表相同，大部分oj题也是以链式二叉树为考察对象的，为后期刷题做准备

4.1 前序、中序、后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则，依次对二 树中的节点进行相应的操作，并且每个节点只操作一次 。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

从现在开始，我们将任何一部分都看作根，左子树，右子树

前序（先根遍历）：根左子树右子树
中序（中根遍历）：左子树根右子树
后序（后根遍历）：左子树右子树根

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

4.1.1 前序遍历

遍历时我们用递归实现：

如果为空树，则直接返回（返回条件）
如果不为空时，则先访问根节点，再依次访问左子树和右子树（子问题）

运行结果：

4.1.2 中序遍历

同理，中序遍历只需把访问的顺序调换一下即可

这里我们可以手动算一算结果是多少，有助于加深我们对遍历方式的认知。

运行结果：

4.1.3 后序遍历

同理，后序遍历只需把访问的顺序调换一下即可

运行结果：

三条遍历的实现过程非常相似，只有细微的差别，但是背后的遍历方式与函数递归时栈帧的创建却需要我们多去画图思考与理解。

4.2 节点个数及高度

4.2.1 二叉树节点个数

方法一：遍历计数

根据刚刚遍历的思想，计算节点个数，每次递归经过一个节点时，size++

但是，思考一个问题，如果我们要在函数内定义size，那每次递归都会创建新的size变量，不能满足想要的效果。有同学可能会说，加上static修饰，变成局部静态变量，如下图。

看起来好像没问题，再看看运行结果。

我们发现，因为每次计算完节点个数，size没有置为0，导致后续计算错误。而且，因为size是局部静态变量，我们没有办法通过外部去修改，所以这种方法不可行。

那应该怎么办呢？其实很简单，把size设置为全局变量即可。

这样我们就能外部将size置为0，实现目的。

方法二：分治

上述方法是不是显得有些繁琐，每次都要将size置为0，所以我们有第二种更简便的方法——分治。什么是分治呢？简单来说，就是运用管理思维，分而治之。

假设一个场景，校长要统计全校的人数，那是不是就安排院长去统计，而院长又安排辅导员去统计……依此类推，最终全校人数经过一层层统计和汇总，交付到校长手中。而不是校长挨个去统计全校师生的人数。这样的效率是不是就很高了？

同理，想象一下，自下而上，让每个节点统计自身下面的节点个数，这样最后汇总到根节点时，就完成了对节点个数的统计。

如果为空树，返回0
如果为非空节点，返回左子树节点个数+右子树节点个数+1（本身节点）

这里熟练以后，还可以用三木操作符化简一下。

运行结果：

4.2.2 二叉树叶节点个数

那么如果我们要求叶节点的个数，按照刚刚分治的思路，只要稍微改动一下即可。

如果为空树，返回0
如果为叶节点，返回1
如果为分支节点，返回左子树叶节点个数+右子树叶节点个数

运行结果：

4.2.3 二叉树的高度

求二叉树的高度，同样运用分治的思维：

如果为空树，返回0
如果为非空节点，则计算出左右子树的高度，再进行比较。返回更大的高度+1

注意，要定义变量存储当前递归计算的左右子树高度，千万不要写成以下形式。看似没什么区别，实际上递归的次数呈几何倍增加，时间复杂度高，效率极其低下。

运行结果：

4.2.4 二叉树第k层节点个数

求二叉树第k层节点个数，分析递归问题时，我们都要弄清楚子问题和返回条件

子问题：转化为求左子树和右子树的第k-1层节点个数之和
返回条件：1.如果为空树，则返回0 2.如果不为空，且k==1，则返回1

运行结果：

4.2.5 二叉树查找值为x的节点

这里查找值为x的节点，要返回的是节点的地址，这样就可以进行修改。

同样，我们先确定一下返回条件

如果为空树，则返回NULL
如果为要查找的值，则返回root（节点地址）

但是这题分解子问题时，有点复杂，可能有人会写成这种形式

这样是不对的，因为后续子问题没有返回值。所以应该怎么做呢？

具体思路如下：

先查找左子树，如果左子树返回值不为空，则返回其返回值
再查找右子树，如果右子树返回值不为空，则返回其返回值（这样如果左子树先找到了，就不用查找右子树了）
注意，由之前的题的警示，我们在每次递归调用时，都存储一下当前的值，防止反复递归，效率太低
最后，如果左右子树返回值都为空，则返回NULL

4.3 层序遍历

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

那层序遍历要怎么实现呢？其实，这里用队列实现非常方便。

利用队列先进先出的性质，每一层的每个结点要出队列时，则将左右孩子带进队列，这样就达到层序遍历的效果。

具体做法：

因为C语言没有对应的库，所以我们将之前写好的队列源代码代码拷贝过来使用
创建队列并初始化，将根节点push入队
当队列不为空时循环，每次获取队头数据，再pop出队，打印树节点的数据
从左到右的顺序，如果孩子不为空，则将孩子节点依次push入队
最后销毁队列

注意，这里队列嵌套了三层，每个节点存储的数据，是树的根节点的地址（指针）

结构体定义：

函数定义：

运行结果：

4.4 二叉树的创建及销毁

4.4.1 二叉树的销毁

经过前面的磨练，相信二叉树的销毁对于各位只是小意思了~

比较方便的方式，是采用后序遍历，先销毁左子树，再销毁右子树，最后销毁根节点。

如果采用其余遍历，先销毁了根节点，那还要保存其地址，这样才能继续往下找。

返回条件：如果已经走到空树，那就不用销毁，直接return即可

使用时要注意，实现半自动，在外部手动置空（和free函数的逻辑一样）

4.4.2 二叉树的创建

经过前面对递归的认识不断加深，我们现在来研究正在创建二叉树的方法。

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

我们通过一道题目来理解二叉树的创建。

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行

大体思路：

先写出树节点的结构体定义和产生新节点的函数
再用数组来存储输入的字符串，将数组和下标i（注意要传址）传入创建二叉树的函数
最后写出中序遍历的函数

这里重点讲讲创建二叉树的函数实现

以前序遍历的形式创建二叉树，也是最常见的创建形式
返回条件：如果当前数组对应下标i的元素为#（表示空），则pi解引用++，再返回NULL
如果不为#，则创建新节点，将数组对应元素放入，同时pi解引用++
子问题：创建完根节点后，继续以先左后右的方式，不断递归创建新节点，最后返回root

代码如下图，其实大家会发现，好像也没有想象中那么难，就是前序遍历的小小改版。（因为大家对递归的掌握更加深刻了）

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTNode* BTreeCreat(char* a, int* pi)
{
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode* root = BuyNode(a[(*pi)++]);
    root->left = BTreeCreat(a, pi);
    root->right = BTreeCreat(a, pi);

    return root;
}

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }

    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}

int main()
{
    char a[100];
    scanf("%s",a);
    int i = 0;
    BTNode* root = BTreeCreat(a, &i);
    InOrder(root);
    return 0;
}

4.4.3 判断是否为完全二叉树

判断一棵二叉树是否为完全二叉树，先回忆一下完全二叉树的定义：前n-1层都为满，最后一层可以不满，但从左到右必须连续。

思路：根据这个特性，我们可以采取层序遍历，如果遇到空以后，还有非空，则不为完全二叉树；如果遇到空后，后面全是空，则为连续，为完全二叉树

具体方法：

采用层序遍历，则创建队列并初始化，将根节点push入队
队列非空则循环，不断取队头元素并pop出队。判断取出的元素是否为空，如果为空，则break跳出循环；如果不为空，则继续把根节点的左右孩子push入队
再进入另一层循环，同样取队头元素。不过判断条件改为，如果元素不为空，则销毁队列，return false
如果等到全部元素取完，还没有return false，则证明后面全为空，为完全二叉树，则销毁队列，return true

运行结果：

关于二叉树，其实还没有完全讲完，只是暂时告一段落。剩下的部分，后续会在C++中讲解，因为用C++做会方便不少。

源代码

queue.h

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

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

typedef BTNode* QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//检测队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);

queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);

	return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);

	return pq->ptail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"


BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

int size1 = 0;

void BTreeSize1(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size1++;

	BTreeSize1(root->left);
	BTreeSize1(root->right);
}

//int BTreeSize(BTNode* root)
//{
//	static int size = 0;
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//
//	BTreeSize(root->left);
//	BTreeSize(root->right);
//	return size;
//}

int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BTreeSize(root->left)
		+ BTreeSize(root->right) + 1;

	//if (root == NULL)
	//{
	//	return 0;
	//}

	//return BTreeSize(root->left)
	//	+ BTreeSize(root->right) + 1;
}

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL
		&& root->right == NULL)
	{
		return 1;
	}

	return BTreeLeafSize(root->left)
		+ BTreeLeafSize(root->right);
}

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);

	return leftHeight > rightHeight ? 
		leftHeight + 1 : rightHeight + 1;
}

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

	if (k == 1)
	{
		return 1;
	}

	return BTreeLevelKSize(root->left, k - 1)
		+ BTreeLevelKSize(root->right, k - 1);
}

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BTNode* leftRoot = BTreeFind(root->left, x);
	if (leftRoot)
	{
		return leftRoot;
	}

	BTNode* rightRoot = BTreeFind(root->right, x);
	if (rightRoot)
	{
		return rightRoot;
	}

	return NULL;
}

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	QueueDestroy(&q);
}

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root); 
}

bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

int main()
{
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
	InOrder(root);
	PostOrder(root);

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

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

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

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

	printf("%d\n", BTreeLevelKSize(root, 1));
	printf("%d\n", BTreeLevelKSize(root, 2));
	printf("%d\n", BTreeLevelKSize(root, 3));

	BTNode* pos = BTreeFind(root, 3);

	LevelOrder(root);

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

	BTreeDestroy(root);
	root = NULL;
	return 0;
}