当前位置: 首页 > 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;特别是对于深度开发需求…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...