数据结构 | 链式二叉树【递归的终极奥义】

🌳链式二叉树的结构及其声明

在上一节中我们说到了一种数据结构——【】。也看到了一些有关二叉树的基本雏形在本节中我们就来说说有关这种链式二叉树的具体实现以及应用


  • 首先来看看它的结构声明。结构体中有三个成员一个是当前结点的值还有两个是指向当前结点左孩子结点的指针以及指向右孩子结点的指针
typedef int BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* lchild;
	struct BinaryTreeNode* rchild;
}BTNode;
  • 也就是下面这种样子
    在这里插入图片描述

🌳链式二叉树的四种遍历方式

好知道了链式二叉树的基本结构之后我们就要去了解如何去遍历出这棵树。对于链式二叉树的遍历方式有四种我们逐个来讲讲

📕先序遍历先根遍历

规则根——左子树——右子树

  • 首先看一下有关先序遍历的的算法算法解析图【我画了很久的/(ㄒoㄒ)/~~】

在这里插入图片描述

  • 有关先序遍历了解了上面的规则之后可以知道每次取遍历都是【根——左子树——右子树】为什么说每次呢从上图可知有关二叉树的遍历我们要使用递归来实现也及时当访问完根之后去访问左子树这个时候左子树不可以直接访问而是要继续依照【根——左子树——右子树】这种规则去进行一个访问即将【2】当做这一棵子树的根遍历完2之后继续去遍历它的左子树依次类推。。。
  • 因此我们可以将这棵树通过层层递归划分成若干个区域如下图所示
  • 温馨提示颜色有点多可能看不太清楚主要是为了理解递归的区间划分

在这里插入图片描述

  • 了解了这些之后我们就可以轻而易举地写出有关先序遍历的序列了可能你在学校里面写的就只是【1 2 3 4 5 6】这样没错这就是先序序列但是在本文中我要带你彻底搞定出递归的真正含义所以我会将访问的空结点也表示出来也就是NULL

在这里插入图片描述

  • 这么对照着看应该清晰一些了有关二叉树的遍历这一块重要的还是自己理解多画画图后期如果时间我录歌视频再放上来讲解一下

递归算法图解

  • 因为图太大了所以截不下来只能这么看了😢
    在这里插入图片描述

📕中序遍历中根遍历

规则左子树——根——右子树

  • 了解了前序遍历那中序遍历也不下话下。和先序做一个区分
    在这里插入图片描述

📕后序遍历后根遍历

规则左子树——右子树——根

  • 后序遍历也是一样的套路

在这里插入图片描述

📕层次遍历

  • 当然除了前序、中序、后序以外还有一种遍历方法就是层次遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历

在这里插入图片描述

辅助队列思维

  • 对于层序遍历呢它和前中后序不一样只是简单的递归我们要使用到另一个数据结构来进行配合解决那就是【队列】有关这种思路的讲解可以看看我的N叉树的层序遍历或者是在本文的末尾中有关二叉树的面试题汇总中也要层序遍历相关的例题这里就不作过多分析

代码详解

  • 给出代码看看。就是通过层序遍历的模板去套入即可具体思路可看我的题解
/*层序遍历*/
void LevelOrder(BTNode* root)
{
	Qu q;
	QueueInit(&q);
	
	if (root != NULL)		//首先将非空根结点入队
		QueuePush(&q,root);

	while (!QueueEmpty(&q))
	{
		QDataType front = QueueFront(&q);	//首先获取队头结点
		printf("%d ", front->data);			//获取到之后输出打印
		QueuePop(&q);		//将其出队

		//将其左右孩子结点再从队尾入队
		if (front->lchild)
			QueuePush(&q, front->lchild);
		if(front->rchild)
			QueuePush(&q, front->rchild);
	}

	QueueDestroy(&q);
}

🌳链式二叉树进阶算法实现

刚才在初步了解了链式二叉树后学习了四种其遍历方式但是遍历一棵链式二叉树并不是很难在二叉树这一节估计只有1到2分的难度真正难的还在后面呢😵

🍃求树的结点个数——难度系数【⭐⭐】

Way1变量累加法

  • 首先看到要求一棵树的结点个数那我猜你想到的一定是去定义一个变量然后去进行一个递归调用每调用一次count++但是这样的话很明显不可以这一点我们首先得否决在C语言函数的局部变量那一块我们有讲过对于局部变量出了作用域就会销毁因此你对于每一次的递归调用单独建立的栈帧都会存在这个局部变量但是呢在栈帧销毁之后这个变量也就跟着销毁了所以这种办法不可以取
int TreeNodeNum1(BTNode* root)
{
	if (root == NULL)
		return;
	int sz = 0;
	sz++;
	TreeNodeNum1(root->lchild);
	TreeNodeNum1(root->rchild);
	return sz;
}

  • 于是有同学呢又想出一种办法就是将这个变量定义为静态变量因为静态变量是存放在静态区中的不会随着某一个函数的调用结束而销毁因此我们可以这么写
int TreeNodeNum1(BTNode* root)
{
	if (root == NULL)
		return;
	static int sz = 0;
	sz++;
	TreeNodeNum1(root->lchild);
	TreeNodeNum1(root->rchild);
	return sz;
}
  • 可以看到第一次的计算确实是可以计算出来这棵树有6个结点但是在我多调用几次之后结点个数却发生了一个累加这就是静态变量的特点均会在上一次的基础上去进行一个运算无论你是调用其他的什么函数或者是多调用几次那其实可以看到这里就出现BUG了
    我们该如何去进行修改呢
    在这里插入图片描述
  • 其实这一块很简单我们不需要静态变量直接将这个变量放到函数外部作为一个全局变量即可因为函数内部的返回值我们不好控制干脆就不要返回值直接将这个记数的变量定义为全局变量这样就很好控制了
int sz = 0;
void TreeNodeNum1(BTNode* root)
{
	if (root == NULL)
		return;
	sz++;
	TreeNodeNum1(root->lchild);
	TreeNodeNum1(root->rchild);
}
  • 我们再来测试一下。可以看到每次的结点个数算出来均是恒定不变的就是每次在上一次调用完求值之后要将sz重新置为0

在这里插入图片描述


Way2分治递归法

  • 很显然对于上述的这种变量累加法并不能体现出链式二叉树的特性接下去我们使用一种分治递归法去求解这种方法的思路很简单也很好理解
  • 我们始终将一个树分割为三个部分【根】【左子树】【右子树】因此进行一个分块求解然后再加起来就可以了

情景思路分析

这个听起来是很好理解但是递归这种结构的话对于有些同学来说还是比较晦涩难懂的因此我们通过一个特殊的情景来分析一下

  • 疫情结束马上就要返校复工了此时学校需要统计有多多少人会返校于是这件事情就交给副校长去办

  • 假设每个领导最多只能管理两个人现在呢副校长他想要了解到两个院系有多个人那么他就要去询问两个副院长也就是链式二叉树所对应的左右子树那对于副院长呢它想要知道这个院里有多少个人那就需要找到每个班级对应的班主任去询问然而对于班主任呢班级方面的事情他就交给班长去负责统计出班里有多少人返校

  • 当班长搜集完信息后就汇报给班主任班主任再汇报给副院长最后副院长再汇报给副校长。副校长接收到一个副院长的统计汇报后再向另一个副院长去询问返校人数信息这对应的就是先访问完左子树之后再访问右子树最后当另一个副院长也将人数汇报上来之后再加上他自己就是本次返校的人数了【当然这只是假设】

具体的图解如下
在这里插入图片描述

以下是代码

int TreeNodeNum(BTNode* root)
{
	return root == NULL ? 0 :
		TreeNodeNum(root->lchild) + TreeNodeNum(root->rchild) + 1;
}
  • 看到代码这里是使用了一个三目运算符当然你也可以写成if语句判断的形式只是这样写比较简洁一些可以看到就是一个对左子树和右子树的分别递归最后再加上1也就是根节点

以下是递归算法图解

在这里插入图片描述

  • 如果你感觉自己对于链式二叉树的递归这一块不是很清楚的话就像我这样画画递归的图解吧可以有助于对代码的理解因为对于递归这种结构只看代码的话是很难理解的通过画图分析就可以清楚很多
  • 后面的题目也是一样我会带着你画你也可试着自己去画画看就是递归的调用和回调的一个过程注重递归出口就行

🍃求树的叶子结点个数——难度系数【⭐⭐🌙】

警惕空指针❗

  • 会求一棵树中的所有结点数现在我们来进阶一下求解树的叶子结点个数如果不知道什么是叶子结点的话建议看看树和二叉树的基本概念
  • 知道了如何去求解总的结点个数那求叶子结点并不难当然也是使用递归去完成只是每次在递归的时候不要就是左子树和右子树的累加和不要加上自己就行
  • 于是有同学就写了这样的代码我们来看看有什么问题
int TreeLeafSize(BTNode* root)
{
	if (root->lchild == NULL && root->rchild == NULL)
		return 1;		//若是左右孩子均为空则表示只有结点
	return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}
  • 首先从根结点开始左右孩子均不为空则往下递归若是当前结点的孩子结点为空则表示其为叶子结点return 1返回上一级递归完左子树之后再递归右子树从下图可以看出当递归2的左子树之后去递归2的右子树时间就会出现【访问空指针】的异常

在这里插入图片描述

DeBug调试观测

这一块我们一起带VS来调试一下看看

  • 首先看到现在递归进到了2的左子树data值为3其左右孩子均为NULL因为可以断定其为叶子结点因为便返回上一级

在这里插入图片描述

  • 然后可以看到回到结点2了

在这里插入图片描述

  • 继续往右子树进行递归

在这里插入图片描述


  • 那我们该用什么办法去解决呢这个很简单只需要判断一下当前递归进来的结点是否为空也就是【root == NULL】若是空的话就返回即可
  • 所以将代码改为如下
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->lchild == NULL && root->rchild == NULL)
		return 1;		//若是左右孩子均为空则表示只有结点
	return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}
  • 测试一下可以看到这棵树的叶子结点有3个

在这里插入图片描述

🍃求树的高度——难度系数【⭐⭐⭐】

规则明细及思路分析

  • 接下去我们再将难度提升一个档次会求结点个数了现在去求求这棵树的高度是多少。首先我给出计算规则防止大家跑偏

📚规则二叉树高度 = 左子树和右子树中高度大的那个 + 1

  • 知道了规则我们就可以通过画画图来理一下思路。可以看到我给3加了一个右孩子结点。接着从肉眼就可以看出对于根节点1来说其左子树的高度为3右子树的高度为2所以整棵树的高度就为3 + 1 = 4

在这里插入图片描述

错误案例示范——怎么就是不长记性(╯▔皿▔)╯

  • 接下去我们来看一个错误的案例释放这也是很多同学会犯的错误而且会导致很严重的重复计算
  • 可以看到这位同学就是将我们的算法图转化为了代码递归式地去比较左右子树的高度最后找出大的那个 + 1但是呢
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	return TreeHeight(root->lchild) > TreeHeight(root->rchild) ?		
		   TreeHeight(root->lchild) + 1 : TreeHeight(root->rchild) + 1;
}
  • 从运行结果可以看出是可以计算出来的树的高度为4但是呢却存在一个很大的隐患

在这里插入图片描述

  • 为什么这么说呢因为这样的写法在LeetCode上提交是会【超时】的超时是什么是算法设计得过于复杂程序运行的时间过长但是那位同学就说就观光几行代码就算是递归也就只有4高度的树而已最多也就是十几次的递归和回调怎么可能会超时呢
  • 然后我是这么解释的

在这里插入图片描述

  • 这里看下来你应该可以明白了原因就在于递归进去结点的时候比较完左右子树的高度后面将其保存再来这样就会导致上一次结点在求求解高度的时候无法获取其左子树或者右子树的高度因此需要再次递归下去但是其左子树的左子树也没有保存因此也需要再进行一个递归
  • 每往上求解一个结点的高度下面的结点就需要多递归一次随着逐层向上求解下面每一个结点的递归次数就是一个并不是2倍的上升而是一个指数级别甚至阶乘级别的上升这取决于这棵树的深度若是深度越深那递归层数就会越多就会导致什么就会导致栈内存不够然后栈溢出
  • 因此大家应该要认识到这种写法是一种极大地浪费资源那我们应该怎么办呢很简单将每次左右子树递归进去回调后的结果做一个保存即可

正确代码描述【递归算法图解】

  • 所以正确的代码应该想下面这样将当前结点递归进去的后左右子树求出的高度做一个保存然后对他们再进行一个比较。这样就不会出现上述的问题了而且代码看起来还比较简洁
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int LHeight = TreeHeight(root->lchild);
	int	RHeight = TreeHeight(root->rchild);

	return LHeight > RHeight ? LHeight + 1 : RHeight + 1;		//返回左右子树中大的那一个再加上根结点
}

下面是算法图解

  • 图解很大截不了图可以看看我的架构然后自己试着画画图

在这里插入图片描述

🍃求第K层有多少个结点——难度系数【⭐⭐⭐🌙】

思路分析及规则明细

  • 好会求结点数会求高度对于树的层次也有了一个概念后我们就要再进一步去考虑更加复杂写的问题那就是去求解第K层有多少个结点这个我们应该怎么去求解呢一起来画画图分析一下吧
  • 假设要求解的是【第三层有多少结点个数
    在这里插入图片描述
  • 从上图你应该可以看出我是什么意思了这也需要一种递归的思维对于根节点①来说是第三层但是对于②和④来说确实第二层而对于③、⑤、⑥来说是第一层只需要按照相对位置往下走就可以了。因此我们可以得出这样运算规则

规则
📚当k > 1 时第k层的结点个数为其左孩子的第k - 1层 + 其右孩子的第k - 1层结点个数
📚当k == 1时return 1

代码描述

  • 所以很明确根据思路就可以写出如下代码
  • 除了判断k之外别忘了每次都要判断一个传进来的根结点是否为空放置访问空指针。然后对于左右孩子的递归就是【k - 1】每往其左右孩子递归一次k就-1递归出口就是当【k == 1】时return 1即可
int TreeNodeNumK(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeNodeNumK(root->lchild, k - 1)
		+ TreeNodeNumK(root->rchild, k - 1);
}
  • 这么看代码一定也会很抽象吧那就试着自己对着代码去画画算法图吧以下是我的分析过程

在这里插入图片描述

🍃查找指定结点——难度系数【⭐⭐⭐】

  • 学会了【统计】我们来学学【查找】

错误案例示范——有些人走着走着就散了🚶‍

  • 首先我们来看看一位同学的错误代码
/*查找指定结点*/
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (!root)			
		return NULL;
	if (root->data == x)
		return root;		//若根节点就是所要查找的结点则直接返回
		
	TreeFind(root->lchild, x);
	TreeFind(root->rchild, x);
	//没有理解清楚递归的返回过程
}
  • 在学习了上面的统计结点个数、叶子结点个数以及第K层的结点个数虽然代码并不复杂而且我带大家画了递归展开图所以有些同学就认为对于二叉树的题目都可以这么去写
  • 乍一看上面的代码其实没有什么问题首先判断递归传入的根是否为空然后再判断其是否就为我们要查找的结点若都不满足就继续递归其左右子树但是呢仔细看可以看出来每次递归下去再回调回来的值有谁去接收呢所以最后只会是返回一个随机值

在这里插入图片描述

  • 可以看到在查找完之后去打印出来的就是一个空值因为根本就没有拿一个变量去接收一下所以在半路就丢了

在这里插入图片描述

正确代码展示及分析

  • 这里其实和前面求解二叉树的高度是一样的在递归进去左右子树再返回回来时要拿一个变量去接收一下才行这样才能保证查找到那个正确的值而不是在半路就丢了走散了
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	/*
	* if (root == NULL)和if(!root)是等价的
	* if(root) - 结点是存在的
	* if(!root) - 结点是不存在的 --> 空的
	* if (root == NULL) -->空的
	* if (root != NULL) -->非空
	*/
	//if (root == NULL)
	//	return NULL;
	if (!root)			
		return NULL;
	if (root->data == x)
		return root;		//若根节点就是所要查找的结点则直接返回
	/*
	* 要保存下当前查找的结点否则递归回来没有接收返回的只会是一个空值或者随机值
	*/
	BTNode* ret1 = TreeFind(root->lchild, x);
	if (ret1)
		return ret1;		//表明在左子树中找到了该结点返回
	BTNode* ret2 = TreeFind(root->rchild, x);
	if (ret2)
		return ret2;		//表明在右子树中找到了该结点返回
	
	return NULL;			//左右子树均没有找到返回NULL
}
  • 可以看到这里在递归左右子树的时候我分别都拿了一个指向结点的指针接收了一下然后在递归回调的时候就可以接收到找到的这个返回值了接着再去判断一下其是否存在若是存在就将其return即可
  • 我们来跟着画一下它的递归算法展开图

在这里插入图片描述

  • 可以看到有返回值去接收了就不知道在半路丢失可以一层一层地返回回来最后把结果给到外界的调用
  • 我们再来看看运行结果

在这里插入图片描述


🍃判断二叉树是否为完全二叉树——难度系数【⭐⭐⭐⭐】

接下来继续做一个进阶在树和二叉树的基本概念中我讲到了两种特殊的二叉树满二叉树和完全二叉树所以在这里我们要判断一棵树是否为完全二叉树该如何去做呢

概念分析及规则明细

  • 我们知道对于完全二叉树来说最下面一层的叶子都依次排列在改成最左边的位置上也就是中间不可以或缺或者说是空出一个这样的话就不能算是完全二叉树。下面是例图📃

在这里插入图片描述

  • 所以我们就可以得出运算规则

📚若遇到的空结点后还有非空的结点则表明其不为完全二叉树
📚若遇到的空结点后均为空则表示其为完全二叉树

  • 有了这个运算规则之后呢我们就可以去将其转化为代码了这个逻辑是要嵌套在二叉树的层序遍历中的层序遍历这一块的题目我也是有做过相关的题解而且在下面模块的OJ算法题实训中也有讲到可以去看看直接套用模板即可

代码描述及分析

首先给出代码

/*判断二叉树是否为完全二叉树*/
bool TreeComplete(BTNode* root)
{
	Qu qu;
	QueueInit(&qu);

	if (root)
		QueuePush(&qu, root);		//首选入队队头结点

	while (!QueueEmpty(&qu))
	{
		QDataType front = QueueFront(&qu);
		QueuePop(&qu);

		//判断当前队列结点是否为空
		if (front == NULL)
			break;		//若为空则break跳出循环进行判断
		else
		{
			//若不为空则入队其左右孩子
			QueuePush(&qu, front->lchild);
			QueuePush(&qu, front->rchild);
		}
	}

	//此处判断是否为完全二叉树
	/*
	* 1.若遇到的空结点后还有非空的结点则表明若遇到的空结点后均为空则表示其为完全二叉树其不为完全二叉树
	* 2.
	*/
	if (!QueueEmpty(&qu))
	{			
		QDataType front = QueueFront(&qu);
		if (front != NULL)
		{				//若是在队列中取到了非空的结点则表示不为完全二叉树
			QueueDestroy(&qu);		//提前return要记得销毁队列
			return false;
		}

	}
	return true;
	QueueDestroy(&qu);
}
  • 看到上述代码应该可以知道为什么这个算法可以被赋四颗星了吧相比其他进阶算法来说确实需要一些二叉树的基本能力
  • 但是呢有了我给你的这个思路之后再去写代码其实也不是什么难事我们只需要在一些地方做一个修改就可以了。首先第一个地方就是在刚获取到当前队头结点的时候此时不要着急去入左右孩子结点需要做一些改动而且对于层序遍历所涉及的OJ题基本也是在这个地方去做一个改动
  • 什么时候跳出循环呢 但是在内层进行判断肯定不行最好做一个分离外层判断那也就需要使用到【break】跳出当前的循环那要什么时候跳出呢刚才看了那张图应该可以知道有一个转折点应该是在层序遍历到NULL的时候此时我们应该跳出循环
  • 那要怎么判断呢 回忆完全二叉树的定义可以知道但凡你遇到NULL了之后就相等于是断层了后面若是再出现有结点那就说明不是完全二叉树我们可以根据这点去判断队列是否为空然后知晓后面是否还有结点需要遍历。这个就是跳出循环后的判断逻辑了

注意在判断出不为完全二叉树后提前【return false】了就需要将队列销毁否则会造成内存泄漏


  • 再来看看运行结果

在这里插入图片描述
在这里插入图片描述

🍃销毁二叉树

思路分析

  • 对一棵二叉树进行了一系列的操作之后我们要去肯定要去销毁这棵二叉树否则也会造成内存泄漏
  • 但是这要怎么去完成呢从根节点开始往下销毁吗设想你现将根节点销毁了那左右子树不是找不到了就和你删除链表结点是一个道理改变了这个指向原本的指向也就是找不到了
  • 因此我们不应该从根结点开始应该先从左右子树开始那对于左子树来说它又可以作为一个根结点依旧是需要先去销毁其左右子树右子树也是一样因此这就又成了一个递归的问题。而且是要销毁掉左右子树之后再去销毁根结点所以这就相当于是一种后序遍历的思维

在这里插入图片描述

代码描述

  • 来展示一下代码
/*销毁二叉树*/
void DestroyTree(BTNode* root)
{
	if (root == NULL)		//if(!root)
		return;

	DestroyTree(root->lchild);
	DestroyTree(root->rchild);

	free(root);
}
  • 代码很简洁当还没遍历到空树时就一直递归遍历其左子树然后进行销毁接着return回去销毁右子树最后再销毁根结点
  • 但是这里有一点要注意的是对于内部的销毁是无法因此外部变化的这个相信你在看了本文后也有所领会因此我们要在外界函数调用完后再对指向根节点的指针置空防治野指针
DestroyTree(n1);
n1 = NULL;		//内部置空外部也要置空【形参改变不影响实参】

🌳链式二叉树OJ算法题实训

本模块请于我另一个专栏【LeetCode算法笔记】进行观看

也可直接点击此链接

🌳总结与提炼

学习完了链式二叉树我们来总结一下所学习的知识点📖

  • 首先我们了解了这种链式二叉树的数据结构知道了它由左右孩子以及结点值组成
  • 接下去了解有关链式二叉树的四种遍历方式分别是先序、中序、后序以及层次遍历这里主要是使用递归的形式去求解非递归的思路我们后续在【数据结构进阶】中再做讲解
  • 然后呢我们在了解了基本的遍历算法后对二叉树有了一些进阶算法的训练分别是【求解树的结点个数】、【叶子结点个数】、【高度】、【第K层结点个数】、【查找指定结点】、【判断是否为完全二叉树以及销毁】等有了这些进阶训练后对于二叉树这种数据结构也有了进一步地了解
  • 接下去就是实战训练我们通过十余道OJ算法题的训练做了一些有关二叉树的实际应用对二叉树更上一个台阶
  • 二叉树这种数据结构无论是在笔试、面试或者考研中都是非常重要的作为读者的你是否有感受到呢

以上就是本文所要描述的所有内容感谢您对本文的观看如有疑问请于评论区留言或者私信我都可以🍀

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6