【数据结构】二叉树

一. 树的概念及结构

1.树的概念

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

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

2. 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1,T2,T3……Tn，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继。

3. 因此，树是递归定义的。

注意：

1. 树形结构中，子树之间不能有交集，否则就不是树形结构。
2. 除了根结点外，每个结点有且仅有一个父结点。
3. 一颗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）棵互不相交的树的集合称为森林；

最近公共祖先:距离某些结点最近的祖先，比如P和Q的最近公共祖先为J，K和F的最近公共祖先为F。结点本身也可以成为自己的祖先

注意：有颜色的为重点掌握，其余只需了解即可。

3.树的表示

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

孩子表示法

树结构相对线性表就比较复杂了，因为不知道孩子的数量。但如若知道树的度，那就很好定义了。

#define N 5
struct TreeNode
{
	int data[N];
	struct TreeNode* childArr[N];//指针数组，每个节点存5个数据
    //指向孩子的指针
	int childSize;
};

但是又有一个缺陷，既然树的度为5，但是你这样设定只会导致每个结点的度均为5，可实际上只要保证每个结点的度<=5即可，如果树的度非常大，如50，而有的树节点很小，如2，5，10等，由此可见，此法开辟造成空间浪费。此外，如果不知道树的度，那么用上述方法定义就比较困难了。这跟我们之前实现的静态顺序表差不多，这里我们同样可以把它改成动态的树。

struct TreeNode
{
	int* data;
	//顺序表存储孩子节点指针
	struct TreeNode** childArr;
	int childSize;
	int childCapacity;
};

注意：这里的孩子节点的指针要变成二级指针，静态的树的孩子结点指针是指针数组，里面存放的是指针；而动态的树的孩子结点指针是二级指针，* childArr中这个* 代表childArr是一个动态数组（指针），里面存放的同样是指针，struct TreeNode* 是数组元素的数据类型。

左孩子右兄弟法

typedef int DataType;
struct TreeNode
{
	struct Node* firstChild1;   //存放第一个孩子结点的地址
	struct Node* pNextBrother;  //存放下一个兄弟结点的地址
	DataType data;    //结点中的数据域
};

假设我们要表示的树如下图：

物理结构如下：

简化一下：

分析：由上图代码图画演示及树的结构得知，根结点A是有B和C两个孩子，让A的leftchild指向第一个孩子B，A的其它孩子C让B的兄弟指针去指向，C没有兄弟了，直接指向NULL。同理，B有3个孩子，让leftchild指针指向第一个孩子D，再让D的兄弟指针指向下一个E，以此类推……此法就很好的显示了一个结点有多少个孩子都无所谓，直接让父亲指向第一个孩子，剩下的孩子用孩子的兄弟指针链接起来。

双亲表示法

这里我们用双亲表示法来表示这棵树(跟上面有所不同）。这里我们了解即可，暂时还用不到。

4.树在实际生活中的应用

树在我们实际生活中的应用之一就是用于表示文件系统的目录：

这是Linux系统存储文件的目录，以后我们就会学习企业最常用的Linux系统，Linux系统存储文件用的就是树的结构。

二. 二叉树的概念及结构

1.二叉树的概念

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

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

从上图可以看出：

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

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

2.生活中的二叉树

我们现实生活中的二叉树长什么样子呢？这里有两张图：

当普通人看到这两棵树时的反应是：张口就是国粹，这两棵树好对称啊！！！

但是当一个程序猿看到它们时的反应就会是：张口同样是国粹，二叉树成精了！！！

所以大家知道怎么区分程序猿和普通人了吗😜😜😜

3.特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

简单来说，满二叉树的每个结点的度均为2，满二叉树是完全二叉树的特殊情况。当深度为K时，完全二叉树就是在[1，k-1]层的区间内均为满二叉树，只有最后一层第K层不满，但是最后一层是从左往右连续的。图示：

4.二叉树的性质

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

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

性质3：对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1

性质4：若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(N+1)

性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1=n否则无左孩子
3. 若2i+2=n否则无右孩子

注：性质5的相关知识会在下面的存储结构中展开拓展

光说不练假把式，拿几道题练练手。

1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199

答案：B

解析：直接利用性质3，叶节点就是度为0，n0总是比n2度为2的结点多1，所以n0=200，选B。

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

答案：A

解析：由前文可得，完全二叉树每个结点的度最大是2，最小为0，设度为i的结点个数为ni，其中i属于[0，2]。

结点总数为2n，则2n=n2+n1+n0，因为是二叉树，存在n0-1=n2，则式子变为n0-1+n1+n0=2n。又因完全二叉树，n1只能为0或1，又要确保结果是偶数，所以n1为1，综上，n0=n，选A。

3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

答案：B

解析：假设高度为h，当结点最多时，此二叉树是满二叉树，那么满足性质2，2^h-1=531，由此得出h为log₂(532)，此情况是高度最小值。当结点最少时，也就是说第1到h-1层均是度为2的结点，只有最后一层第h层只有1个结点。此时列式：2 ^(h-1)-1+1=531，解得h为log2(531)+1，而此情况是树的高度的最大值，树的取值范围（log₂(532)，log₂(531)+1）取整，得到h为10，选B。

4.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

答案：B

解析：和第3题差不多，结点总数为767，则767=n2+n1+n0，因为是二叉树，存在n0-1=n2，则式子变为n0-1+n1+n0=767。又因完全二叉树，n1只能为0或1，又要确保结果是奇数，所以n1为0，综上，n0=B，选B。

5.二叉树的存储结构

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

顺序存储

下面我们来表示如下的完全二叉树（逻辑结构）

此时我们尝试用数组去存储（物理结构）

我们将上述逻辑结构中树的数据存在数组里头，用下标来代表不同的数据，以便于访问。此时，我们就要将这块数组想象成”树“，怎么做呢？见下图：

只需要将数组还原成树的样子即可，如上图。

既然图画出来了，现在有个问题。如何理清父亲与孩子的关系呢？
首先，假设父亲的下标为parent，左孩子的下标为leftchild，右孩子的下标为rightchild，则父子间下标关系如下：

leftchild = parent * 2 + 1
rightchild = parent * 2 + 2
parent = (child - 1) / 2
解析：由图中不难发现，所有左孩子的下标均为奇数，而右孩子下标均为偶数，所以不难得出左右孩子的表达式。相反可以推出父亲的表达式。

但是父亲的式子中，只是(child - 1) / 2，并没有区分左右孩子，这是为什么呢？
这里我们假设leftchild和rightchild的下标均为3，算出来的parent下标不难发现均为1，同理左右孩子下标均为4时，父亲的下标算出来都是1，由此规律可得知直接用child下标表示父亲即可，无需区分左右孩子。

链式存储

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

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{	
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}		
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；

6.非完全二叉树的存储结构

在前几篇博文中，我们学习的都是完全二叉树或满二叉树，而这两个都是可以用数组来实现的，但是如果不是完全二叉树呢？

由上图得知，普通二叉树也可以使用数组来存储，但是会存在大量的空间浪费，而完全二叉树就不会这样，因为其空间利用率100%的。既然这样，那普通二叉树该如何进行存储呢？答案是使用链式结构进行存储。

链式二叉树和我们之前的学习略有差别。以前我们学习的数据结构无非就是增删查改这些东西，而链式二叉树不太关注这块的增删查改。因为普通二叉树的增删查改没有意义。如下的二叉树：

链式二叉树是要比之前的链表更加复杂的，如果只是单纯的让链式二叉树存储数据的话，价值就不大了，不如使用线性表。接下来，我将通过其遍历方式，结点个数……为大家展开讨论。此节内容是为了后续学习更复杂的搜索二叉树打基础，具体是什么后面再谈。

在具体讲解之前，再回顾下二叉树，二叉树是：
空树
非空：根节点，根节点的左子树、根节点的右子树组成的。

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

三.二叉树的基本操作

1.手动创建一颗二叉树

其实构建一棵树的思想还是挺简单的，按照图示创建6个节点，并根据上图中的样子将节点顺次链接起来。

#include 
#include 
#include 

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

//法一：
BTNode* CreateBinaryTree()
{
	BTNode* node1 = (BTNode*)malloc(sizeof(BTNode));
	assert(node1);
	BTNode* node2 = (BTNode*)malloc(sizeof(BTNode));
	assert(node2);
	BTNode* node3 = (BTNode*)malloc(sizeof(BTNode));
	assert(node3);
	BTNode* node4 = (BTNode*)malloc(sizeof(BTNode));
	assert(node4);
	BTNode* node5 = (BTNode*)malloc(sizeof(BTNode));
	assert(node5);
	BTNode* node6 = (BTNode*)malloc(sizeof(BTNode));
	assert(node6);

	node1->data = 1;
	node2->data = 2;
	node3->data = 3;
	node4->data = 4;
	node5->data = 5;
	node6->data = 6;
	
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node2->right = NULL;
	node3->left = NULL;
	node3->right = NULL;
	node4->left = node5;
	node4->right = node6;
	node5->left = NULL;
	node5->right = NULL;
	node6->left = NULL;
	node6->right = NULL;
	
    return node1;
}

//法二：
//创建结点
//BTNode* CreateBTNode(BTDataType x)
//{
//	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//	if (node == NULL)
//	{
//		printf("malloc fail\n");
//		exit(-1);
//	}
//	node->data = x;
//	node->left = node->right = NULL;
//	return node;
//}
构建树
//BTNode* CreatBinaryTree()
//{
//	//创建6个结点
//	BTNode* node1 = CreateBTNode(1);
//	BTNode* node2 = CreateBTNode(2);
//	BTNode* node3 = CreateBTNode(3);
//	BTNode* node4 = CreateBTNode(4);
//	BTNode* node5 = CreateBTNode(5);
//	BTNode* node6 = CreateBTNode(6);
//	//将结点连接起来，构成自己想要的树
//	node1->left = node2;
//	node1->right = node4;
//	node2->left = node3;
//	node4->left = node5;
//	node4->right = node6;
//	//返回根结点
//	return node1;
//}
int main()
{
	BTNode* tree = CreateBinaryNode();
	return 0;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。

2.二叉树的遍历

• 还是以这颗二叉树为例，后续的遍历均是建立在次二叉树基础上展开。

2.1.前序遍历

遍历顺序：根 -> 左子树 -> 右子树

思路
既然先从根走，根是1，接下来访问1的左子树，此时又要先访问其左子树的根为2，接着再访问2的左子树，2的左子树的根为3，接着访问其左子树和右子树，不过均为空，递归返回，此时3作为2的左子树访问完毕，访问2的右子树为NULL，再递归返回。此时1的左子树就访问完毕了，访问其右子树，同理访问左子树4，再访问左子树5，接着访问5的左右子树，均为NULL，递归返回，访问4的右子树6，接着访问5的左右子树，均为NULL，递归返回，此时4的左右子树均访问完毕，再递归返回，此时1的右子树也访问完毕了，最后递归返回。

图示：

代码:前序遍历的代码非常简洁。

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");//如果为空，就打印空
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

运行结果:

我们单纯的看代码是无法理解他是如何递归调用的，我们还是需要画递归展开图。

递归展开图：

上图是逻辑上的递归图解，可能不太好理解，我们从物理结构上画，可能易于理解。让我们通过一幅递归展开图来深刻理解其原理：

深入理解：树是二叉树的形状，他的递归调用也是二叉树的形状，递归从底层的角度，即从物理的角度在建立栈帧，栈帧里面在保存里面定义的局部变量，这里最重要的局部变量是root。建立栈帧，递归调用，递归返回，销毁栈帧。 比如，左子树递归调用完成的时候，只剩根节点1的栈帧，然后开始访问右子树，又开始建立栈帧…空间是可以重复利用的，右子树调用递归建立的栈帧，跟左子树递归建立的栈帧是重叠的，当我们递归右子树时，左子树建立的栈帧已经销毁了，递归看的是深度，二叉树的递归是双路递归，先递归左边，左边递归完了，栈帧已经销毁了，再递归右边。

2.2.中序遍历

遍历顺序：左子树 -> 根 -> 右子树

思路:
根据遍历顺序，我们得知，如若想访问根1，得先访问其左子树2，访问2还得先访问2的左子树3，再访问3的左子树为NULL，递归返回访问根结点3，再访问3的右子树NULL，递归返回访问根结点2，再访问2的右子树NULL，递归返回访问根结点1，再访问1的右子树，1的右子树访问规律同1的左子树，这里不过多赘述。

图示：

代码:中序遍历的代码也非常简洁。

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");//如果为空，就打印空
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

运行结果:

我们单纯的看代码是无法理解他是如何递归调用的，我们还是需要画递归展开图。

递归展开图：

2.3.后序遍历

遍历顺序：左子树 -> 右子树 -> 根

思路:
要访问1得先访问1的左子树2，继而得先访问2的左子树3，再先访问3的左子树NULL，右子树NULL，根3，递归返回访问2的右子树NULL，根2，再递归返回访问1的右子树……类似的，这里不过多赘述。

图示：

代码:后序的代码也非常简单，有了前文前序遍历和中序遍历的基础，后序遍历只需要把打印放后面即可。

void PosOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");//如果为空，就打印空
		return;
	}
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d ", root->data);
}

运行结果:

我们单纯的看代码是无法理解他是如何递归调用的，我们还是需要画递归展开图。

递归展开图：

2.4.层序遍历

遍历顺序：第一层 -> 第二层 - >第三层

思路:
大家可能也发现了，先前的遍历思想都是通过递归来完成的，而层序的遍历则是通过队列来实现的。

首先，把根节点1的结点指针先入队列，队列此时不为空，出队头的数据，把队头数据的孩子2的结点指针和4的结点指针入进去，队列不为空，出2，入孩子3，队列不为空，再出4，把孩子5和6入进去，然后再出，没有孩子继续出，出到最后队列为空。总结如下两句话：

1. 先把根入队列，借助队列性质：先进先出
2. 上一层的节点出的时候，带下一层的节点进去

图解：

代码：层序遍历代码较为复杂，还调用了队列的代码。

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //先把根结点入进去
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q); //入队头
		QueuePop(&q); //出队头
		printf("%d ", front->data); //打印队头数据
		if (front->left)
		{
			QueuePush(&q, front->left); //front左孩子不为空，就入队
		}
		if (front->right)
		{
			QueuePush(&q, front->right);//front右孩子不为空，就入队
		}
	}
	printf("\n");
	QueueDestory(&q);
}

运行结果:

3.二叉树函数接口的实现

3.1.二叉树的节点个数

思想：
求结点个数，这里我将提供如下几种方法，但不都是可行的，要对比着看，本质都是递归的思想：

法一：遍历
在前文中，我们已经学习了如何遍历链式二叉树，现在想求结点的个数，那么只需要随便采用一种遍历方式，并把打印换成计数++来求个数即可，听起来非常容易，实际实现过程一波三折，先看代码：

//节点个数
void BinaryTreeSize(BTNode* root)
{
	int count = 0; //局部变量
	if (root == NULL) //如果为空
		return;
	++count;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
}

上述代码能够准确求出结点个数吗？其实根本求不出来。

具体解释起来需要借用栈帧的思想，因为这里用的是递归，而递归是每递归一次在栈帧里面都会开辟一块栈帧空间，每一层栈帧都会有一个count，而我希望的是只需要有一个count，然后判断节点是否为空，如果不为空count++，但是现在每递归一次，重新开辟一个count，count即局部变量。递归完就销毁，和形参的改变不会影响实参一个道理。所以这种方法不行。

法二：定义局部静态变量count
在法一中，我们定义的是局部变量count，会导致每递归一次就开辟栈帧，并创建count，每次递归结束返回就销毁栈帧。那如果我们把count放在静态区里面，那count不就不会销毁了吗？代码如下：

//节点个数
int BinaryTreeSize(BTNode* root)
{
	static int count = 0; //局部静态变量
	if (root == NULL) //如果为空
		return count;
	++count;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
	return count;
}

运行结果如下：

看似好像是成功了，确实结点个数为6，但真的就是成功了吗？当然不是，如果我们现在想多打印几次呢？

发生什么事了？怎么size还呈现等差数列递增呢？就是因为这里运用了static关键字，将count存在静态区，导致多次调用没办法初始化为0，使其每次递归调用累计加加，但是当你再重新调用自己时，count不会重新置为0，会依旧保留为曾经++的结果。局部的静态变量有一个好处，它的生命周期在全局，但是它的作用域在局部。它的初始化为0只有第一次调用会执行，其余均不会。由此可见，局部的静态也是不行的，还得再优化。

法三：定义全局变量count
法二的局部静态变量行不通，那就把count设定为全局变量。要知道全局变量是存在静态区的。虽然也在静态区，但是其初始化为0是可以重复执行的。这样就解决了上述只初始化一次的问题。这里每次调用前，仍然要初始化count=0，不然还是会出现上面的问题。因为静态变量的生命周期虽然在全局，但是它只能在局部去访问，所以不能初始化。

//节点个数
int count = 0;
void BinaryTreeSize(BTNode* root)
{
	if (root == NULL) //如果为空
		return;
	++count;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
}

运行结果如下：

确实可以求出结点个数，并且也不会出现像法二一样的问题。但是其实定义全局变量也会存在一个小问题：线程安全的问题，这个等以后学到Linux再来讨论，我们还要继续优化。

法四：最优解
我们这里可以考虑多套一层，可以考虑把变量的地址传过去。这样操作不会存在任何问题，代码如下：

//节点个数
int count = 0;
void BinaryTreeSize(BTNode* root, int* pCount)
{
	if (root == NULL) //如果为空
		return;
	++(*pCount);
	BinaryTreeSize(root->left, pCount);
	BinaryTreeSize(root->right, pCount);
}

法五：巧妙的思路
直接利用子问题的思想来写，返回当root为空为0，不是就递归左树+右树+1。

空树，最小规模子问题，结点个数返回0
非空，左子树结点个数+右子树结点个数 + 1（自己）

//子问题思路解决
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
    BinaryTreeSize(root->left) + 
    BinaryTreeSize(root->right) + 1;
}

运行结果：

此法非常巧妙，堪称完美，很灵活的运用了递归的思想，我们通过递归图来深刻理解下：

递归展开图：

注意：BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1中的1放在前面后面没有影响，表达式需要算出值才能相加返回。

总结：
上述算法思想其实就是分治思想，类似于我们说的大事化小，小事化了。

把复杂的问题分成更小规模的子问题，子问题再分成更小规模的子问题……直到子问题不可再分割，就能得到结果。

其实就是在套娃，接下来的多个问题都将会用到分治思想。

3.2.二叉树叶节点个数

法一：遍历+计数

在遍历的基础上如果结点的左右子树均为空则count++。但是此题我们依旧采用分治思想。

法二：分治思想

首先，如果为空，直接返回0，如若结点的左子树和右子树均为空，则为叶节点，此时返回1，其它的继续分治递归。

代码如下：

//叶结点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0; //为空，返回0
	if (root->left == NULL && root->right == NULL)
		return 1; //如果左右子树均为空，则为叶结点，返回1
	return TreeLeafSize(root->left) + TreeLeafSize(root->right); //继续分治递归
}

递归展开图：

3.3.二叉树的深度

此题同样是运用分治的思想来解决，要比较左子树的高度和右子树的高度，哪个子树高就加1，因为还有根结点，也是1个高度。

int TreeHeight(BTNode* root)
{
    if(root == NULL)
    	return 0;
   	int leftHight = TreeHight(root->left);
   	int rightHight = TreeHight(root->right);
    return (leftHight > rightHight ? leftHight:rightHight) + 1;
}

递归展开图：

3.4.二叉树第K层节点个数

这里我们还是可以用分治的思想，我们要求二叉树第K层节点个数，我们可以求二叉树的左右子树的K-1层

分成三步，根据不同的情况进行处理，

1. 空树，返回0
2. 非空，且K == 1，返回1
3. 非空，且K>1，转换成左子树K-1层节点个数 + 右子树K-1层节点个数

int TreeKLevelSize(BTNode* root, int k)
{
	//第K层节点个数,K>0
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKLevelSize(root->left, k - 1) + 
        TreeKLevelSize(root->right, k - 1);
}

递归展开图：

3.5.二叉树查找值为X的节点

1. 先去根结点寻找，是就返回根节点
2. 此时去左子树查找有无节点x
3. 最后再去右子数去查找有无节点x
4. 若左右子树均找不到节点x，直接返回空

//二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	//如果根节点为空，直接返回空
	if (root == NULL)
		return NULL;
	//如果找到节点，直接返回节点位置
	if (root->data == x)
		return root;
	//若没找到，去左子树找
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;
	//此时左子树没找到，去右子树找
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;
	//若左子树和右子树都每找到，直接返回空
	return NULL;
}

递归展开图：

3.6.二叉树的销毁

我要把二叉树销毁，需要销毁二叉树所有的节点，我们遍历一个节点就销毁一个节点，你以为这就完了？但是又会存在一个问题，那就是你要采用什么样的遍历方式？倘若你采用前序遍历，刚开始就把根销毁了，那么后面的子树还怎么销毁呢？因为此时根没了，子树就找不到了。那中序遍历可不可以呢？也不可以，中序遍历是先访问左子树，再访问根，最后访问右子树。但是你销毁了根，右子树就访问不了了。所以要采用先销毁子树再销毁根的方法，也就是后序遍历的思想。

//二叉树的销毁
void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
	root = NULL;
}

因为已经画过后序遍历的递归展开图，而二叉树的销毁思想和二叉树的后序遍历思想差不多，所以这里就不画了，画的也累了😪

3.7.判断二叉树是否为完全二叉树

在做提前，再来回顾下完全二叉树的概念：前k-1层是满的，最后一层是连续的。

来看一幅图：

在这三幅图中，很明显肉眼得知第二幅和第三幅图是完全二叉树，只有第一幅不是，现在如何用代码的方式表明出来呢？

思路：层序遍历+变形
通过上图，不难发现，如果是完全二叉树的话，在层序遍历的时候是不会出现间隔的NULL。例如第一幅图就不是完全二叉树，因为层序遍历到第三层的时候会出现间隔NULL，因为3 -> NULL -> 5 -> 6，而剩余两幅图均不会出现这样的问题，接下来，我将利用类似的思想解决这道题。

层序遍历明确指出，当其中一个结点删除（pop）出来时，要把它的孩子给push进队列里，但前提是把不为空的孩子给push进去，现在规矩变了，不管你是否为空，都给push进去，也就是说出一个结点，push两个孩子结点，使其停止的条件是当我pop出来的结点为NULL时，此时停止push，一直pop到队列为空，如果全是空，就是完全二叉树，如果有非空，就不是。

画图演示：

//判断一颗二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //根结点不为空，入队列
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); //删除队头数据，方便后续取队头数据
		if (front == NULL) //如果取队头为空，停止，接下来进入下一个while循环判断是否为完全二叉树
			break;
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); 
		//如果空出到非空，那么说明不是完全二叉树
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true; //全是空，此时返回true，为完全二叉树
}

四.二叉树完整代码

由于二叉树中还调用了队列，代码较多，碍于篇幅的原因，就不把代码放到这里了。这里我直接给出码云（gitee）仓库的地址，需要完整代码的同学可以在上面自取：BinaryTree · wei/test_code - 码云 - 开源中国 (gitee.com)

结语

终于结束了，这章没少画图，也是为了便于自己以及大家理解，写了一个星期了，希望各位佬给个三连！！！