当前位置: 首页 > news >正文

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


在这里插入图片描述

🎬 鸽芷咕:个人主页

 🔥 个人专栏: 《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 链式结构二叉树的创建

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

📚 代码演示:

#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 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

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

代码演示:

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL)return;printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

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

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

🍹递归的技巧

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

2.1 前序遍历递归展开图

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

三、中序遍历

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

  • 直接照猫画虎就好了

代码演示:

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

四、后序遍历

代码演示:


//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL)return;PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

五、二叉树的层序遍历

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

  • 以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

在这里插入图片描述

5.1 层序遍历的思想

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

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

📚 代码演示:

// 层序遍历
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语句啦!
看到这里了还不给博主扣个:
⛳️ 点赞🍹收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。
在这里插入图片描述

相关文章:

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

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《linux深造日志》 《高效算法》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 一、二叉树的遍历1.1 链式结构二叉树的创建1.1 二叉树结构图 二、 前序遍历代码演示&#xff1a;2.1 前序遍历递…...

WebGL开发数字孪生项目

WebGL&#xff08;Web Graphics Library&#xff09;是一种用于在Web浏览器中渲染交互式3D图形的JavaScript API。虽然WebGL本身并不是一个数字孪生开发框架&#xff0c;但它提供了强大的图形渲染功能&#xff0c;可以用于开发与数字孪生相关的项目。以下是一些可以使用WebGL开…...

【51单片机系列】C51中的中断系统扩展实验

本文是关于51单片机中断系统的扩展实验。 文章目录 一、 扩展实验一&#xff1a;使用外部中断0控制蜂鸣器&#xff0c;外部中断1控制直流电机二、扩展实验二&#xff1a;修改定时器初值&#xff0c;设定3秒钟的定时时间让LED模块闪烁三、扩展实验三&#xff1a;使用定时器1和数…...

Poi实现复杂Excel导出,理解POI操作Excel思路!!!

前言 对于简单excel报表导出&#xff0c;有很多简单的工具如easypoi&#xff0c;而且现在网上已经有很多工具类整合easypoi使用起来非常方便。但是简单的弊端往往无法适配一些负责场景&#xff0c;而我们实际生产中面临的都是客户自定以的一个负责报表导出&#xff0c;这是利用…...

关于 jsconfig.json 文件在导入文件路径提示方面

前文&#xff1a;以前我弄不清 jsconfig.json 文件的作用是什么&#xff0c;只觉得 tsconfig.json 文件是用来 ts 编译的配置项&#xff0c;js 又不用编译为什么会需要 jsconfig.json 文件。搬了这么久的砖&#xff0c;也算是有所心得&#xff0c;今日记下以备不时之需。 jsco…...

验证码:防范官网恶意爬虫攻击,保障用户隐私安全

网站需要采取措施防止非法注册和登录&#xff0c;验证码是有效的防护措施之一。攻击者通常会使用自动化工具批量注册网站账号&#xff0c;以进行垃圾邮件发送、刷量等恶意活动。验证码可以有效阻止这些自动化工具&#xff0c;有效防止恶意程序或人员批量注册和登录网站。恶意程…...

python学习笔记--异常捕获

异常场景 numinput("input you number:") n9000 try:resultn/int(num)print({} 除以num 结果为{}.format(n,result)) except ZeroDivisionError as err:print("0不可以作为除数&#xff0c;出现报错{}".format(err)) except ValueError as err:print(&quo…...

ChatGPT如何计算token数?

GPT 不是适用于某一门语言的大型语言模型&#xff0c;它适用于几乎所有流行的自然语言。所以 GPT 的 token 需要 兼容 几乎人类的所有自然语言&#xff0c;那意味着 GPT 有一个非常全的 token 词汇表&#xff0c;它能表达出所有人类的自然语言。如何实现这个目的呢&#xff1f;…...

页面菜单,通过get请求一个url后,跳转另外一个页面,+丢失问题

业务场景描述&#xff1a; 在A系统&#xff0c;菜单点击跳B系统这个操作。 A系统菜单是get请求到B系统的一个缓冲页面&#xff0c;然后这个缓冲页面获取到url中的accessToken后&#xff0c;在这个页面中通过post请求后端接口。 问题描述&#xff1a; 当accessToken中包含了…...

高并发场景下的延时双删

基本介绍 "延时双删"是一种在并发编程中使用的技术&#xff0c;用于处理缓存和数据库之间的数据一致性问题。在高并发的场景下&#xff0c;这种方法特别有用。下面是对延时双删的详细介绍&#xff1a; 基本概念&#xff1a; 缓存与数据库的不一致&#xff1a;在并发…...

log4js-node在nodejs项目中的使用示例

在Node.js项目中使用log4js-node模块可以帮助你记录日志。以下是一个简单的示例&#xff0c;演示了如何在Node.js项目中使用log4js-node模块&#xff1a; 首先&#xff0c;你需要安装log4js-node模块。在终端中执行以下命令&#xff1a; npm install log4js 接下来&#xff…...

Java_集合进阶(Collection和List系列)

一、集合概述和分类 1.1 集合的分类 已经学习过了ArrayList集合&#xff0c;但是除了ArrayList集合&#xff0c;Java还提供了很多种其他的集合&#xff0c;如下图所示&#xff1a; 我想你的第一感觉是这些集合好多呀&#xff01;但是&#xff0c;我们学习时会对这些集合进行…...

QT GUI代码大全(MainWindow, QFile, QPainter, QGraphicsItem/Scene/View)

文章目录 窗口设置QMainWindow类 按钮和菜单QMenuBar类QMenu类QAction类 文件交互QFileDialog类QFileInfo类QFile类QTextStream 绘图QPixmap类QPainter类QBrush类QPen类QPainterPath类 游戏场景QGraphicsItem类QGraphicsScene类QGraphicsView类 窗口设置 QMainWindow类 QMainW…...

C# Onnx Yolov8 Detect 物体检测 多张图片同时推理

目录 效果 模型信息 项目 代码 下载 C# Onnx Yolov8 Detect 物体检测 多张图片同时推理 效果 模型信息 Model Properties ------------------------- date&#xff1a;2023-12-18T11:47:29.332397 description&#xff1a;Ultralytics YOLOv8n-detect model trained on …...

学习使用js保留两位小数同时去掉小数末尾多余的00

学习使用js保留两位小数同时去掉小数末尾多余的00 前言去除00方法 前言 let number 50000000;let new_number number / 10000;console.log(formatter-new_number, new_number);return new_number.toFixed(2) 万;会发现整数使用toFixed(2)&#xff0c;之后会有多余的.00 去…...

linux驱动的学习 驱动开发初识

1 设备的概念 在学习驱动和其开发之前&#xff0c;首先要知道所谓驱动&#xff0c;其对象就是设备。 1.1 主设备号&次设备号&#xff1a; 在Linux中&#xff0c;各种设备都以文件的形式存在/dev目录下&#xff0c;称为设备文件。最上层的应用程序可以打开&#xff0c;关…...

Node.js中npm中ws的WebSocket协议的实现

在Node.js中&#xff0c;ws是一个非常有用的模块&#xff0c;它提供了WebSocket协议的实现。WebSocket协议是一种在Web浏览器和服务器之间进行双向通信的协议&#xff0c;它可以使得Web应用程序更加交互式和实时。在本文中&#xff0c;我们将详细介绍npm中ws的内容。 ws是什么…...

PHP HTTPoxy CGI 应用程序漏洞 CVE-2016-5385

HTTPoxy CGI 应用程序漏洞 CVE-2016-5385 已亲自复现 漏洞名称漏洞描述影响版本 漏洞复现环境搭建漏洞利用 修复建议 漏洞名称 漏洞描述 在Oracle Communications BRM 10.x/12.x&#xff08;云软件&#xff09;中发现漏洞。它已经被宣布为关键。此漏洞影响组件用户数据库的未…...

qt-C++笔记之使用QLabel和QPushButton实现一个bool状态的指示灯

qt-C笔记之使用QLabel和QPushButton实现一个bool状态的指示灯 code review! 文章目录 qt-C笔记之使用QLabel和QPushButton实现一个bool状态的指示灯1.QPushButton实现2.QLabel实现2.QLabel实现-对错符号 1.QPushButton实现 运行 代码 #include <QtWidgets>class Ind…...

自动驾驶技术入门平台分享:百度Apollo开放平台9.0全方位升级

目录 平台全方位的升级 全新的架构 工具服务 应用软件&#xff08;场景应用&#xff09; 软件核心 硬件设备 更强的算法能力 9.0版本算法升级总结 更易用的工程框架 Apollo开放平台9.0版本的技术升级为开发者提供了许多显著的好处&#xff0c;特别是对于深度开发需求…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...