【数据结构】——二叉树的递归实现,看完不再害怕递归

这篇具有很好参考价值的文章主要介绍了【数据结构】——二叉树的递归实现,看完不再害怕递归。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】——二叉树的递归实现,看完不再害怕递归,数据结构,算法

 创作不易,感谢三连加支持?!

一  递归理解

递归无非就是相信它,只有你相信它,你才能写好递归!为什么?请往下看

在进入二叉树的实现之前,我们得先理解一遍递归,可能很多人对于递归感到恐惧或者害怕,有时候还不敢面对,其实大可不必,  递归其实分为两个东西:

1.递归结束的条件

2.递归的子问题

1.递归的结束条件:一遍以题目的题意为主,只要理解题意就会知道结束条件是什么,比如求二叉树的结点个数,那他的结束条件就是没有结点的时候,没有结点,那就返回0就行了

2.递归子问题:在使用递归的过程中可能一个问题可以被分成很多个相同的问题,这些相同的问题也就是子问题,拿上面求二叉树的结点个数这个题目来说,我们要求的就是以根为结点这个树的所有结点个数,那么我们可以分成求根节点左子树和右子树的结点个数,然后左子树和右子树又可以和上面一样继续分开

弄清楚上面这个以后,我们在写递归的时候,可以先想想递归的结束条件是什么,然后先结束条件写上,然后再根据子问题一个一个分解,这个递归过程就完成了。

其实我们大部分对于上面两个点都理解,只不过我们写的时候就是写不出来,这种情况是不是很多人有呢? 往下看,相信看完,你的疑惑会少很多!

那我们还是拿上面的例子来说明吧

求二叉树的结点个数(递归实现)

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)//判断条件
		return 0;
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;//递归
}

上面代码的结束条件很好理解,那么就是后面的递归过程不好理解

    这里的+1是我们递归思想为左子树的结点个数+右子树的结点个数+自己 ,可能还是有点抽象

那么我们不妨 先假设如果只有一个根结点,左右子树都为空,那么返回的就是他自己,也就是1

如果还是比较混乱,那就看看下面的图

【数据结构】——二叉树的递归实现,看完不再害怕递归,数据结构,算法

如果理解了里面的细节,那么我们就看看如果攻破递归 !!

首先判断条件我们肯定第一步直接写,那么我们的下一步就是把每一个递归看作一个黑盒,这个黑盒怎么运作的我们不管(这个是在你理解了递归的细节之后),相信它,它一定可以帮你完成任务,你相信它,它也相信你,比如上面的代码我们可以改成这样

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	int left = BinaryTreeSize(root->_left);//相信它,把它当作一个黑盒,它肯定能帮助你完成你想做的事情
	int right = BinaryTreeSize(root->_right);//和上面一样
	return left + right + 1;//最后把结果返回
}

 这里的黑盒就是我们的递归函数,写完判断条件,那么后面我们希望求出左子树的结点个数和右子树的结点个数,那么我们直接把认为交给这两个黑盒(函数),他们可以帮我们算出来。剩下的我们只需要去把他们的返回值接收就行了,然后把所有的结果一次性返回就ok了,相信看到这里,你应该有点感觉了 

那我们趁热打铁,直接来看二叉树的实现

二  二叉树的实现

1.二叉树的创建和销毁
typedef char BTDataType;//一样的先定义一个树的结构体
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;


//然后对它进行初始化
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
}

创建二叉树可以用递归创建,也可以自己一个结点一个结点的创建
递归创建得先给你一个序列才能创建
这里我们用一个前序递归来创建二叉树

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

这里的’#’号代表空

1.既然是递归那么我们的想法就是先写出结束条件,那是不是当我们遇到空的时候就不用递归下去了,也就是遇到’#‘号我们直接返回就行了

2.第二就是我们是前序遍历,所以我们需要先把根结点弄出来

3.第三步递归去把左右子树全部创建,这里我们就需要用两个黑盒去实现

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)//pi是数组下表
{
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;//遇到空了,下表也要往后面走
		return NULL;
	}
	BTNode* cur = BuyNode(a[*pi]);//不是空,那么我们创建根结点结点
	(*pi)++;//继续往后面走
	cur->_left = BinaryTreeCreate(a, n, pi);//黑盒去创建左子树
	cur->_right = BinaryTreeCreate(a, n, pi);//黑盒去创建右子树
    //完成任务直接返回根结点
	return cur;
}

 那这样我们的二叉树就被创建出来了,其实也不是很难,如果用这个思想去做递归的题目可以轻松不少,因为想的少,前提是前期是理解了递归的过程,不然这样直接去想到后面也会寸步难行

还有一个销毁,销毁我们可不是简单把指针置空就完成任务了,这里也需要递归去实现,和上面的思想一样

先判断结束条件,后面用黑盒去帮你把左右子树销毁,有这个思路,那么写起来就很轻松

void BinaryTreeDestory(BTNode* root)
{
	if (root==NULL)
	{
		return;//直接返回
	}
	BinaryTreeDestory(root->_left);//两个黑盒帮你完成任务
	BinaryTreeDestory(root->_right);
	free(root);//最后别忘记释放
}

那么下面我们就对以上的思想进行一个强化

2.计算二叉树叶子结点的个数

思想:计算叶子结点,那么结束条件肯定也是结点为空就停止,既然是叶子结点,那么肯定是左右子树都为空才是叶子结点,那么后面递归我们就需要用到黑盒去完成

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

 这里没有+1是没有算自己,因为我们是算的左右结点,如果左右结点是叶子结点那么就返回它就行了


3.二叉树第k层节点个数 

 思想:第一还是判断条件,如果结点为空,那么就返回,因为结点为空说明结点个数为0,

第二我们要算第k层的结点个数,我们知道如果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);
}

 注意这里黑盒的参数,k是要一直减小的,因为是越来越靠近第k层的

4. 二叉树查找值为x的结点

一样的我们的黑盒大法

剩下的你们自己说

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)//找到就返回
		return root;
    //黑盒大法
	BTNode*left=BinaryTreeFind(root->_left,x);
	BTNode* right = BinaryTreeFind(root->_right,x);
    //看那个不为空,不为空就返回
	if (left)
		return left;
	if (right)
		return right;
    //有的人会这样写
    //因为要返回的是指针,这里的或判断是bool型只会返回一个0或者1;
    //return  BinaryTreeFind(root->_left,x)||BinaryTreeFind(root->_right,x);
}

 以上就是递归思想的总结和二叉树基本操作和实现,可以试试用上面的思想去做一下二叉树的前序遍历中序遍历和后序遍历,这样思路会更加清晰

 这里着重说一下层序遍历

5.二叉树的层序遍历

这里的就不是用黑盒思想那么简单了,这里的遍历需要用到队列去实现,思想就是先把根结点入队列,然后出队列,然后把左右结点入队列,左结点出队列的时候,把左结点的左左节点和右结点入队列,后面的操作和这里一样,这样也就实现了层序遍历 

【数据结构】——二叉树的递归实现,看完不再害怕递归,数据结构,算法

 图画的不好还请谅解

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);//放头节点

	while (!QueueEmpty(&q))如果队列为空就退出来
	{
		BTNode* front = QueueFront(&q);//出第一个结点
		QueuePop(&q);

		printf("%d ", front->data);

		if(front->left)入左右结点
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}

	printf("\n");

	QueueDestroy(&q);
}
6.判断是否是完全二叉树 

 和上面一样都需要用队列实现,如果要用其他方法那就比较麻烦了,不推荐

这里的思想就是层序遍历,然后出数据,因为完全二叉树是连续的不可能出现左子树为空,右子树不为空的情况,所以如果出的数据为空,那么退出,然后再去遍历,如果有不为空的那么就不是完全二叉树

bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))//和层序遍历一样
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		// 遇到空就退出
		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	// 检查后面的节点有没有非空
	// 有不是空的,不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;如果走到这里就说明是完全二叉树
}

如果看到这里,就请三连支持一下吧,非常感谢!

【数据结构】——二叉树的递归实现,看完不再害怕递归,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-845328.html

到了这里,关于【数据结构】——二叉树的递归实现,看完不再害怕递归的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解

      本篇博客 (上篇) 先带大家学习 递归方式 进行三种遍历, 而在后续的 (下篇) 中将为大家详细讲解非递归的三种遍历方式。 目录 1、二叉树 2、二叉树的递归遍历 2.1、先序遍历 2.2、中序遍历 2.3、后序遍历  二叉树(Binary tree)是树形结构的一个重要类型。许多实际问

    2024年02月08日
    浏览(41)
  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(43)
  • 数据结构与算法学习:二叉树的后序遍历的递归与非递归实现,以及非递归实现中的流程控制的说明。

    需求二叉树: 采用二叉树后序遍历非递归算法。设置一个指针p初始指向树根,p先入栈,而后使得p指向它的左孩子p-firstchild,重复操作,使得每个左孩子都依次入栈,同时初始化一个Treenode*类型的指针 pre,这个指针是后序前驱,这个后序前驱用以区分为已访问过的结点和未

    2023年04月22日
    浏览(47)
  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(51)
  • 【Java数据结构】二叉树的前中后序遍历(递归和非递归)

    二叉树遍历是二叉树的一种重要操作 必须要掌握 二叉树的遍历可以用递归和非递归两种做法来实现 前序遍历的遍历方式是 先根节点 在左节点 在右节点 述这棵树前序遍历的结果是: A B D E C F G 递归的思想就是把问题拆分成一个个小问题来解决 treeNode是一个内部类 具体实现

    2023年04月26日
    浏览(51)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(40)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(54)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(56)
  • 【数据结构】二叉树的实现

    一棵二叉树是结点的一个有限集合,该集合分为两点: 一是为空和二是由一个根节点加上两棵别称为左子树和右子树的二叉树组成从图上看出有2个性质: 二叉树不存在度大于2的结点 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树 对于任意的二叉树都是由以下

    2024年02月02日
    浏览(38)
  • 数据结构:完全二叉树(递归实现)

           如果完全二叉树的深度为h,那么除了第h层外,其他层的节点个数都是满的,第h层的节点都靠左排列。        完全二叉树的编号方法是从上到下,从左到右,根节点为1号节点,设完全二叉树的节点数为sum,某节点编号为i,        当2*i = sum时,有左孩子,其编号为

    2024年01月24日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包