前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析

递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析

作者头像
鸽芷咕
发布2023-12-25 15:17:26
1520
发布2023-12-25 15:17:26
举报
文章被收录于专栏:C++干货基地C++干货基地
在这里插入图片描述
在这里插入图片描述

🎬 鸽芷咕个人主页 🔥 个人专栏: 《linux深造日志》 《高效算法》

⛺️生活的理想,就是为了理想的生活!


文章目录
  • 一、二叉树的遍历
    • 1.1 链式结构二叉树的创建
    • 1.1 二叉树结构图
  • 二、 前序遍历
    • 代码演示:
    • 2.1 前序遍历递归展开图
  • 三、中序遍历
    • 代码演示:
  • 四、后序遍历
    • 代码演示:
  • 五、二叉树的层序遍历
    • 5.1 层序遍历的思想
  • 📝文章结语:

一、二叉树的遍历

学习二叉树链式结构,最简单的方式就是遍历。所谓 二叉树遍历(Traversal) 是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个结点只操作一次

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历

  1. 前序遍历( Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
  2. 中序遍历( Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
  3. 后序遍历( Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后

访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

1.1 链式结构二叉树的创建

这里只是模拟创建一下链式二叉树真正的结构并不是这样创建的:

📚 代码演示:

代码语言:javascript
复制
#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//创建节点
BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc file");
		exit(-1);
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

int main()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;


	PreOrder(node1);

	return 0;
}

1.1 二叉树结构图

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

二、 前序遍历

前序遍历( Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

  • 也就是先访问堆顶然后再访问左子树 (但是要保证每个子树都是这样遍历的)
  • 而这个情况用递归在合适不过了,简直就是非常的简单。大家看下这段代码看看理解嘛?

代码演示:

代码语言:javascript
复制
//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
		return;

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

是不是非常震惊,只需要几行代买就解决前序遍历的问题,这就是递归思想

  • 大问题化简成递归小问题

🍹递归的技巧

大问题转化为子问题 以及递归的结束条件

2.1 前序遍历递归展开图

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

三、中序遍历

有了前序遍历的经验我们接下来中序遍历简直就是 直接秒杀

  • 直接照猫画虎就好了

代码演示:

代码语言:javascript
复制
//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
		return;

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

四、后序遍历

代码演示:

代码语言:javascript
复制
//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
		return;

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

五、二叉树的层序遍历

层序遍历就是从所在二叉树的根结点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点.

  • 以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
在这里插入图片描述
在这里插入图片描述

5.1 层序遍历的思想

层序遍历大家看到一层一层遍历不知道对,我们前面学的数据结构 队列 是否有想法也是和层序一样:

  • 从跟进去然后是左右子树,子树又是左右子树
  • 每次把根 打印出来就把他的子树带进去 然后删除跟
  • 这样是不是就是前一层带后一层的子树了

📚 代码演示:

代码语言:javascript
复制
// 层序遍历
void LevelOrder(BTNode* root)
{
	Que q;
	QueueInit(&q);

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

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		if(front->left)
			QueuePush(&q, front->left);

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

		QueuePop(&q);
	}
}

📝文章结语:

☁️ 把本章的内容全部掌握,铁汁们就可以熟练应用switch语句啦! 看到这里了还不给博主扣个: ⛳️ 点赞🍹收藏 ⭐️ 关注 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要! 你们的点赞就是博主更新最大的动力! 有问题可以评论或者私信呢秒回哦。

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-12-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 一、二叉树的遍历
    • 1.1 链式结构二叉树的创建
      • 1.1 二叉树结构图
      • 二、 前序遍历
        • 代码演示:
          • 2.1 前序遍历递归展开图
          • 三、中序遍历
            • 代码演示:
            • 四、后序遍历
              • 代码演示:
              • 五、二叉树的层序遍历
                • 5.1 层序遍历的思想
                • 📝文章结语:
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档