数据结构初阶之基础二叉树（C语言实现）

📃博客主页： 小镇敲码人
💞热门专栏：数据结构与算法
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌏 任尔江湖满血骨，我自踏雪寻梅香。 万千浮云遮碧月，独傲天下百坚强。 男儿应有龙腾志，盖世一意转洪荒。 莫使此生无痕度，终归人间一捧黄。🍎🍎🍎
❤️ 什么？你问我答案，少年你看，下一个十年又来了 💞 💞 💞

📖 树

树是一种数据结构，和它的名字很像，树这种数据结构就像倒着的树。

🔥 树的几个基本概念

1. 节点： 像上图一样存储一些值的圆圈就叫节点。
2. 根节点：根节点是一种比较特殊的节点，它位于树的最顶部，就像树的根一样，所以叫根节点。
3. 节点的度：一个节点有几个子树，它的度就为几，如上图节点A的度为3。
4. 树的度： 一棵树中，最大的节点的度称作树的度，如上图，树的度为3.
5. 节点的层次：从根开始定义，根为第一层，以此类推。
6. 树的深度：树中节点的最大层次。如上图节点的最大层次为4。
7. 孩子节点或子节点：一个节点含有的子树的根节点称作这个节点的子节点。如上图节点A的子节点为B、C、D。
8. 双亲节点或父节点：如果一个节点含有子树，那么这个节点就可以叫做这些子树根节点的父节点，如上图B、C、D的父节点为A.
9. 兄弟节点： 具有相同父节点的节点互为兄弟节点，如上图B、C、D互为兄弟节点。
10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟节点，如上图F、G互为堂兄弟节点。
11. 节点的祖先：从根到该节点路径上的所有节点都可以成为该节点的祖先，如上图的A是所有节点的祖先。
12. 子孙：以某节点为根节点，它的子树上的所有节点都可以称作它的子孙。如除A以外的所有节点都可以叫做A的子孙。
13. 森林：由m（m > 0）棵互不相交的树组成的集合叫做森林。

🔥 树的结构设计

树的模拟实现比较复杂，我们的重点放在二叉树的模拟实现上，实际中有双亲表示法、孩子双亲表示法以及孩子兄弟表示法，我们这里简单的来了解一下，孩子兄弟表示法。

typedef int DataType;
struct Node
{
   Node* _firstchild;//保存第一个孩子节点
   Node* _pnextBrother;//保存下一个兄弟节点
   DataType _data;//节点中的数据域
}

🔥 树的应用

文件系统的目录树结构

📖 二叉树

二叉树就是每个节点至多有两个孩子的树。

从上图可以知道：

• 它的每一个节点至多有两个子节点，所以我们可以知道二叉树的最大度为2。
• 二叉树是有左右子树之分的，不能颠倒，因此二叉树是有序树（有顺序）。

🎦 两种特殊的二叉树

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

🎦 二叉树的一些基本性质

这些性质大家可以结合图来理解，主要用来应对选择题。

🎦 二叉树的两种结构

🔵 顺序存储

顺序存储就是使用数组去存储，主要适用于完全二叉树，因为如果你不是完全二叉树就会存在空间的浪费，我们来画图解释一下为什么会存在空间的浪费。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

堆是一种完全二叉树，我们在实现堆时，会使用数组存储，后序我们会重点介绍堆这种数据结构，这篇博客我们先来重点看二叉树。

🔵 链式存储

链式存储实际上就是用链表去存储节点，一个节点有三个数据域，左孩子的节点指针，右孩子的节点指针，节点的数据值。链式结构又分为二叉链和三叉链，当前我们二叉树中用的一般都是二叉链，高阶数据结构如红黑树等会用到三叉链。

🎦 链式二叉树的模拟实现

🔵 链式二叉树的结构设计

前面已经将链式二叉树的逻辑结构画出，它用代码来描述应该是这样的。

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

🔵 链式二叉树的函数方法声明

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
// 求某一个数的高度/深度
int BinaryTreeHeight(BTNode* root);

🔵 链式二叉树的函数方法模拟实现

💎 创建二叉树的两种方法

🍁 创建方法一

第一种创建二叉树的方式是通过在测试文件里面直接创建节点，然后手动的把它们的关系给链接起来。

void Test1()
{
   BTNode* Node1 = (BTNode*)malloc(sizeof(BTNode));
	Node1->_data = 1;
	Node1->_left = NULL;
	Node1->_right = NULL;
	BTNode* Node2 = (BTNode*)malloc(sizeof(BTNode));
	Node2->_data = 2;
	Node2->_left = NULL;
	Node2->_right = NULL;
	BTNode* Node3 = (BTNode*)malloc(sizeof(BTNode));
	Node3->_data = 5;
	Node3->_left = NULL;
	Node3->_right = NULL;
	BTNode* Node4 = (BTNode*)malloc(sizeof(BTNode));
	Node4->_data = 8;
	Node4->_left = NULL;
	Node4->_right = NULL;
	BTNode* Node5 = (BTNode*)malloc(sizeof(BTNode));
	Node5->_data = 5;
	Node5->_left = NULL;
	Node5->_right = NULL;
	BTNode* Node6 = (BTNode*)malloc(sizeof(BTNode));
	Node6->_data = 7;
	Node6->_left = NULL;
	Node6->_right = NULL;
	BTNode* Node7 = (BTNode*)malloc(sizeof(BTNode));
	Node7->_data = 10;
	Node7->_left = NULL;
	Node7->_right = NULL;
	Node1->_left = Node2;
	Node1->_right = Node3;
	Node2->_left = Node4;
	Node2->_right = Node5;
	Node3->_left = Node6;
	Node4->_left = Node7;
	BinaryTreeLevelOrder(Node1);//层序遍历
}

注意：以下函数都用方法一的数据来测试
上面的节点用二叉树的图来表示是这样的：

我们打印走的是层序遍历，这个要用到队列，我们稍后再说，至于为什么要用层序遍历打印，当然是为了更快的检查我们的二叉树是否构建正确，黑框是我们的打印结果，可以看到是符合预期的。

🍁 创建方法二

上面的方法显然是不太好的，因为需要我们手动去链接，如果节点的个数很庞大，10万个，也要我们手动去链接吗，这显然是不太合适的，所以接下来我们方法二就来给小伙伴们介绍一下，二叉树常见的构建方法，给你传一个数组，并告诉你这个数组是什么遍历让你来构建二叉树。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	assert((*pi) < n);
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

由于这个前序遍历的数组给我们给出了空指针，也就是每一个节点都给出来了，空指针用’#'来表示，所以这个二叉树是唯一的，另外这个数组应该是一个字符数组，我们通过递归来写就很简单了，实际上就是一个前序遍历还原的过程，过于简单，我们不做过多的阐述。如果你对递归的过程不太理解，我们下面的前、中、后序遍历会深入的去讲解。

• 注意这里如果没有给出代表空指针的’#‘，二叉树就不唯一了，我们举个例子来画图说明：
  假设此时二叉树的前序遍历是1 2 3 4 6 5 8

这里N代表空节点。

我们这里随便写都写出了两种。

注意：当我们不给出空节点时，只有中序和前序给出或者中序和后序给出，这个二叉树才确定，因为我们可以通过中序来划分左子树和右子树，然后前序或者后序得到根，这样就能确定这个二叉树了，后序我们二叉树OJ会有类似的题目，如果小伙伴不太会也请不要担心。

💎 二叉树的前序遍历

🍂 递归实现

二叉树的前序遍历就是先遍历根节点，然后再去遍历它的左子树，最后遍历它的右子树。递归实现很简单，代码看着很短，关键是我们要理解代码为什么是这样，这里我们通过画递归展开图来解释下面的程序：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
	  printf("NULL ");
	  return;
	}
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_left);
	BinaryTreeInOrder(root->_right);
}

这个函数的递归展开图大致就是这样注意我们只画了一部分，希望能帮助你理解，当你熟练之后就可以只画一个草图了，像这样：

使用方法一创建二叉树，打印结果如下：

🍂 非递归实现

递归遍历很简单，遍历完左子树后又可以返回这个左子树的根节点，然后继续遍历右子树，但是我们非递归该如何控制呢？难道要用变量去一个个保存维护吗，这太复杂了，我们很容易想到由于递归正是利用了隐式栈后入先出的特点，我们使用一个显示栈来模拟这个过程就可以了。
我们先画图来分析：

我们继续总结，简化一下我们其实在一直重复做着相同的事情：

知道了原理是什么，再去写程序就是信手拈来，C语言代码实现如下，其中手搓栈的代码请进入博主的仓库自取：

// 二叉树前序遍历非递归版本
void BinaryTreePrevOrderF(BTNode* root)
{
	Stack st1;//建立栈对象
	StackInit(&st1);//初始化栈对象

	BTNode* cur = root;
	//开始循环进行前序遍历
	while (!StackEmpty(&st1) || cur == root)
	{
		//开始遍历左子树
		while (cur != NULL)
		{
			printf("%d ", cur->_data);//先遍历打印根节点
			StackPush(&st1,cur);//将当前节点指针入栈
			cur = cur->_left;//继续遍历左树
		}

		printf("NULL ");
		//遍历完了某个根节点的左子树，cur为空跳出循环
		while (!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			cur = cur->_right;
			if (cur != NULL)//此时表明我们找到了栈里面最近一次入栈的那个右子树根节点不为空的节点
			{
				StackPop(&st1);//我们已经拿到它的右子树根节点，它已经没有用了，弹出去！
				break;
			}
			printf("NULL ");
			StackPop(&st1);//没有找到这个节点没有用了，弹出去
		}
	}
}

注意我们栈的数据类型是这个二叉树的结构体指针，这里可能是编译器的问题，不能使用这个结构体的别名，只能使用原来的那个来定义栈的数据类型，它们分属于不同的文件。

这里我们使用二叉树的创建方法一来验证一下，打印结果：

和我们的预期一致。

💎 二叉树的中序遍历

二叉树的中序遍历就是先遍历左子树，然后再遍历它的根节点，最后遍历它的右子树，对于每个节点都是同样的规则。

🍂 递归实现

递归实现和前序遍历类似，这里我们直接给出代码：

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}

打印结果：

递归遍历过程理解，这里我们不再画递归展开图，直接画出简略图：

这里我们也打印出了NULL，是为了便于大家理解。

🍂 非递归实现

非递归和前序的非递归类似，我们依旧画图来分析

这里没有具体的去画栈的数据进出分析，因为我们已经有了前序的基础，中序和前序是很相似的，改一下打印（存入数组）的顺序即可。

代码实现：文章来源地址https://www.toymoban.com/news/detail-841458.html

//二叉树中序遍历非递归版本
void BinaryTreeInOrderF(BTNode* root)
{
	Stack st1;//创建一个栈对象
	StackInit(&st1);//初始化栈对象
    
	BTNode* cur = root;//创建一个临时遍历cur用于遍历二叉树
	while (!StackEmpty(&st1) || cur != NULL)//栈不为空，或者cur不为空，我们就继续执行程序。
	{
		while (cur != NULL)
		{
			StackPush(&st1, cur);
			cur = cur->_left;
		}
		printf("NULL ");
		//某一个节点的左子树遍历完了，开始管它的右子树
		while(!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			printf("%d ", cur->_data);//这个节点的左树（可能为空）遍历完了，可以遍历根节点了
			cur = cur->_right;
			if(cur != NULL)
			{
				StackPop(&st1);//这个节点的根节点和左子树已经遍历完吗，右树的根节点我们已经保存，它已经没有用了，我们直接弹出去
				break;//出循环去遍历当前根节点的右树，同样的逻辑
			}
			StackPop(&st1);//这个节点的右树为空，同样没有用，我们也弹出去。
			printf("NULL ");
		}
	}
}

遍历结果：

符合预期。

😀 二叉树的后序遍历

二叉树的后序遍历就是先遍历左子树，然后再去遍历它的右子树，最后遍历它的根节点。

🌷 递归实现

递归实现还是一如既往的简单，关键是理解

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);//先遍历它的左子树
	BinaryTreeInOrder(root->_right);//再遍历它的右子树
	printf("%d ", root->_data);//最后打印它的根节点的值
}

打印结果：

🌷 非递归实现

这里最难的应该就是后序遍历的非递归，也不能说难吧，就是后序遍历的非递归和前面两个不太一样，前序遍历和中序遍历的非递归是比较相似的，这里我们画出具体的数据出入栈的分析图就很清晰了：

代码实现：

// 二叉树后序遍历非递归版本
void BinaryTreePostOrderF(BTNode* root)
{
	Stack st1;//定义栈对象
	StackInit(&st1);//初始化栈对象

	BTNode* cur = root;//创建临时变量用来遍历二叉树
	while (!StackEmpty(&st1) || cur != NULL)//栈不为空，或者cur不为空进入循环
	{
		while (cur != NULL)
		{
			StackPush(&st1, cur);//将左子树的根节点的左节点依次入栈，这里也要把第一个根节点入栈（因为等下要去遍历它的右子树）
			cur = cur->_left;
		}

		printf("NULL ");
		//某一个节点的左子树为空跳出循环
		BTNode* prev = NULL;//定义遍历prev用于保存上一个遍历的右子树根节点
		cur = StackTop(&st1);
		while(!StackEmpty(&st1) && (cur->_right == NULL || cur->_right == prev))//如果栈不为空，并且满足打印和pop的条件，我们就继续pop，直到不满足条件
		{
			if (cur->_right == NULL)
				printf("NULL ");
			printf("%d ", cur->_data);
			StackPop(&st1);
			prev = cur;
			if (!StackEmpty(&st1))
			{
				cur = StackTop(&st1);
			}
		}
		//程序执行到这里，只存在两种情况，1.cur的右树不为空，我们需要去遍历它的右树，2.栈为空，由于是后序，栈为空说明已经遍历完了，把cur置为空，让循环结束
		if (!StackEmpty(&st1))
			cur = cur->_right;
		else
			cur = NULL;
	}
}

运行结果：

与预期一致。

🏣 二叉树的层序遍历（非递归）

层序遍历和它的名字一样，是将二叉树一层一层的遍历，我们应该如何实现呢？

这里我们不再卖关子了（dog，层序遍历需要借助数据结构队列先进先出的特性来实现，我们画图来分析，使用队列来做的合理性：

代码实现：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;//建立队列对象
	QueueInit(&q);//初始化队列
	QueuePush(&q,root);//将根节点入队列
	while (!QueueEmpty(&q))//队列为空，层序遍历结束
	{
		BTNode* cur = QueueFront(&q);//取队头
		QueuePop(&q);//pop队头
		if (cur == NULL)//如果队头为空，直接打印空
		{
			printf("NULL ");
		}
		else//否则打印队头数据
		{
			printf("%d ", cur->_data);
		}
		if (cur != NULL)//如果队头不为空，入队头的数据
		{
			QueuePush(&q, cur->_left);
			QueuePush(&q, cur->_right);
		}
	}
}

运行结果：

符合预期。

🏣 二叉树节点的个数

我们想计算二叉树的节点的个数应该怎么去做呢？用递归的思想就很简单，当一个节点作为根时，我们想计算以它为根的这棵二叉树节点的数量，只需要求出它的左树的节点总数量和右树的节点总数量之和再加1就可以了，递归下去它的每个节点都面临相同的问题，这样我们就将一个大问题划分为了一个个相同的子问题，可以用递归来解决。

🌓 递归版本（前序遍历）

// 二叉树节点个数(递归版)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
}

运行结果：

递归解法很简单？根本没有挑战性？那不妨我们来尝试一下非递归。

🌓 非递归版本（前序遍历）

分析：

其实就是二叉树的前序遍历，只不过从打印变成了Size++，想一想，前序遍历打印的次数不就是节点的个数吗，只不过我们不打印NULL了而已，使用任何一种遍历都可以求出节点个数。

// 二叉树节点个数非递归版
int BinaryTreeSizeF(BTNode* root)
{
	Stack st1;//定义栈的临时变量
	StackInit(&st1);//初始化栈

	BTNode* cur = root;//定义临时变量cur用于遍历
	int Size = 0;
	while(!StackEmpty(&st1) || cur != NULL)
	{
		while (cur != NULL)
		{
			Size++;//根节点的位置Size++
			StackPush(&st1,cur);//节点指针入栈
			cur = cur->_left;//以当前节点为根节点，遍历它的左子树
		}

		//有一个节点的左子树走完了
		while (!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			cur = cur->_right;
			StackPop(&st1);
			if (cur != NULL)//有节点的右子树不为空，我们跳出出栈循环，去遍历它的右子树
			{
				break;
			}
		}
	}
	return Size;
}

运行结果:

🐹 二叉树叶子节点个数

此函数用来求叶子节点的个数我们的思路也很简单，走一个前序遍历，二叉树的叶子节点的个数 = 左子树叶子节点的个数，和右子树叶子节点的个数之和。

🌏 递归版本

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) 
{
	if (root == NULL)//如果当前节点为空，我们返回0
		return 0;
	if (root->_left == NULL && root->_right == NULL)//如果当前节点是叶子节点我们直接返回1
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

实际我们要处理的就这两种情况：

运行结果：

🌏 非递归版本

非递归主要走的还是前序的非递归，在一些细节的地方处理即可。

我们仍然使用Size来记录叶子节点的个数，当一个节点的左孩子为空且右孩子也为空，我们保证右孩子为空很简单，关键是如何保证左孩子为空，注意：只有循环刚结束的栈顶节点的左孩子才会空，其它的都有左孩子，你细思（dog。

代码实现：

// 二叉树叶子节点个数非递归版
int BinaryTreeLeafSizeF(BTNode* root)
{
	Stack st1;//定义栈的临时变量
	StackInit(&st1);//初始化栈

	BTNode* cur = root;//定义临时变量cur用于遍历
	int Size = 0;
	while (!StackEmpty(&st1) || cur != NULL)
	{
		while (cur != NULL)
		{
			StackPush(&st1, cur);//节点指针入栈
			cur = cur->_left;//以当前节点为根节点，遍历它的左子树
		}

		//叶子节点只会在刚出循环的栈顶元素中出现
		cur = StackTop(&st1);
		if (cur->_right == NULL)//为空，叶子节点个数++，不为空继续遍历它的右子树
		{
			Size++;
			StackPop(&st1);
			//找到下一个右子树不为空的节点
			while (!StackEmpty(&st1))
			{
				cur = StackTop(&st1);
				cur = cur->_right;
				StackPop(&st1);
				if (cur != NULL)//有节点的右子树不为空，我们跳出出栈循环，去遍历它的右子树
				{
					break;
				}
			}
		}

	}
	return Size;
}

运行结果：

🍎 二叉树第k层节点个数（假设二叉树从第一层开始）

求第K层节点的个数也很简单，递归的思想基本和前面的没什么区别，二叉树第k层节点的个数 = 根节点左子树第k层节点的个数+根节点右子树第k层节点的个数。

🌴 递归版本

代码实现：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);//我们规定二叉树层数从1开始，如果k小于1就要报错，说明传错了。
	if (root == NULL)//如果此时root为空还没返回说明找不到了，直接返回0
		return 0;
	if (k == 1)//找到了，返回1
		return 1;
	return BinaryTreeLevelKSize(root->_left,k-1) + BinaryTreeLevelKSize(root->_right,k-1);//根节点的第K层，相对于它的子树来说就是k-1层
}

运行结果：

🌴 非递归版本

🚗 使用栈实现

代码实现：

// 二叉树第k层节点个数非递归使用栈实现
int BinaryTreeLevelKSizeFS(BTNode* root, int k)
{
	Stack st1;//创建队列
	StackInit(&st1);//初始化队列

	BTNode* cur = root;//定义临时变量cur来遍历二叉树
	int k1 = 1;
	int Size = 0;
	while (!StackEmpty(&st1) || cur != NULL)
	{
		while (cur != NULL)
		{
			if (k1 >= k)//满足情况，我们break,同时Size++
			{
				Size++;
				cur = NULL;//把cur置为空，如果后面还存在右子树满足，cur就会被更新，否则就退出循环
				break;
			}
			else//还没有满足层数的要求，我们存入节点指针和层数，继续遍历
			{
				//统一先存值，再存节点
				StackPush(&st1, k1);
				StackPush(&st1, cur);
				k1++;
			}
			cur = cur->_left;//没有满足情况继续遍历
		}
		//找节点右子树不为空的那个节点
		while (!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			StackPop(&st1);//pop节点指针
			if (cur->_right != NULL)//找到了
			{
				cur = cur->_right;
				k1 = StackTop(&st1)+1;
				StackPop(&st1);//pop这个节点对应的层数
				break;
			}
			cur = NULL;//如果没找到，程序就应该结束，cur应该被置空
			StackPop(&st1);//pop对应的层数
		}

	}
	return Size;
}

细节有很多，比如对cur的置空处理就很关键，我们举几个例子来探讨以下为什么要这样做：

运行结果：

🚗 使用队列实现

刚刚这种方法在逻辑上理解可能有点困难，我们使用队列会更容易理解：

代码实现：

// 二叉树第k层节点个数非递归使用队列实现
int BinaryTreeLevelKSizeFQ(BTNode* root, int k)
{
	assert(k > 0);//层数必须合法

	Queue q1;//创建队列变量
	QueueInit(&q1);//初始化队列变量

	QueuePush(&q1, root);//先将根节点入队列
	BTNode* cur = NULL;//创建临时变量用于辅助完成队列的入队操作

	while (!QueueEmpty(&q1))
	{
		int Size = QueueSize(&q1);//某一层的节点个数
		if (k == 1)
			return Size;
		while (Size--)
		{
			cur = QueueFront(&q1);
			QueuePop(&q1);
			if (cur->_left)
				QueuePush(&q1,cur->_left);
			if (cur->_right)
				QueuePush(&q1, cur->_right);
		}
		k--;
	}
	return 0;//没有这层
}

运行结果：

❤️ 二叉树查找值为x的节点

注：这里我们默认不会存相同的值。

递归思想：先去左树找，如果左树不能找到，再去右树找。

代码实现：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->_left, x);
	if (left == NULL)
		return BinaryTreeFind(root->_right, x);
	else
		return left;
}

假设此时我们找节点值为10的节点，运行结果为：

❤️ 求某一个树的高度/深度

求一个树的高度/深度，假设从1开始，递归思路也很简单，一个树的深度 = 它左右子树的最大深度+1。

代码实现：

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHight = BinaryTreeHeight(root->_left) + 1;//保存左树的最大深度+1
	int rightHight = BinaryTreeHeight(root->_right) + 1;//右树的最大深度+1
	return leftHight > rightHight ? leftHight : rightHight;//返回最大值
}

运行结果：

非递归我们不再给出，使用层序遍历或者前中后序均可，有兴趣的小伙伴可自行尝试。

❤️ 判断二叉树是否是完全二叉树

上面我们已经谈到，完全二叉树是基于满二叉树的概念引申出来的，我们简单点来说：完全二叉树就是对应深度的满二叉树按照顺序减少一些节点，比如下面的图：

那我们应该如何判断一棵树是否是完全二叉树呢？我们可以借助二叉树的层序遍历去完成这个判断，并且我们需要存入NULL，因为层序遍历都是一层一层按照顺序来遍历的，当NULL后面都没有为非空的节点时表面这个树是完全二叉树，否则就不是。空树不是完全二叉树。

代码实现：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	assert(root);//如果为空不需要判断直接强制报错。

	Queue q;
	QueueInit(&q);//初始化队列
	QueuePush(&q, root);//先存入根节点
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)//找到空节点，退出循环
			break;
		QueuePush(&q, cur->_left);
		QueuePush(&q, cur->_right);
	}
    
	while (!QueueEmpty(&q))//继续遍历，如果能找到非空节点，则这个树一定不是完全二叉树返回false
	{
		BTNode* cur1 = QueueFront(&q);
		QueuePop(&q);
		if (cur1 != NULL)
			return false;
	}
	return true;//是完全二叉树，返回true
}

运行结果：

❤️ 二叉树销毁

二叉树的销毁就是我们手动释放空间的过程，因为有些节点是在堆上申请的，需要我们自己去释放，走一个后序遍历就可以完成，注意不能走前序或者中序，因为前序和中序都是根在右树前面就释放了，我们后面就找不到右树了（非法访问的问题）。

代码实现：

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)//传二级指针，是为了让其不用在外面置空
{
	if (*root == NULL)//如果已经为空，返回
		return;
	BinaryTreeDestory(&(*root)->_left);//先去释放左树
	BinaryTreeDestory(&(*root)->_right);//再释放右树节点
	free(*root);//最后释放根节点
	*root = NULL;//注意不要忘记置空
}

到了这里，关于数据结构初阶之基础二叉树（C语言实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！