初阶数据结构：树---二叉树的链式结构

一、二叉树的链式结构

（一）、概念

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

（一）、二叉树链式结构的遍历

1、前序遍历

2、中序遍历

3、后序遍历

4、层序遍历

（二）、二叉树的构建

（三）、二叉树的销毁

（四）、二叉树节点个数

（五）、二叉树叶子节点的个数

（六）、二叉树第K层节点个数

（七）、二叉树查找值为X的节点

三、DFS（深度优先遍历）和BFS（广度优先遍历）

在计算机科学的广袤领域中，数据结构犹如基石，支撑着无数复杂系统与高效算法的构建。而二叉树链式结构，作为数据结构家族中的重要成员，以其独特的组织方式和强大的功能，在诸多领域发挥着不可或缺的作用。无论是数据库索引的优化，还是编译器中语法树的构建；无论是文件系统的目录管理，还是人工智能中决策树的实现，都能看到二叉树链式结构活跃的身影。它不仅为数据的存储与检索提供了高效的解决方案，还为算法的设计与优化开辟了新的思路。本次博客本文将深入探索二叉树链式结构的奥秘，领略其独特魅力与无限潜力。

一、二叉树的链式结构

（一）、概念

我们知道二叉树是度不超过2，有左右子树之分的有序树。我们通过上篇博客了解到二叉树的顺序结构，也就是堆。那么二叉树的链式结构又是什么呢？

二叉树链式结构是一种用链表来表示二叉树的数据结构。在这种结构中，每个节点包含三个部分：数据域（用于存储节点的数据）、左子节点指针（指向该节点的左子节点）和右子节点指针（指向该节点的右子节点）。当左子节点或右子节点不存在时，对应的指针为空（通常用NULL表示）。

如果说二叉树顺序存储的逻辑结构和物理结构是不一样的，那么二叉树链式存储就可以形象的表现二叉树。

因此，对于二叉树的链式存储其节点结构如下：

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;//数据域
	struct BinaryTreeNode* _left;//左子节点
	struct BinaryTreeNode* _right;//右子节点
}BTNode;

ps:上述代码中对char类型进行重命名是为了方便存储其他类型数据。

为了更直观地理解，我们来看一个简单的例子：假设有一棵包含以下节点的二叉树，根节点为 A，A 的左子节点是 B，右子节点是 C；B 的左子节点是 D，右子节点是 E；C 的左子节点是 F，右子节点是 G。其链式结构可以用下图表示：

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

二叉树链式结构的实现有很大的学习意义，深入了解二叉树链式结构的实现对于我们后续思考问题有很大帮助。

在我们深入了解二叉树链式结构的实现前，我们需要一个链式二叉树来帮助我们更好的理解。因此开始我们的手动建树。代码如下：

BTNode* BuyBinaryNode(char x)
{
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	Node->_data = x;
	Node->_left = Node->_right = NULL;
	return Node;
}

先写一个申请节点函数，直接通过malloc函数申请节点，再将新节点的左右孩子指针置空，防止野指针问题出现。然后我们再手动拼接节点，让它们构成一个上图所示的节点。代码如下：

int main()
{
	BTNode* nodeA = BuyBinaryNode('A');
	BTNode* nodeB = BuyBinaryNode('B');
	BTNode* nodeC = BuyBinaryNode('C');
	BTNode* nodeD = BuyBinaryNode('D');
	BTNode* nodeE = BuyBinaryNode('E');
	BTNode* nodeF = BuyBinaryNode('F');
	BTNode* nodeG = BuyBinaryNode('G');
	nodeA->_left = nodeB;
	nodeA->_right = nodeC;
	nodeB->_left = nodeD;
	nodeB->_right = nodeE;
	nodeC->_left = nodeF;
	nodeC->_right = nodeG;
	return 0;
}

接下来，让我们用这个手动建的二叉树去深入理解本次的重点---二叉树链式结构的遍历。

（一）、二叉树链式结构的遍历

看到这，或许你会感到奇怪，区区一个遍历，如何当的了如此大任。NO，NO，NO。它还真的能够担任。如果你能够将二叉树链式结构的遍历学的十分深入，那么二叉树链式结构对你来说就没有什么难度了。让我们来看看二叉树链式结构的遍历吧。

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

二叉树的遍历方式有四种，分别是：

1、前序遍历（也被称为前根遍历、先根遍历）

2、中序遍历

3、后序遍历

4、层序遍历

我们该如何理解这些遍历呢？

我们需将二叉树看成根，左子树，右子树三部分组成。对于左子树和右子树也需看成根、左子树、右子树三部分组成，一直到没有左右子树为止。

1、前序遍历就是先遍历根，然后是左子树，最后是右子树。

2、中序遍历就是先遍历左子树，然后是根，最后是右子树。

3、后序遍历就是先左子树，然后右子树，最后才是根。

4、层序遍历也就是以此一层从左到右遍历。

ps:记忆上述遍历，对于前、中、后序遍历可以看作根的位置在前、中、还是后，而对于层序遍历就比较容易记忆。

1、前序遍历

对于二叉树链式结构的遍历，基于其独特的结构也即（递归式结构），我们需采用递归的形式来实现二叉树的前序遍历。

我们先来看一个问题：求第n项的斐波那契数？

想要解决这个问题有很多种方法，在这些方法中有一种叫：利用递归求斐波那契数。代码如下：

int css(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	return css(n - 1) + css(n - 2);
}

当我们将其递归展开图画出来，就可以看到这恰好就是一个二叉树：

那我们可不可以参考这样的方式来实现二叉树的前序遍历呢？

当然可以。我们如果使用递归来实现遍历，那么递归返回条件是什么呢？

还记得在上一篇博客中一定不要忘记树的叶节点是有左右孩子指针的，虽然它们的左右孩子指针都为空，但这不就是我们的递归返回条件吗？当二叉树递归，一直递到为空然后开始返回。

我们知道二叉树的前序遍历是先根后左最后右孩子的。那么按照这个顺序，我们可以写出如下代码：

void BinaryTreePreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePreOrder(root->_left);
	BinaryTreePreOrder(root->_right);
}

是不是感到很惊讶，通过递归调用 BinaryTreePreOrder 函数分别遍历左子树和右子树。这样就按照 “根左右” 的顺序完成了对整个二叉树的前序遍历。我们先通过递归展开图来使我们能够更为理解为什么这样就可以实现二叉树的前序遍历。

从图中可以看到，递归顺序是先一直沿着二叉树的左孩子，直到左孩子为空，返回后再递归返回路上的右孩子的，因此通过上述代码的顺序就可以完成二叉树的前序遍历。

上述代码之所以要在为NULL，返回时打印NULL，是为了更方便理解。代码结果如下：

前序遍历的顺序不是先根然后左孩子，最后右孩子吗？

由上图来解释，就是先打印A，然后递归一直沿着左孩子走，并打印一路上的子树的根。直到左孩子为空，然后返回。此时处于D节点，然后往右孩子递归，为空，返回，返回。此时递归深度处在B节点，同样往B节点的右孩子递归，然后打印E，再往E节点的左孩子递归。为空返回，然后往E节点的右孩子递归。为空，返回，返回，一直返回到A节点，再往A节点的右孩子递归。待A节点的右子树递归结束，整个二叉树的递归也就结束了。

通过二叉树的前序遍历，我们能不能想到，既然二叉树的前序遍历是这样的，那么中序遍历和后序遍历是不是也能如此来实现？

当然可以。我们只需按照二叉树遍历的顺序来改变代码顺序即可达到二叉树的中序遍历和后序遍历。

2、中序遍历

代码如下：

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

在这个实现中，同样先判断根节点是否为空，若为空则返回。接着先递归遍历左子树，当左子树遍历完成后，打印根节点的数据，最后再递归遍历右子树。对于二叉搜索树（BST），中序遍历的结果是一个有序序列，这是中序遍历在二叉搜索树中的一个重要应用。例如，对于一个存储整数的二叉搜索树，中序遍历可以得到从小到大排列的整数序列。

3、后序遍历

代码如下：

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

在这段代码中，首先判断根节点是否为空，若为空则返回。然后依次递归遍历左子树和右子树，当左右子树都遍历完后，才打印根节点的数据。后序遍历在一些场景中非常有用，比如在删除二叉树的节点时，需要先删除子节点，再删除父节点，这时后序遍历就可以派上用场。

前序遍历、中序遍历和后序遍历效果如下：

那为什么可以通过改变代码顺序来达到不同遍历效果呢？

因为二叉树递归的顺序不论是前序遍历还是中序遍历，或者是后续遍历，都是一样的，改变的只是访问当前节点值的时间而已。前序遍历是最开始就访问节点的值，中序遍历是在递归左孩子到空返回后才访问节点的值，而后序遍历就是左右孩子都递归后才访问节点的值。这里的左右孩子是指子树的左右孩子，而不是只指整个二叉树的根。

同时，当我们了解了二叉树的前中后序遍历还需去了解它们的规律，毕竟有一些考试的题目会让你根据上述两种遍历结果求第三种遍历结果。

但在一般情况下，仅通过前序遍历和后序遍历不能唯一确定一棵二叉树，也就无法唯一确定其中序遍历序列，在某些特殊情况下可以：

一般情况无法唯一确定

原理分析

前序遍历的顺序是根节点 -> 左子树 -> 右子树，后序遍历的顺序是左子树 -> 右子树 -> 根节点。虽然前序遍历的第一个元素和后序遍历的最后一个元素都是根节点，但对于左右子树节点的划分，仅依靠前序和后序遍历无法明确区分。

例如，对于前序遍历序列 [1, 2, 3] 和后序遍历序列 [2, 3, 1]，存在两种可能的二叉树结构：

一种是根节点为 1，左子节点为 2，右子节点为 3。
另一种是根节点为 1，2 是 1 的左子节点，3 是 2 的左子节点。

这两种不同的二叉树结构，中序遍历结果是不同的，第一种的中序遍历是 [2, 1, 3]，第二种的中序遍历是 [3, 2, 1]。

特殊情况可以确定

满二叉树或每个非叶子节点都有两个子节点的二叉树

对于满二叉树（每个节点要么有两个子节点，要么是叶子节点）或者每个非叶子节点都有两个子节点的二叉树，是可以通过前序遍历和后序遍历确定中序遍历的。

如：已知某二叉树的前序遍历为ABDECFG，中序遍历为DBEAFCG，求后序遍历？

我们该怎么求呢？

如果是前序遍历，那么第一个一定为二叉树的根节点的值，同时二叉树的根节点的值右边是先全为左子树左孩子的值，然后是左子树右孩子的值，再是右子树左孩子的值，最后是右子树右孩子的值。

中序遍历序列的第一个元素是二叉树最左侧的叶子节点（即从根节点一直沿着左子树指针走到最底层的节点）。

当已知根节点时，在中序遍历序列中，根节点将序列划分为两部分，左边是左子树的中序遍历结果，右边是右子树的中序遍历结果。

如果是后序遍历，那么最后一个一定为二叉树根节点的值，最后一个的前一个值一定为右子树第一个节点值，也即二叉树根节点的右孩子，并按照左孩子->右孩子->根的顺序，同时右子树也是如此。如果后序遍历知道左右子树节点个数，那么在后序遍历结果中最后一个左子树的节点值一定为左子树第一个节点值，也即二叉树根节点的左孩子。

故上题二叉树的根节点值为A，我们只看前序遍历无法确定左子树是否有节点存在，故我们还需看中序遍历，我们通过中序遍历可得，这个二叉树的左右子树都存在，且左子树有3个节点，右子树右3个节点（不计根节点）。那么可知D为左子树最后一个左孩子的值，B为左子树第一个左孩子的值。因为中序遍历中D的右边第一个为B，可知D的父节点为B，根据上述可得E为左子树第一个左孩子的右孩子的值。再对右子树进行分析，还原出二叉树来，最后通过二叉树得到后序遍历：DEBFGCA。这个题的二叉树如下：

我们再来通过一道题来检验一下：

已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（）

根节点值为5，左子树有两个节点右子树右4个节点。先分析左子树，4为左子树最后一个左孩子的值，通过中序遍历可知7可能为左子树右孩子的值，但结合前序遍历可知7为左子树第一个左孩子的值。由此，左子树分析完毕。

已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（）我们先把题目放过了，好分析。

现在开始分析右子树，9、6、2、1是右子树的节点值，通过中序遍历可知6为右子树最后一个左节点的值，那么9有可能为其父节点的值，也有可能为其右孩子的值，再通过前序遍历，可得9为右子树第一个节点的值，也即根节点的右孩子的值，前序遍历9后面就是6，说明6为9的左孩子，通过中序遍历可得1为9的右孩子，那么再结合前序遍历2和1的位置可得1是2的右孩子。

那么其后续遍历就是4761295.答案也正是如此。

那如果是通过中后序遍历求前序遍历也能这样得到吗？

当然可以，看题：

已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（）

由后序遍历可得A为二叉树根节点值，且J为左子树最后一个左孩子的值。然后结合中序遍历可得，这个二叉树左子树有6个节点，右子树也有6个节点。先分析左子树，因为后序遍历是按照左右根的顺序，中序遍历是按照左根右的顺序，但中序遍历和后序遍历都为JG，那么G为J的父节点。那么D可能为G的右孩子，但通过后序遍历来看又不对，中序遍历和后序遍历的DHK是相反的。那么D就为G的父节点才符合，再通过后序遍历可得B为根节点的左孩子，C为根节点的右孩子，由此就分析出了左子树。

已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（）

再来分析右子树，C为根节点右孩子，那么L可能为右子树最后一个左孩子的值，同时通过中序遍历可知F为C的右孩子，由后序遍历LMI我们可以假设LM为I的左右孩子，而在中序遍历中也符合，故假设成立，那E是谁的值呢？通过后序遍历可知，E可能为C的左孩子，而在中序遍历中也符合，

由此右子树也分析出来了。

由此，该二叉树的前序遍历为：ABDGJHKCEILMF.答案也是如此。

ps：一定不要死记硬背，要去理解和观察，只有真正掌握了前中后序遍历的规律，才能不晕头转向。

4、层序遍历

层序遍历是按照二叉树的层次，从根节点开始，逐层从左到右访问节点。对于上述二叉树，层序遍历的结果是：A B C D E F G 。

层序遍历通常使用队列来实现。其原理是：首先将根节点入队，然后从队列中取出一个节点，访问该节点的数据，接着将该节点的左子节点和右子节点（如果存在）依次入队，重复这个过程，直到队列变为空。此时，所有节点都已被访问，完成了层序遍历。

我们可以直接借用之前队列的代码来实现层序遍历。

typedef struct QueueNode
{
	BTNode* data;
	struct QueueNode* next;
}Qnode;
typedef struct Queue
{
	//头指针
	Qnode* head;
	//尾指针
	Qnode* tail;
	//计数存储数据个数
	int size;
}Queue;
void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
}

void QueuePush(Queue* q,BTNode* x)
{
	assert(q);
	//申请新节点
	Qnode* ptr = (Qnode*)malloc(sizeof(Qnode));
	if (ptr == NULL)
	{
		perror("QueuePush::malloc");
		return;
	}
	ptr->data = x;
	//提前将新节点next指针置空
	ptr->next = NULL;
	//判断队列是否为空
	if (q->head == NULL && q->tail == NULL)
	{
		q->head = q->tail = ptr;
	}
	else
	{
		q->tail->next = ptr;
		q->tail = ptr;
	}
	q->size++;
}

void QueuePop(Queue* q)
{
	assert(q);
	//判断头指针是否为空，为空那还出什么队列
	assert(q->head);
	//先存储头指针指向的节点的下一个节点的位置
	Qnode* headnext = q->head->next;
	//释放头指针指向的节点空间
	free(q->head);
	//再让头指针指向之前存储的节点
	q->head = headnext;
	//如果队列中只有一个节点，那释放空间后，头指针是空，但
	//尾指针没有被置为空，而是处于野指针状态，因此也要将
	//尾指针置空
	if (q->head == NULL)
	{
		q->tail = NULL;
	}
	q->size--;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size;
}

void QueueDestroy(Queue* q)
{
	assert(q);
	Qnode* ptr = q->head;
	if (q->head == NULL)
	{
		return;
	}
	while (ptr)
	{
		Qnode* ptrnext = ptr->next;
		free(ptr);
		ptr = ptrnext;
	}
	q->head = q->tail = NULL;
	printf("队列销毁成功\n");
	q->size = 0;
}
BTNode* QueueFront(Queue* q)
{
	assert(q);
	if (q->head == NULL)
	{
		return NULL;
	}
	return q->head->data;
}

看完队列的代码，你是不是会感到奇怪，动图上不是节点值进队列和出队列吗？怎么代码节点中却是BTNode* data。如果是节点值进队列，那么出队列时，进它的左右孩子，待出队列时无法通过左右孩子进它们的左右孩子。如果进队列的是节点地址，那么这个问题可以完美解决。层序遍历代码如下:

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (QueueEmpty(&q))
	{
		BTNode* foot = QueueFront(&q);
		printf("%c ", foot->_data);
		QueuePop(&q);
		if (foot->_left)
		{
			QueuePush(&q, foot->_left);
		}
		if (foot->_right)
		{
			QueuePush(&q, foot->_right);
		}	
	}
}

层序遍历结果如下：

了解了层序遍历后，我们来看一个问题：如何判断二叉树是完全二叉树？

完全二叉树的概念是：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

那么根据这个概念，我们可以通过层序遍历来解决这个问题。也即我们不止让有值节点入队列，我们让空也入队列，这样经过层序遍历后，最后一个数字都为空则为完全二叉树。

（二）、二叉树的构建

我们建链式二叉树除了手动建树外还有一种就是通过二叉树的前序遍历结果构建二叉树。也就是二叉树前序遍历的还原。大家可以先做一下题。

二叉树的构建

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树？

我们如何实现呢？前序遍历的顺序是根节点 -> 左子树 -> 右子树。前序遍历的数组其中 # 表示空节点。我们可以利用递归的方法，根据前序遍历的特性来构建二叉树。代码如下：

BTNode* _BinaryTreeCreate(int* i,BTDataType* a,int n)
{
	if (a[*i] == '#')
	{
		(*i)++;
		return NULL;
	}
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		return NULL;
	}
	Node->_data = a[(*i)++];
	Node->_left = _BinaryTreeCreate(i, a,n);
	Node->_right = _BinaryTreeCreate(i, a,n);
	return Node;
}
BTNode* BinaryTreeCreate(BTDataType* a, int n)
{
	int i = 0;
	return _BinaryTreeCreate(&i, a,n);
}

检查空节点：首先检查当前索引 *i 指向的元素是否为 #。如果是，则表示当前节点为空，将索引 *i 加 1，并返回 NULL。
分配节点内存：如果当前元素不是 #，则使用 malloc 函数为新节点分配内存。如果内存分配失败（即 Node == NULL），则返回 NULL。
赋值节点数据：将当前索引 *i 指向的元素赋值给新节点的 _data 成员，并将索引 *i 加 1。
递归构建左子树：调用 RestorePreOrder 函数递归地构建当前节点的左子树，并将返回的左子树的根节点指针赋值给 Node->_left。
递归构建右子树：调用 RestorePreOrder 函数递归地构建当前节点的右子树，并将返回的右子树的根节点指针赋值给 Node->_right。
返回节点指针：最后返回当前构建的子树的根节点指针。

这样就可以通过二叉树的前序遍历创建二叉树了，我们可以将其再用前序遍历打印一遍以确定是否正确。结果如下：

（三）、二叉树的销毁

当我们不再需要二叉树时，需要将其销毁，释放占用的内存空间，以避免内存泄漏。销毁二叉树的过程通常使用递归的方式进行。因为二叉树的节点是通过链表连接的，直接删除根节点会导致无法访问其左右子树的节点，所以需要从叶子节点开始逐步释放内存。也即我们需要使用递归的方式，先递归到叶子节点，如何从叶子节点开始逐步销毁节点。代码如下：

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
	*root = NULL;
}

ps：使用二级指针才能改变实参。

（四）、二叉树节点个数

我们该如何求二叉树的节点个数呢，最容易理解的一种方法就是每访问一个节点就计数一次，当所有节点都访问完了，我们也就得到了二叉树的节点个数，我们可以直接使用前序遍历，或者其他遍历方式，再加上计数器就可以实现了。代码如下：

void css(BTNode* root, int* size)
{
	if (root == NULL)
	{
		return;
	}
	(*size)++;
	css(root->_left,size);
	css(root->_right,size);
}
int BinaryTreeSize(BTNode* root)
{
	int size = 0;
	css(root, &size);
	return size;
}

还有一种方法就是在递归的时候如果当前节点为空，返回 0；否则，返回左子树的节点个数加上右子树的节点个数再加上 1（当前节点）。代码如下：

int BinaryTreeSize(BTNode* root)
{
	//int size = 0;
	//css(root, &size);
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

（五）、二叉树叶子节点的个数

叶节点是指没有子节点的节点。计算叶节点个数同样可以使用递归方法。如果当前节点为空，返回 0；如果当前节点没有左子节点和右子节点，说明它是叶节点，返回 1；否则，返回左子树的叶节点个数加上右子树的叶节点个数。代码如下：

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left)+BinaryTreeLeafSize(root->_right);
}

（六）、二叉树第K层节点个数

计算二叉树第 k 层的节点个数，我们可以通过递归来实现。如果当前节点为空或者 k 小于 1，返回 0；当 k 等于 1 时，说明到达了目标层，返回 1；否则，递归地计算左子树和右子树第 k - 1 层的节点个数并相加。代码如下：

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

	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
	return 0;
}

（七）、二叉树查找值为X的节点

查找值为 x 的节点，我们可以从根节点开始，通过递归的方式在二叉树中进行查找。如果当前节点为空，返回 NULL；如果当前节点的值等于 x，返回当前节点；否则，先在左子树中查找，如果找到则返回找到的节点，否则在右子树中查找。代码如下：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	if (BinaryTreeFind(root->_left, x) != NULL)
	{
		return BinaryTreeFind(root->_left, x);
	}
	if (BinaryTreeFind(root->_right, x) != NULL)
	{
		BinaryTreeFind(root->_right, x);
	}
}

如此一个二叉树的基本实现就完成了。全部代码如下：

FBinaryTree.c副源文件

BinaryTree.h头文件

BinaryTree.c源文件

#include"BinaryTree.h"
BTNode* BuyBinaryNode(char x)
{
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	Node->_data = x;
	Node->_left = Node->_right = NULL;
	return Node;
}
BTNode* _BinaryTreeCreate(int* i,BTDataType* a,int n)
{
	if (a[*i] == '#')
	{
		(*i)++;
		return NULL;
	}
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		return NULL;
	}
	Node->_data = a[(*i)++];
	Node->_left = _BinaryTreeCreate(i, a,n);
	Node->_right = _BinaryTreeCreate(i, a,n);
	return Node;
}
BTNode* BinaryTreeCreate(BTDataType* a, int n)
{
	int i = 0;
	return _BinaryTreeCreate(&i, a,n);
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
	*root = NULL;
}
void css(BTNode* root, int* size)
{
	if (root == NULL)
	{
		return;
	}
	(*size)++;
	css(root->_left,size);
	css(root->_right,size);
}
int BinaryTreeSize(BTNode* root)
{
	//int size = 0;
	//css(root, &size);
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left)+BinaryTreeLeafSize(root->_right);
}

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

	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
	return 0;
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	if (BinaryTreeFind(root->_left, x) != NULL)
	{
		return BinaryTreeFind(root->_left, x);
	}
	if (BinaryTreeFind(root->_right, x) != NULL)
	{
		BinaryTreeFind(root->_right, x);
	}
}

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;//数据域
	struct BinaryTreeNode* _left;//左子节点
	struct BinaryTreeNode* _right;//右子节点
}BTNode;
BTNode* BuyBinaryNode(char x);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n);
// 二叉树销毁
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);

#include"BinaryTree.h"
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}
typedef struct QueueNode
{
	BTNode* data;
	struct QueueNode* next;
}Qnode;
typedef struct Queue
{
	//头指针
	Qnode* head;
	//尾指针
	Qnode* tail;
	//计数存储数据个数
	int size;
}Queue;
void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
}

void QueuePush(Queue* q,BTNode* x)
{
	assert(q);
	//申请新节点
	Qnode* ptr = (Qnode*)malloc(sizeof(Qnode));
	if (ptr == NULL)
	{
		perror("QueuePush::malloc");
		return;
	}
	ptr->data = x;
	//提前将新节点next指针置空
	ptr->next = NULL;
	//判断队列是否为空
	if (q->head == NULL && q->tail == NULL)
	{
		q->head = q->tail = ptr;
	}
	else
	{
		q->tail->next = ptr;
		q->tail = ptr;
	}
	q->size++;
}

void QueuePop(Queue* q)
{
	assert(q);
	//判断头指针是否为空，为空那还出什么队列
	assert(q->head);
	//先存储头指针指向的节点的下一个节点的位置
	Qnode* headnext = q->head->next;
	//释放头指针指向的节点空间
	free(q->head);
	//再让头指针指向之前存储的节点
	q->head = headnext;
	//如果队列中只有一个节点，那释放空间后，头指针是空，但
	//尾指针没有被置为空，而是处于野指针状态，因此也要将
	//尾指针置空
	if (q->head == NULL)
	{
		q->tail = NULL;
	}
	q->size--;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size;
}

void QueueDestroy(Queue* q)
{
	assert(q);
	Qnode* ptr = q->head;
	if (q->head == NULL)
	{
		return;
	}
	while (ptr)
	{
		Qnode* ptrnext = ptr->next;
		free(ptr);
		ptr = ptrnext;
	}
	q->head = q->tail = NULL;
	printf("队列销毁成功\n");
	q->size = 0;
}
BTNode* QueueFront(Queue* q)
{
	assert(q);
	if (q->head == NULL)
	{
		return NULL;
	}
	return q->head->data;
}
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (QueueEmpty(&q))
	{
		BTNode* foot = QueueFront(&q);
		printf("%c ", foot->_data);
		QueuePop(&q);
		if (foot->_left)
		{
			QueuePush(&q, foot->_left);
		}
		if (foot->_right)
		{
			QueuePush(&q, foot->_right);
		}
	}
}
int main()
{
	BTNode* nodeA = BuyBinaryNode('A');
	BTNode* nodeB = BuyBinaryNode('B');
	BTNode* nodeC = BuyBinaryNode('C');
	BTNode* nodeD = BuyBinaryNode('D');
	BTNode* nodeE = BuyBinaryNode('E');
	BTNode* nodeF = BuyBinaryNode('F');
	BTNode* nodeG = BuyBinaryNode('G');
	nodeA->_left = nodeB;
	nodeA->_right = nodeC;
	nodeB->_left = nodeD;
	nodeB->_right = nodeE;
	nodeC->_left = nodeF;
	nodeC->_right = nodeG;
	BinaryTreePrevOrder(nodeA);
	printf("\n");
	BinaryTreeInOrder(nodeA);
	printf("\n");
	BinaryTreePostOrder(nodeA);
	printf("\n");
	BinaryTreeLevelOrder(nodeA);
	printf("\n");
	BTDataType a[] = "ABD##E#H##CF##G##";
	BTNode* root = BinaryTreeCreate(a, strlen(a));
	BinaryTreePrevOrder(root);
	printf("\n");
	printf("%d\n", BinaryTreeSize(nodeA)); 
	printf("%d\n", BinaryTreeLeafSize(nodeA));
	printf("%d\n", BinaryTreeLevelKSize(nodeA, 3));
	BTNode* node = BinaryTreeFind(nodeA, 'D');
	printf("%c\n", node->_data);
    BinaryTreeDestory(&nodeA);
	return 0;
}

三、DFS（深度优先遍历）和BFS（广度优先遍历）

DFS，就像是一位充满冒险精神的探险家，在面对一座迷宫般的图或树时，总是迫不及待地沿着一条通道一直走下去，直到前方无路可走，才会无奈地回头，寻找其他可能的通道继续探索。在计算机科学中，DFS 沿着树或图的深度，从起始节点开始，递归地访问每一个可能的分支路径，直到到达叶子节点或者没有未访问的节点时，才回溯到上一个节点，继续探索其他未被访问的分支。

实现 DFS 主要有两种方式：递归和栈。递归实现的 DFS 简洁而优雅，它利用函数调用栈来自动管理节点的访问顺序。

而BFS 则像是一位有条不紊的规划者，在探索图或树时，它从起始节点出发，先访问与起始节点直接相连的所有节点，也就是第一层节点。然后，再依次访问这些第一层节点的未访问过的邻居节点，即第二层节点，如此一层一层地向外扩展，直到所有可达节点都被访问完。

在实现 BFS 时，队列这种数据结构发挥了关键作用。队列遵循先进先出（FIFO）的原则，正好契合 BFS 逐层访问的特性。

在二叉树中，DFS就是二叉树的前序遍历，BFS就是二叉树的层序遍历。

至此，二叉树的链式结构就结束了，如果面对递归感到难以理解，那么画它的递归展开图来帮助理解一定是最有用的方法。如果对哪里还是感到困惑，可以放到评论区，谢谢观看。