【二叉树】——链式结构（快速掌握递归与刷题技巧）

📙作者简介： 清水加冰，目前大二在读，正在学习C/C++、Python、操作系统、数据库等。

📘相关专栏：C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。

欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正！

✨每一次努力都是一种收获，每一次坚持都是一种成长✨       

目录

 前言

1. 二叉树的链式结构

   1.1链式二叉树的结构

2. 二叉树初阶训练

 2.1 二叉树节点个数

 2.2 叶子节点个数

 2.3 第k层节点个数

总结

---

 前言

        前边我主要介绍了二叉树的顺序结构，链式结构也只是简单提及，今天我们来详细介绍一下二叉树的链式结构。

---

1. 二叉树的链式结构

        二叉树的顺序结构是通过顺序表来存储二叉树的数据，那么链式结构就是通过链表，连接二叉树的各个节点，进而来实现二叉树的树形结构。链式二叉树存储不需要像堆那要必须是完全二叉树，它可以是一颗普通二叉树。 

   1.1链式二叉树的结构

        二叉树的链式结构是指使用节点之间的指针连接来表示二叉树的结构。在链式结构中，每个节点都包含一个数据元素和指向其左子节点和右子节点的指针。一个二叉树的节点通常由两个部分组成：数据域和指针域。

typedef struct BinaryTree
{
	int data;//数据域
	struct BinaryTree* left;//指针域
	struct BinaryTree* right;//指针域
}BTNode;

         通过这种链式结构，我们可以方便地遍历和操作二叉树。最常见的遍历方法就是使用递归遍历二叉树。前边我们也简单介绍了二叉树的前序、中序、后续遍历。也很简单，但是在实际中，并不会这么直白的让你递归遍历二叉树，都是遍历的变形。

2. 二叉树初阶训练

 2.1 二叉树节点个数

   如何计算一个二叉树的节点个数呢？

  链式结构的树使用递归来遍历最简单，也是最常用的遍历方法。这样写吗？

int TreeSize(BTNode* root)
{
	int size = 0;
	if (root == NULL)
		return 0;
	else
		++size;
	
	TreeSize(root->left);
	TreeSize(root->right);
	
	return size;
}

         节点是NULL就返回0，不为空就size++。看似没有问题，但深入思考一下就会发现端倪，每次递归都会重新创建一个size然后++，每次的size都加到了一个size上吗？其实并没有，size出了函数作用域就会销毁，递归到叶子节点返回后，前边的size就会被销毁。

         只要解决size作用域问题是不是就可以解决了？增加size的生命周期有两种方法，一个是使用全局变量，另一个是使用static修饰。这样虽然可以计算出二叉树的节点个数，但这样也存在缺点，这个函数的使用就会变成一次性的，如果在一个程序中多次调用，数据就会累计（如第一次是5，第二次就是10……），也有解决的办法就是每次使用前将size置为0。但这都不是这个问题的最优解，最优解就是使用递归解决。

        递归的核心就是分治，将一个复杂的过程分解成一个一个的类似子问题。要计算一颗二叉树的节点个数就只需要计算左子树节点个数+右子树节点个数+1。左子树又可以分为左子树右子树，直到叶子节点，叶子节点的左右子树为NULL，所以遇到NULL就返回0；那我们就可以这样写：

int TreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

 如下图：

         虚线代表的递归返回，返回节点的个数。这里也仅仅是一个简单的递归，有了这个题目的思路，我们来进阶一下。

 2.2 叶子节点个数

        计算叶子节点个数也是使用递归，对这个问题进行分治，计算一棵树的叶子节点个数，也就是左子树和右子树中叶子节点的个数，子树又可以再分为左子树、右子树。遇到叶子节点就停止。使用递归可以大幅的减少代码的复杂度。现在就只需考虑一下递归停止的条件。叶子节点的左子树与右子树都为空，所有当根的左右子树都为NULL时就可以判定为叶子节点。

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);
}

  例如这棵树，有三个叶子节点：

         当前节点为NULL就不是叶子节点返回0，如果左右子树都为NULL，则该节点就是叶子节点，返回1，最后将左子树和右子树的叶子节点个数相加，最终返回值就是叶子节点的个数。

 2.3 第k层节点个数

         在前两个的基础上我们再来一个变形，计算第k层节点个数。这道题目不像前两个那要，它需要有控制一下递归的深度。

int BinaryTreeLevelKSize(BTNode* root, int k)

        传入一个k，和根节点，通过k来控制递归的深度。这里我们默认根节点的高度是1。如果遇到NULL就返回0；

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + 
           BinaryTreeLevelKSize(root->right, k - 1);    
}

例如这棵树：

         假设我们要计算第3层节点个数。第一次调用从根开始，k此时等于3，然后开始向下递归第二次调用，传参是k-1，到第二层时k=2，到第三层时，k=1。这里我们需要注意一下两个判断返回的顺序，要先判断当前节点是否为NULL，不为NULL才开始判断k是否为1。

---

总结

         本篇文章主要简单介绍了一下二叉树的链式结构，以及链式结构遍历的特点，通过一些简单的练习帮助大家更快上手二叉树的链式递归。理解并使用好递归的分治，对于后续的学习至关重要，希望这篇文章可以帮到您。最后，感谢阅读！