【初阶数据结构与算法】二叉树链式结构的定义与实现万字笔记(附源码)

【初阶数据结构与算法】二叉树链式结构的定义与实现万字笔记(附源码)

一、二叉树链式结构的定义

   链式二叉树就是⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系，通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址，数据域则是当前节点存放的数据，其结构如下：

代码语言：javascript代码运行次数：0运行复制

typedef int BTDataType;

typedef struct BinaryTreeode
{
	BTDataType data;
	struct BinaryTreeode* left;
	struct BinaryTreeode* right;
}BTode;

   当我们使用链式结构来表示二叉树时，这个二叉树并不会有很多限制，它对节点的插入删除等操作要求并不高，所以我们后面会手动来创建链式二叉树，本文重要的不是创建二叉树的方法，而是二叉树各种功能的实现    那么什么时候我们不能手动创建二叉树了呢？这个就要等我们后面在C++部分讲到二叉搜索树才能揭晓答案，二叉搜索树就只能通过特定的函数创建，而不能手动创建了，接着我们就再次回到我们今天的主题—二叉树链式结构功能的基本实现

二、二叉树链式结构功能的基本实现

1.链式二叉树的手动创建

   链式二叉树的手动创建很简单，就是创建一堆的节点，然后将它们互相连接起来，这里给出一个二叉树的图片，我们按照图片的结构手动创建一颗链式二叉树，如下：

   为了方便我们直接操作，我们先写一个申请二叉树节点的函数，可以通过传节点的值来帮我们申请一个具有该值的节点，如下：

代码语言：javascript代码运行次数：0运行复制

//申请节点
BTode* BTBuyode(BTDataType x)
{
	BTode* newnode = (BTode*)malloc(sizeof(BTode));
	if (newnode == ULL)
	{
		perror("mallc");
		return ULL;
	}
	newnode->data = x;
	newnode->left = newnode->right = ULL;
	return newnode;
}

   接下来我们就挨个的申请节点，然后使用左右指针将这些节点串联起来，如下：

代码语言：javascript代码运行次数：0运行复制

//手动创建一颗链式二叉树
//返回根节点
BTode* CreateBinaryTree()
{
	BTode* nodeA = BTBuyode('A');
	BTode* nodeB = BTBuyode('B');
	BTode* nodeC = BTBuyode('C');
	BTode* nodeD = BTBuyode('D');
	BTode* nodeE = BTBuyode('E');
	BTode* nodeF = BTBuyode('F');
	BTode* nodeG = BTBuyode('G');
	BTode* nodeH = BTBuyode('H');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeB->right = nodeE;
	nodeC->left = nodeF;
	nodeC->right = nodeG;
	nodeD->left = nodeH;

	return nodeA;
}

   这样我们手动创建一颗链式二叉树，返回了它的根节点，接下来我们就可以开始对它进行操作了，后面的内容才是今天的重点

2.链式二叉树的前中后序遍历

   链式二叉树的这个结构非常适合递归，它每一次函数调用创建的栈帧就可以看做我们要递归的一个节点，在链式二叉树的接口实现中，我们一定要有抽象能力，当然，我们后面也会给大家画图来解释，这里不再多说    我们今天第一个重点就是完成链式二叉树的遍历，如果不能实现二叉树的遍历，那么我们连里面存放了什么数据都不知道，所以接下来我们就开始介绍二叉树的前中后序遍历    首先我们来解释一下前中后序遍历，前序遍历就是根左右，也就是先打印当前子树中的根，再把左右孩子当成另外两颗子树，继续递归执行根左右的思想    中序遍历就是左根右，也就是先递归打印当前根的左孩子这颗子树，然后再打印根节点，最后再递归打印当前根的右孩子这颗子树    而后序遍历就是左右根，跟上面两种例子是同样的思想，就是先递归打印当前根的左子树，再递归打印当前根的右子树，最后再打印根    听到这里你是不是懵了呢？这是很正常的，光听概念是很难学会递归的，我们要在实例中去应用才能掌握，所以下面实现前中后序遍历的过程和思想才是我们要重点掌握的，而不是这里前中后序遍历的概念，我们来一起学习吧！

前序遍历

   前序遍历就是左右根，打印当前子树中的根，左右孩子又分别成一颗子树，于是左右孩子又再次执行上面的根左右的遍历思想，最终这样递归下去就可以实现二叉树的前序遍历    如果不理解可以先不管，现在我们先把代码写出来，等一下根据代码我们来画图才能将它说清楚，这也是一种学习方法，这种抽象的算法先看代码再理解，否则很难想到，之后我们才能根据理解写出类似的算法，如下：

代码语言：javascript代码运行次数：0运行复制

//前序遍历
void PreOrder(BTode* root)
{
	if (root == ULL)
	{
		//走到空节点开始返回
		return;
	}
	//打印根节点
	printf("%c ", root->data);
	//递归左孩子这颗子树
	PreOrder(root->left);
	//递归右孩子这颗子树
	PreOrder(root->right);
}

   接着我们来画图按照这段代码的逻辑来走一遍我们的前序遍历，要仔细理解这里的图，后面才能解决我们的中后序遍历，如图：

   那么我们分析完前序遍历之后，我们来看看我们前序遍历代码能不能实现我们画图所诉的打印，如图：

   可以看到代码的运行结果和我们分析的一模一样，这就是我们的前序遍历，是我们第一次接触到递归的暴力美学，所以我们讲的很仔细，要仔细理解    后面的中后序遍历基本上都是一个思想，所以后面的中后序遍历就不再画图了，可以自行画图来理解，思路大致相同

中序遍历

   中序遍历就是先递归打印左孩子这颗子树，然后打印根节点，最后再递归打印右孩子这颗子树，和前序遍历的思想都很接近，只是说根节点的打印不同    中序遍历的实现和前序遍历的思想差不多，也是通过递归实现，可以自己尝试画画中序遍历的图，看看自己能不能写出来中序遍历，再来看后面的代码，这里就直接给出中序遍历的实现代码了：

代码语言：javascript代码运行次数：0运行复制

//中序遍历:左根右
void InOrder(BTode* root)
{
	if (root == ULL)
	{
		//走到空节点开始返回
		return;
	}
	//递归左孩子这颗子树
	InOrder(root->left);
	//打印根节点
	printf("%c ", root->data);
	//递归右孩子这颗子树
	InOrder(root->right);
}

   我们来看看代码运行结果：

   可以看到中序遍历和前序遍历代码的实现只有一点点不同，就是打印根节点的位置不同，但是其实结果已经发生了超级多的变化，如果感兴趣可以自行画画图理解，思路和前序遍历差不多

后序遍历

   后序遍历就是先递归打印当前根的左子树，再递归打印当前根的右子树，最后再打印根，跟上面前中序遍历的思路很像    而现在我们有了前中序遍历思想的启迪，接下来我们实现后序遍历就很简单了，很多同学可能都能直接猜到代码该怎么写，那么在这之前，还是希望大家先画图分析一下，写出代码，再来看看自己写的对不对，代码如下：

代码语言：javascript代码运行次数：0运行复制

//后序遍历:左右根
void PostOrder(BTode* root)
{
	if (root == ULL)
	{
		//走到空节点开始返回
		return;
	}
	//递归左孩子这颗子树
	PostOrder(root->left);
	//递归右孩子这颗子树
	PostOrder(root->right);
	//打印根节点
	printf("%c ", root->data);
}

   我们来看看代码运行结果：

   可以看到后序遍历和前中序遍历代码的实现基本上也是差别很小，也是打印根节点的位置不同，但是其实也发生了很多的变化，希望可以自己画图理解理解，这里就不再画了，接着学习链式二叉树的下一个接口

.链式二叉树节点的个数

   在上面我们稍微体会到了一点递归的暴力美学，从现在开始，就是真正开始爽的地方，我们就根据之前前中后序的递归思想实现这些接口，代码量都很小，但是却可以实现我们的要求，我们一起来学习    求二叉树节点的个数不就是求当前根节点的个数，再加上左右子树节点的个数吗？所以我们可以利用递归的思想，当前根节点算1，然后加上左右子树节点的个数    当然，我们一旦要递归就要考虑返回条件，这里的返回条件就是根节点为空，如果根节点为空了，就直接返回0，于是代码就水灵灵出来了，如下：

代码语言：javascript代码运行次数：0运行复制

//二叉树节点的个数
int BinaryTreeSize(BTode* root)
{
	if (root == ULL)
	{
		return 0;
	}
	int leftsize = BinaryTreeSize(root->left);
	int rightsize = BinaryTreeSize(root->right);

	return 1 + leftsize + rightsize;
}

   我们来看看代码运行结果：

   可以看到成功算出了我们二叉树中所有节点的个数

4.链式二叉树叶子节点的个数

   求整颗二叉树叶子节点个数可以猜分为，左子树叶子节点个数加右子树叶子节点个数，这样就可以继续使用我们的递归思想了    求叶子节点个数相当于比前面要求严格一些，不是只要根节点不为空就要算，而是根节点既不为空，并且这个根节点的左右孩子都为空，这样才算一个    所以我们最后总结为，如果根节点为空直接返回，如果不为空并且左右孩子都为空就返回1，然后我们整颗二叉树叶子节点个数这个问题就可以拆成，左子树叶子节点个数加右子树叶子节点个数，如下：

代码语言：javascript代码运行次数：0运行复制

//二叉树叶子节点的个数
int BinaryTreeLeaveSize(BTode* root)
{
	if (root == ULL)
	{
		return 0;
	}
	if (root->left == ULL && root->right == ULL)
	{
		return 1;
	}
	int leftsize = BinaryTreeLeaveSize(root->left);
	int rightsize = BinaryTreeLeaveSize(root->right);

	return leftsize + rightsize;
}

   我们来看看代码运行结果：

   可以看到得出了我们想要的结果

5.链式二叉树的高度/深度

   在解决这个问题之前，我们要知道如何判断二叉树的高度，就是给我们二叉树，我们要能判断二叉树的高度，如图：

   我们肉眼可能一下就看出来，二叉树1的高度为4，二叉树2的高度为，那么它们是怎么来的呢？其实二叉树的高度就是它左右子树中最高的那个，最后再加上根节点，所以我们就还是可以利用递归的算法思想，如下：

代码语言：javascript代码运行次数：0运行复制

//二叉树的高度/深度
int BinaryTreeDepth(BTode* root)
{
	if (root == ULL)
	{
		return 0;
	}
	int leftDepth = 1 + BinaryTreeDepth(root->left);
	int rightDepth = 1 + BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth : rightDepth;
}

   我们来看看代码运行结果：

   可以看到得出了我们想要的结果

6.链式二叉树第k层节点的个数

   这个需求就和上面求叶子节点个数类似，求叶子节点个数是如果左右孩子为空返回1，这里就是如果当前节点在k层就返回1    那么如何判断这个节点是否在第k层呢？首先我们还是使用递归的算法思想，将求二叉树第k层节点的个数，转化为求二叉树左右子树的第k层节点个数的和    具体判断方法就是，我们每递归一层就让k-1，当k变成了1，那么就说明当前节点就在第k层，这个可以自行尝试，这里就不再多说    那么有了这个思路我们就可以直接写代码了，如下：

代码语言：javascript代码运行次数：0运行复制

//⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTode* root, int k)
{
	if (root == ULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1);
}

   我们来看看代码运行结果：

   可以看到程序帮我们算出了对应层次节点的个数

7.链式二叉树的查

   这个功能我们还是可以使用递归的思想解决，我们在二叉树中查某个节点，其实就是看当前根节点是不是要查的节点，如果是就直接返回    如果不是就去对应的左子树里面，如果左子树里面到了，就直接返回，如果左子树也没有到，就去右子树中，如果到了就直接返回，如果最后左右子树都没有到就直接返回空，如下：

代码语言：javascript代码运行次数：0运行复制

//查值为x的节点
BTode* BinaryTreeFind(BTode* root, BTDataType x)
{
	if (root == ULL)
	{
		return ULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTode* left = BinaryTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	BTode* right = BinaryTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return ULL;
}

   我们来测试一下代码能否实现我们的查功能，首先我们来二叉树中有的节点，如图：

   可以看到程序很好地完成了任务，接下来我们再测试一下如果二叉树没有这个节点会不会被到，如图：

   可以看到程序最后没有到，符合我们的预期，那么我们的查功能就实现完毕啦

8.链式二叉树层序遍历

   接下来的二叉树的层序遍历和判断是否为完全二叉树相对于之前的结构就会难一些，因为这两个接口不能使用递归完成    首先我们来介绍一下层序遍历，层序遍历就是按层次来访问各个节点，我们举一个例子：

   在这颗二叉树中，如果我们按照层序遍历打印节点，那么最后结果一定是ABCDEFGH，每个节点都按照对应的层次依次打印，这就是层序遍历    那么怎么实现层序遍历呢？这里我也不再卖关子了，实现链式二叉树的层序遍历要使用我们之前学过的一个数据结构—队列，接下来我们就先把队列加入我们的项目    我们可以直接将队列的头文件和实现文件添加到当前目录下，如果不会的话也可以麻烦一点去把之前写过的队列内容拷贝到我们的项目里，这里就不再多说了    在讲解原理前，我们先把队列里面的数据类型改成我们的二叉树节点指针类型，这样才能让我们的队列存放我们的二叉树节点    接着我们就来讲解如何使用队列实现层序遍历，方法就是从先让根节点入队列，随后我们就创建一个循环，只要队列不为空我们就循环执行以下的操作    我们取出当前队列的头节点，然后打印里面的内容，随后将当前这个节点的左右孩子入队列，让当前节点出队列，当然，我们要注意一点的就是，如果当前节点左孩子或者右孩子为空，那么就没有必要入队列了，所以要进行一下判断    以上就是我们层序遍历的所有思路，可以自行画图理解一下，这里我们直接根据上面的思路来写代码，如下：

代码语言：javascript代码运行次数：0运行复制

//二叉树层序遍历
void LevelOrder(BTode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTode* front = QueueFront(&q);
		printf("%c ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
}

   我们来看看代码运行结果：

   可以看到程序确实帮我们按层次打印了各个节点，那么我们的层序遍历就实现完毕啦

9.判断链式二叉树是否为完全二叉树

   首先我们自己要知道如何判断一颗二叉树是不是完全二叉树，判断方法就是，保证除了最后一层以外，其它层次满了，并且保证最后一层的节点是左右依次排列的，这样才是一颗完全二叉树    那么我们怎么用程序来判断呢？这里我们需要用到上面我们层序遍历的思想，不同的是层序遍历时不把空节点入队列，而我们这里要把空节点也入队列    因为我们可以将判断一颗二叉树是否为完全二叉树这个问题转化为，层序遍历时遍历到最后一个节点后，接下来队列中的节点只能是空，换句话说，如果在层序遍历时碰到了空节点，那么队列后面就都只能为空，这样才是完全二叉树    如果在如果在层序遍历时碰到了空节点，但是队列后面有非空节点，说明这颗树就不是完全二叉树，不信的话可以自己画画图，这里就不再画了，我们直接根据这个思路来写代码，判断层序遍历碰到空节点后，队列后面的节点是否都为空，如下：

代码语言：javascript代码运行次数：0运行复制

//是否为完全二叉树
bool BinaryTreeComplete(BTode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTode* front = QueueFront(&q);
		if (front == ULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q))
	{
		BTode* front = QueueFront(&q);
		if (front)
		{
			return false;
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return true;
}

   我们来看看代码运行结果：

   可以看到程序成功帮我们判断出当前二叉树是一颗完全二叉树，也可以自行创建一颗非完全二叉树试试，也没有问题

10.链式二叉树的销毁

   由于我们链式二叉树的节点都是动态申请的，所以我们要将它们进行释放，否则会造成内存泄漏，要一个一个地销毁节点，说明我们要遍历整颗二叉树，我们上面学过的遍历方法就起到作用了    我们就可以直接选择后序遍历来释放节点，先释放左右子树，最后释放掉我们的根节点，并且将根节点置空，如下：

代码语言：javascript代码运行次数：0运行复制

//二叉树的销毁
void BinaryTreeDestroy(BTode** proot)
{
	if (*(proot) == ULL)
	{
		return;
	}
	BinaryTreeDestroy(&(*proot)->left);
	BinaryTreeDestroy(&(*proot)->right);
	free(*proot);
	*proot = ULL;
}

三、源码代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

typedef char BTDataType;

typedef struct BinaryTreeode
{
	BTDataType data;
	struct BinaryTreeode* left;
	struct BinaryTreeode* right;
}BTode;

//前序遍历
void PreOrder(BTode* root)
{
	if (root == ULL)
	{
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历
void InOrder(BTode* root)
{
	if (root == ULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历
void PostOrder(BTode* root)
{
	if (root == ULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

//二叉树节点个数
int BinaryTreeSize(BTode* root)
{
	if (root == ULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//二叉树叶子节点个数
int BinaryTreeLeaveSize(BTode* root)
{
	if (root == ULL)
	{
		return 0;
	}
	if (root->left == ULL && root->right == ULL)
	{
		return 1;
	}
	return BinaryTreeLeaveSize(root->left) + BinaryTreeLeaveSize(root->right);
}

//⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTode* root, int k)
{
	if (root == ULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1);
}

//二叉树高度
int BinaryTreeDepth(BTode* root)
{
	if (root == ULL)
	{
		return 0;
	}
	int leftDepth = 1 + BinaryTreeDepth(root->left);
	int rightDepth = 1 + BinaryTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth : rightDepth;
}

//查值为x的节点
BTode* BinaryTreeFind(BTode* root, BTDataType x)
{
	if (root == ULL)
	{
		return ULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTode* left = BinaryTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	BTode* right = BinaryTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return ULL;
}

//二叉树的销毁
void BinaryTreeDestroy(BTode** proot)
{
	if (*(proot) == ULL)
	{
		return;
	}
	BinaryTreeDestroy(&(*proot)->left);
	BinaryTreeDestroy(&(*proot)->right);
	free(*proot);
	*proot = ULL;
}

//二叉树层序遍历
void LevelOrder(BTode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTode* front = QueueFront(&q);
		printf("%c ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
}

//是否为完全二叉树
bool BinaryTreeComplete(BTode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTode* front = QueueFront(&q);
		if (front == ULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q))
	{
		BTode* front = QueueFront(&q);
		if (front)
		{
			return false;
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return true;
}

   那么今天二叉树链式结构的定义与实现就结束啦，后面我们讲完链式二叉树的一些OJ题后初阶数据结构就差不多结束了，可以进入我们的排序算法了，敬请期待吧！    bye~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-05，如有侵权请联系 cloudcommunity@tencent 删除前往查看笔记遍历数据结构与算法源码二叉树