【数据结构与算法】详解二叉树下：实践篇————通过链式结构深入理解并实现二叉树

在计算机科学中，二叉树是一种重要的数据结构，它以其独特的结构和性质在数据存储、搜索和算法设计中发挥着重要作用。链式结构作为二叉树的一种常见表示方式，通过节点间的指针连接，实现了对二叉树的高效存储和访问。

一、二叉树前置知识

参考前置文章：二叉树理论篇

【数据结构与算法】详解二叉树 上：理论篇——二叉树的基本概念与性质-CSDN博客

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

二叉树的每个节点包括三个部分：

• 数据部分，这里称为data
• 左指针，指向节点的左孩子，这里称为left指针。如果左孩子为空，则指向NULL
• 右指针，指向节点的右孩子，这里称为right指针。如果右孩子为空，则指向NULL

结构如下图所示：

结构定义如下：

typedef char 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("newnode\n");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

二叉树的一般插入意义不大，跟手动插入无异，后面会在搜索二叉树篇章讲解二叉树插入的实现

🍃销毁

递归调用完成销毁，每棵树先释放左孩子和右孩子，再返回去销毁根，因此使用后序遍历的方法最为合适（不需要记录孩子，只需要正常遍历销毁即可） 后序遍历，文章的后面便会介绍，如果不太理解，可以直接点击目录查看遍历部分 调用函数 如果节点为空，直接返回 如果节点非空

• 先调用函数释放左子树
• 再调用函数释放右子树
• 最后释放节点自身

void BinaryTreeDestory(BTNode* root)//后序遍历并销毁
{
	if (root== NULL)
		return;
	BinaryTreeDestory(root->left);//左
	BinaryTreeDestory(root->right);//右
	free(root);//根
}

四、二叉树的遍历

二叉树的遍历是二叉树的基本操作之一，它指的是按照某种规则访问二叉树中的所有节点，并且每个节点只被访问一次。二叉树的遍历方式有多种，其中最常见的有四种：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）和层序遍历（Level-order Traversal）。

• 前序遍历（根 左 右）
• 中序遍历（左 根 右）
• 后序遍历（左 右 根)
• 层序遍历（逐层访问）

这里以每次遍历节点打印节点数据为例（指针走到空打印N）

🍃前序遍历

使用递归的方法实现：

• 访问根节点
• 前序遍历左子树
• 前序遍历右子树

接收一个指针（地址）

指针从二叉树的根结点开始遍历

递归的结束条件: 指针指向空，则打印N，return

不满足递归条件，向深处递推:

1. 打印指针指向的节点的数据（相当于访问根节点）

2. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）

3.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	printf("%c", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);

}

🍃中序遍历

使用递归的方法实现：

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

接收一个指针（地址）

指针从二叉树的根结点开始遍历

递归的结束条件:指针指向空，则打印N，return

不满足递归条件，向深处递推:

1. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）

2.打印本节点的数据（相当于访问根节点）

3.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c", root->data);
	BinaryTreeInOrder(root->right);
}

🍃后序遍历

使用递归的方法实现：

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点

接收一个指针（地址）

指针从二叉树的根结点开始遍历

递归的结束条件:指针指向空，则打印N，return

不满足递归条件，向深处递推:

1. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）

2.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）

3.打印本节点数据（相当于访问根节点）

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c", root->data);
	
}

🍃层序遍历

层序遍历（Level-order Traversal）

• 从根节点开始，按层次从上到下、从左到右遍历二叉树

通常使用队列（Queue）来实现层序遍历。

如果树不为空，将它的根结点的地址作为数据，入队列

对队列的节点访问:

每次取队首的节点访问，将它的地址记录下来并出队列，同时将它的左右孩子（如果存在的话)入队列

当队列为空时，二叉树的层次遍历完成

层次遍历直接借用了以前已经实现好的队列，详细内容可以参考前置文章 【数据结构与算法】使用单链表实现队列：原理、步骤与应用_利用循环单链表(如下图)模拟实现队列操作,请给出入队enqueue过程,要求时间复-CSDN博客

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);//队列初始化
	if (root)//树的根节点入队列
		QueuePush(&queue, root);

	while (!QueueEmpty(&queue))//结束条件是队列为空
	{
		BTNode* tmp = QueueFront(&queue);//取队首元素打印数据并出队列
		printf("%c", tmp->data);
		QueuePop(&queue);

		//左右子树若不为空，入队列
		if (tmp->left)
			QueuePush(&queue, tmp->left);
		if (tmp->right)
			QueuePush(&queue, tmp->right);
	}
	printf("\n");
	QueueDestroy(&queue);
}

五、二叉树的扩展功能

🍃求节点个数

两种方式:

方式一:计数器方式 这种方式需要考虑的坑比较多——想要求得树的节点个数就得递归调用，所以用局部变量计数不可行（每次调用都会重置变量），静态局部变量也不可行（一次调用可行，多次调用会将值累加） 全局变量可行，但得在外部每次调用的时候对全局变量置零 指针的方式也可行:实参多传递一个变量的地址，形参用指针接收，多次调用也需要重新创建变量或置零 这两种方式的实现思路: 如果节点为空，返回 否则计数器++ 再调用函数对左子树求个数 调用函数对右子树求值 函数不需要返回值，会通过全局变量/指针带出

方式一并不推荐，实现复杂容易出错，所以这里就不给出实现代码了、

方式二: 递归方式（推荐）

• 递归调用相加对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。
• 否则，返回1（表示当前节点本身）加上左子树和右子树的节点数（递归调用）

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

🍃求叶子节点个数

解决方式与求二叉树的节点数量类似，同样使用递归实现，只是细节略有差异: 递归调用:

• 对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。
• 如果节点左右孩子都为空，返回1（表示当前节点为叶子节点）
• 如果上面两个return都没有执行，说明该节点既不为空也不是叶子节点，返回左子树+右子树的叶子节点数（递归调用）

// 二叉树叶子节点个数
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层……逐层分解，对于第k层，求的就是第一层 具体实现逻辑：

• 递归调用函数，参数有两个，分别是节点地址和k
• 如果节点为空，返回0
• 上述判断不成立，再判断如果k==1，返回1
• 如果上述都没有执行，说明节点既不为空，也不是第k层
• 递归调用函数，返回该节点的左孩子的k-1层的节点数+右孩子的k-1层的节点数（如果下一层k==1，则直接返回结果；如果不是，还会继续递归调用）

// 二叉树第k层节点个数
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);

}

🍃求二叉树的高度

二叉树的高度（或深度）是指从根节点到最远叶子节点的最长路径上的节点数。一个空树的高度定义为0 对于非空二叉树，其高度可以通过递归的方式计算：

• 如果树是空的，那么高度是0。
• 否则，高度是左子树和右子树高度的最大值加1（加1是因为要算上根节点）。

不过这里有一个坑要避免一下: 如果用三目操作符完成return语句，即:return（ root-＞left)＞（root-＞right)？（ root-＞left)+1:（root-＞right)+1 在树比较大时，时间会出现极端的增长 原因是第一次计算的结果没有被记录下来，每次都要重复计算两次，但第一层计算两次，第二层就多计算2*2次，第三层计算2*2*2次，以此类推，将会是一个非常恐怖的计算量 解决方式也很简单: 如果树是空的，那么高度是0。 否则，先求得左右孩子的高度记录并记录下来，两个值比较，将较大的值+1返回

//求树的高度
int BinaryHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BinaryHeight(root->left);
	int rightHeight = BinaryHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

🍃查找值为X的节点

实现思路: 递归遍历二叉树，查找值为x的节点 但有一个关键且容易被忽略的点，就是如何在递归调用的过程中，将查找到的节点的地址通过返回值带出来（因为是递归调用，所以必须让函数的第一层带出返回值） 实现方法： 递归调用函数如果节点为空，返回NULL 上述未执行，再判断节点的值是否为x，如果是的话，返回该节点的地址（注意此处返回只能返回给上一层，不能跳出整个函数）如果上述都未执行，再进一步判断: 调用函数获取左子树返回的值，如果该值不为空，说明获得了值为x的节点的地址，将该值返回给上一层 如果调用左子树未返回值，再调用函数获取右子树返回的值，如果改值不为空，说明获得了值为x的节点的地址，将该值返回给上一层 上述表达式都未返回结果，说明查不到值为X的节点，返回NULL

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* n1 = BinaryTreeFind(root->left, x);
	if (n1)
		return n1;
	BTNode* n2 = BinaryTreeFind(root->right, x);
	if (n2)
		return n2;
	return NULL;
}