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

二叉树的前序、中序和后序遍历：详解与实现

news 来源：原创 2025/6/13 17:17:20

1. 前序遍历（Pre-order Traversal）

1.1 定义

前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

1.2 访问顺序

对于任意节点：

访问根节点。
递归遍历左子树。
递归遍历右子树。

1.3 示例

假设我们有以下二叉树：

        A/ \B   C/ \   \D   E   F

前序遍历的结果是：A -> B -> D -> E -> C -> F。

1.4 递归实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}public class BinaryTree {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.add(root.val); // 访问根节点res.addAll(preorderTraversal(root.left)); // 递归遍历左子树res.addAll(preorderTraversal(root.right)); // 递归遍历右子树return res;}
}

1.5 应用场景

构建表达式树：前序遍历可以生成表达式的前缀表达式。
复制二叉树：通过前序遍历可以复制一个二叉树。
序列化二叉树：前序遍历可以用于将二叉树序列化为一个字符串。

2. 中序遍历（In-order Traversal）

2.1 定义

中序遍历的顺序是：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

2.2 访问顺序

对于任意节点：

递归遍历左子树。
访问根节点。
递归遍历右子树。

2.3 示例

假设我们有以下二叉树：

        A/ \B   C/ \   \D   E   F

中序遍历的结果是：D -> B -> E -> A -> C -> F。

2.4 递归实现

public class BinaryTree {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.addAll(inorderTraversal(root.left)); // 递归遍历左子树res.add(root.val); // 访问根节点res.addAll(inorderTraversal(root.right)); // 递归遍历右子树return res;}
}

2.5 应用场景

二叉搜索树（BST）：中序遍历可以生成一个递增的有序序列。
表达式树：中序遍历可以生成表达式的中缀表达式。

3. 后序遍历（Post-order Traversal）

3.1 定义

后序遍历的顺序是：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

3.2 访问顺序

对于任意节点：

递归遍历左子树。
递归遍历右子树。
访问根节点。

3.3 示例

假设我们有以下二叉树：

        A/ \B   C/ \   \D   E   F

后序遍历的结果是：D -> E -> B -> F -> C -> A。

3.4 递归实现

public class BinaryTree {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.addAll(postorderTraversal(root.left)); // 递归遍历左子树res.addAll(postorderTraversal(root.right)); // 递归遍历右子树res.add(root.val); // 访问根节点return res;}
}

3.5 应用场景

删除二叉树：后序遍历可以确保在删除根节点之前先删除其子节点。
表达式树：后序遍历可以生成表达式的后缀表达式。

4. 总结

遍历方式	访问顺序	应用场景
前序遍历	根 -> 左 -> 右	构建表达式树、复制二叉树、序列化二叉树
中序遍历	左 -> 根 -> 右	生成有序序列、表达式树的中缀表达式
后序遍历	左 -> 右 -> 根	删除二叉树、表达式树的后缀表达式

4.1 递归实现的通用模板

public class BinaryTree {public List<Integer> traversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}// 递归遍历左子树res.addAll(traversal(root.left));// 访问根节点（根据遍历方式调整位置）res.add(root.val);// 递归遍历右子树res.addAll(traversal(root.right));return res;}
}

二叉树的前序、中序和后序遍历：详解与实现

1. 前序遍历（Pre-order Traversal） 1.1 定义前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。 1.2 访问顺序对于任意节点： 访问根节点。递归遍历左子树。递归遍历右子…...

编程日记 2025/5/24 19:24:49

5、Rag基础：RAG 专题

RAG 简介什么是检索增强生成？检索增强生成（RAG）是指对大型语言模型输出进行优化，使其能够在生成响应之前引用训练数据来源之外的权威知识库。大型语言模型（LLM）用海量数据进行训练，使用数十亿个参数为回答问题、翻译语言和完成句子等任务生成原始输出。在 LLM 本就强…...

编程日记 2025/5/24 5:03:34

FISCO BCOS 智能合约开发详解

一、FISCO BCOS 智能合约开发概览 FISCO BCOS 是一个国产开源联盟链平台，支持两种类型的智能合约：FISCO BCOS Documentation Solidity 合约：与以太坊兼容，使用 Solidity 语言编写，适用于灵活的业务逻辑开发。预…...

编程日记 2025/5/29 13:36:30

Linux操作系统从入门到实战（四）Linux基础指令（下）

Linux操作系统从入门到实战（四）Linux基础指令（下） 前言一、date 指令二、cal 指令三、find 指令四、which 指令五、whereis 指令六、alias 指令七、grep 指令八、zip/unzip 指令九、tar 指令（重要）十、bc 指…...

编程日记 2025/6/3 0:12:19

使用 LLM助手进行 Python 数据可视化

在数据科学中，数据可视化是一项至关重要的任务，旨在揭示数据背后的模式和洞察，并向观众传达这些信息。然而，在编程语言（如 Python）中创建有洞察力的图表有时可能会耗时且复杂。本文介绍了一种借助 AI 助手&…...

编程日记 2025/5/28 7:42:03

#搭建gitlab docker pull gitlab/gitlab-ce docker run -d\--hostname localhost \-p 443:443 -p 80:80 -p 2222:22 \--name gitlab \-v /myproject/gitlab/config:/etc/gitlab \-v /myproject/gitlab/logs:/var/log/gitlab \-v /myproject/gitlab/data:/var/opt/gitlab \gitla…...

编程日记 2025/5/27 6:39:20

Python3:面向对象编程

这里写目录标题 🧩 面向对象编程：让代码化身为积木世界一、核心概念：类与对象二、四大基石：面向对象的核心特性1️⃣ 封装(Encapsulation)：包装复杂性，提供简单接口2️⃣ 继承(Inheritance)：站在…...

编程日记 2025/5/29 21:44:33

数据可视化 —— 饼图

一、饼图的所有常用使用场景饼图是一种直观展示数据占比关系的图表，适用于以下常见场景： 1. 市场与商业分析市场份额：展示不同品牌/产品在市场中的占有率。收入构成：分析公司各业务线或产品的收入占比。客户分布&#xff1…...

编程日记 2025/5/18 10:52:11

OpenLayers WebGL与3D渲染（进阶一）

1. WebGL概述 WebGL是一种JavaScript API，它基于OpenGL ES 2.0/3.0标准，允许在不使用插件的情况下在兼容的Web浏览器中呈现高性能的交互式3D和2D图形。在地理信息系统(GIS)领域，WebGL为地图渲染和空间数据可视化提供了强大的性能支持。 1.1…...

编程日记 2025/5/30 16:32:24

ARP协议（地址解析协议）

ARP协议是用来把IP地址转换成MAC地址的。因为在局域网里，真正通信靠的是MAC地址，但我们平时只知道目标的IP地址，所以需要一个办法把IP地址变成MAC地址 —— 这个过程就是靠ARP完成的。举个超简单的例子： 你电脑要发数据给192.1…...

编程日记 2025/5/25 22:33:21

深度学习常见框架：TensorFlow 与 PyTorch 简介与对比

🐇明明跟你说过：个人主页 🏅个人专栏：《深度探秘：AI界的007》 🏅 🔖行路有良友，便是天堂🔖 目录一、引言 1、为什么需要深度学习框架？ 2、框架的发展背…...

编程日记 2025/5/29 12:37:34

iOS 类与对象底层原理

iOS 类与对象底层原理文章目录 iOS 类与对象底层原理探索对象本质objc_setProperty 源码cls与类的关联原理联合体isa的类型isa_t 原理探索initIsa方法通过setClass方法中的shiftcls来验证绑定的一个流程通过 isa & ISA_MSAK通过object_getClass通过位运算类&类的结构…...

编程日记 2025/5/28 16:23:44

Babel、core-js、Loader之间的关系和作用全解析

在现代前端开发中，Babel、polyfill（如 core-js）和 Loader 是非常常见又容易混淆的几个概念。为了彻底搞明白它们的作用、关系和使用方法，下面一篇文章详细梳理。一、Babel的作用 Babel 是一个 JavaScript 的编译器，主…...

编程日记 2025/4/28 6:03:31

总线位宽不变，有效数据位宽变化的缓存方案

总线位宽不变，有效数据位宽变化的缓存方案譬如总线位宽为64bit，但是有时候只有高32bit有效，有时只有低32bit有效，有时64bit都有效。总线上收到的数据要先缓存到FIFO中，那么这个FIFO的宽度和深度如何设置呢&#xff1…...

编程日记 2025/5/27 6:02:52

若依脱敏功能升级：接口返回想脱就脱，想不脱就不脱（实现灵活可控制的数据脱敏）

若依原生框架中的脱敏功能不够灵活（默认超级管理员不脱敏，其他则脱敏）。有时候，我们有些接口想要脱敏，但是有些接口又不想脱敏。（例如列表查询的时候脱敏。修改的时候，不想数据脱敏&#xff0…...

编程日记 2025/5/28 7:50:23

【Azure Redis 缓存】在Azure Redis中，如何限制只允许Azure App Service访问？

问题描述在Azure Redis服务中，如何实现只允许Azure App Service访问呢？ 问题解答 Azure Redis 开启防火墙的功能，并在防火墙中添加上App Service的出口IP地址即可。两步即可实现此目的！ 1）查询 App Service 的出口IP…...

编程日记 2025/5/31 5:57:58

如何解决无训练数据问题：一种更为智能化的解决方案

手动标注数据真的很费时间，而且买数据集又贵得要命，还不一定能完全符合你的需求。但这里有个令人兴奋的好消息，为啥不用 AI 来解决这个问题呢？别再依赖传统方法了，你可以用像 LLM（大型语言模型）和图像生成器这样的 AI 工具，为你的特定目标创建合成训练数据。如今有那…...

编程日记 2025/5/27 16:58:08

AI 应用同质化：一场看不见的资源 “吞噬战”

大家好，我是涛涛，今天聊聊令人担心的事情。一、同质化的“繁荣”背后当ChatGPT在2022年掀起全球AI热潮时，中国互联网行业迅速进入“All in AI”模式。根据艾瑞咨询数据，2023年国内AI应用市场新增注册企业超2.3万家&#xff0c…...

编程日记 2025/5/22 20:38:11

Java + Spring Boot + MyBatis获取以及持久化sql语句的方法

在Java的Spring Boot项目中结合MyBatis获取实际执行的SQL语句，可以通过以下几种方法实现： 方法一：配置MyBatis日志级别通过调整日志级别，MyBatis会输出执行的SQL语句及参数，适用于快速调试。修改application.prope…...

编程日记 2025/6/1 17:57:01

「浏览器即OS」：WebVM技术栈如何用Wasm字节码重构冯·诺依曼体系？

一、冯诺依曼架构的维度坍塌 1. 传统计算模型的能量耗散浏览器执行效率瓶颈分析： 操作x86指令周期Wasm指令周期能效比提升矩阵乘法3894.2x内存访问1234x系统调用120012100x 二、WebVM的量子纠缠架构 1. 浏览器内核的重构 // 基于WASI的系统调用处理 #[no_mangl…...

编程日记 2025/5/27 4:56:40

Vue3项目目录结构规范建议

以下是一个推荐的 Vue 3 项目目录结构规范，适用于中大型项目并遵循最佳实践： 基础目录结构 bash src/ ├─ assets/ # 静态资源 │ ├─ images/ # 图片文件 │ ├─ fonts/ # 字体文件 │ └─ styles/ …...

编程日记 2025/5/24 2:02:00

【计算机视觉】CV实战项目- Four-Flower：基于TensorFlow的花朵分类实战指南

深度解析Four-Flower：基于TensorFlow的花朵分类实战指南项目概述与技术背景技术栈组成完整实战流程环境配置1. 基础环境安装2. 项目环境搭建3. 环境验证数据准备模型架构解析训练过程优化1. 训练配置2. 关键参数建议3. 训练监控常见问题与解决方案1. 内存不足错…...

编程日记 2025/5/18 10:40:30

4.27 JavaScript核心语法+事件监听

JavaScript负责网页的行为（交互行为） JS基本语法： 引用方式变量&常量&数据类型： alert()标签输出弹出框，如以上代码会输出true。函数： 自定义对象: 属性方法行为 JS中的全局变量是window。 js…...

编程日记 2025/5/31 7:24:06

于键值（KV）的表

基于键值（KV）的表将行编码为键值（KVs） 索引查询：点查询和范围查询在关系型数据库中，数据被建模为由行和列组成的二维表。用户通过SQL表达他们的意图，而数据库则神奇地提供结果。不那么神奇的…...

编程日记 2025/5/31 11:51:41

Matlab算例运行

1. 使用终端命令运行算例： 2. 如果点击Run 按钮就是会一直报错，所以直接改成终端运行算例...

编程日记 2025/5/29 13:31:12

package.json script 中的 prepare 脚本的作用是什么

在 package.json 的 scripts 中，prepare 脚本是一个特殊的生命周期脚本，主要作用和执行时机如下： prepare 脚本的作用和执行时机执行时机： 在执行 npm publish 命令之前运行。在执行不带参数的 npm install 命令时运行&#xff…...

编程日记 2025/5/29 12:48:29

图论---最大流（Dinic）

最大流一定是阻塞流，阻塞流不一定是最大流。阻塞流---从起点到终点的管道已经阻塞了。时间复杂度： 一般情况：O(n2m)O(n2m)（但实际运行效率较高，尤其在稀疏图上）。使用当前弧优化后，效率接近…...

编程日记 2025/5/28 11:56:47

FastAPI系列06：FastAPI响应（Response）

FastAPI响应（Response） 1、Response入门2、Response基本操作设置响应体（返回数据）设置状态码设置响应头设置 Cookies 3、响应模型 response_model4、响应类型 response_classResponse派生类自定义response_class 在“FastAPI系列0…...

编程日记 2025/5/26 20:29:36

双目RealSense系统配置rs_camera.launch----实现D435i自制rosbag数据集到离线场景的slam建图

引言 Intel RealSense系列相机因其出色的深度感知能力和灵活的配置选项，在机器视觉与应用中得到广泛应用。大家在后期的slam学习中，无论是对算法本身的性能要求还是实验的泛化性都有一定的要求，那么公开的数据集如kitti、tum、Eourc不能满足…...

编程日记 2025/5/19 19:40:00

【MCP-2】MCP是什么，利用智普大模型在MaxKB中调用自己开发的MCP服务

在上一篇【MCP-1】MCP是什么，从DEMO入手文章中我们介绍了MCP是什么、他能干啥，以及简单的Demo示例等，这篇文章我们使用MaxKB这个工具，利用智普大模型，看看MCP到底怎么用。创建SSE协议的MCP服务在上篇文章中的Demo是…...

编程日记 2025/5/28 15:04:48

Allegro23.1新功能之如何单独关闭铜皮显示效果操作指导

Allegro23.1新功能之如何单独关闭铜皮显示效果操作指导 Allegro升级到了23.1的时候，支持单独关闭铜皮显示，如下图如何仅关闭shape的显示，单独显示线，具体操作如下点击setup...

编程日记 2025/6/1 18:21:48

《从分遗产说起：JS 原型与继承详解》

“天天开心就好” 先来讲讲概念： 原型（Prototype） 什么是原型？ 原型是 JavaScript 中实现对象间共享属性和方法的机制。每个 JavaScript 对象（除了 null）都有一个内部链接指向另一个对象，这…...

编程日记 2025/5/22 7:11:30

【Part 2安卓原生360°VR播放器开发实战】第二节｜基于等距圆柱投影方式实现全景视频渲染

《VR 360全景视频开发》专栏将带你深入探索从全景视频制作到Unity眼镜端应用开发的全流程技术。专栏内容涵盖安卓原生VR播放器开发、Unity VR视频渲染与手势交互、360全景视频制作与优化，以及高分辨率视频性能优化等实战技巧。 📝 希望通过这个专栏&am…...

编程日记 2025/5/29 18:14:00

Android——RecyclerView

RecyclerView的使用依赖 implementation("androidx.recyclerview:recyclerview:1.4.0")activity_recyclerview.xml <androidx.recyclerview.widget.RecyclerViewandroid:id"id/rv"android:layout_width"match_parent"android:layout_height…...

编程日记 2025/5/27 8:26:14

跨域问题（Cross-Origin Problem）

跨域问题（Cross-Origin Problem）是浏览器出于安全考虑，对不同源（协议、域名、端口）之间的资源访问进行限制而引发的限制。以下是详细解释： 1. 核心定义跨域：当一个网页（源A&#x…...

编程日记 2025/5/18 11:21:13

阿里云直接对系统云盘扩容

阿里云直接对系统云盘扩容登录阿里云控制台，进入ECS实例管理页面，检查目标磁盘的容量是否已更新为扩容后的数值。通过SSH远程连接服务器，使用命令 lsblk 或 fdisk -l 查看当前磁盘分区和容量，确认扩容后的物理磁盘已被系统识别。…...

编程日记 2025/5/26 7:28:48

Java大厂面试突击：从Spring Boot自动配置到Kafka分区策略实战解析

第一轮核心知识面试官：请解释Spring Boot中自动配置的工作原理并演示如何自定义一个ConfigurationProperties组件？ xbhog：自动配置通过EnableAutoConfiguration注解触发，结合当前环境判断（如是否检测到MyBatis依赖&…...

编程日记 2025/5/29 17:52:48

【python】lambda用法（结合例子理解）

目录 lambda 是什么？为什么叫 lambda？语法举例 1. 最简单的 lambda：单个数字处理 2. 用 lambda 排序一组字符串（按照长度排序） 3. 在列表里找出绝对值最小的数字 4. 给 map() 用 lambda 5. 组合使用：筛选出偶数 lambda 和 def 的对比 lambda 适合用在什么地…...

编程日记 2025/5/29 9:55:42

前端Ui设计工具

PS 稿、蓝湖、Sketch 和 Figma 前端 UI 设计工具的对比分析 PS 稿（Adobe Photoshop） 提供精准设计细节：PS 稿能让前端更精准地理解页面布局、元素尺寸、颜色等，通过精确测量和查看信息面板，把握设计元素的空间关系、…...

编程日记 2025/5/27 7:12:42

深入探索Python Pandas：解锁数据分析的无限可能

放在前头深入探索Python Pandas：解锁数据分析的无限可能深入探索Python Pandas：解锁数据分析的无限可能在当今数据驱动的时代，高效且准确地处理和分析数据成为了各个领域的关键需求。而Python作为一门强大且灵活的编程语言，…...

编程日记 2025/5/29 21:20:11

django admin 设置字段不可编辑

在Django中，如果你想让管理员在后台管理界面中无法编辑某个字段，你可以通过在模型的Meta类中设置editable属性为False，或者在admin.py文件中使用readonly_fields属性来实现。方法1：在模型中使用Meta类设置你可以在模型的Meta类…...

编程日记 2025/6/4 11:50:25

AI在医疗领域的10大应用：从疾病预测到手术机器人

AI在医疗领域的10大应用：从疾病预测到手术机器人系统化学习人工智能网站（收藏）：https://www.captainbed.cn/flu 文章目录 AI在医疗领域的10大应用：从疾病预测到手术机器人摘要引言1. 医学影像诊断：从静态…...

编程日记 2025/6/1 11:44:56

深入理解 Java 单例模式：从基础到最佳实践

单例（Singleton）模式是 Java 中最基本、最常用的设计模式之一。它确保一个类在任何情况下都只有一个实例，并提供一个全局访问点来获取这个唯一的实例。一、为什么需要单例模式？（使用场景） 单例模式主要适…...

编程日记 2025/5/29 21:18:29

Rust：安全与性能兼得的现代系统编程语言

一、起源与设计理念 Rust 是由 Mozilla 研究院 Graydon Hoare 于 2006 年发起设计的系统级编程语言，其诞生源于传统系统语言（如 C/C）在内存安全与并发编程方面的缺陷。经过近十年的迭代，Rust 1.0 稳定版于 2015 年正式发布&#…...

编程日记 2025/5/30 21:57:53

AI赋能智慧医疗新范式：小天互连即时通讯打造高效、安全的医疗通讯平台

在医疗行业，高效的信息协作与严格的数据安全不仅直接关系患者诊疗效率，更是医院现代化管理的核心命题。小天互连即时通讯系统通过将智能化功能与医疗场景深度结合，打造出全链路数字化协作平台，有效破解了传统沟通模式的效率瓶颈&a…...

编程日记 2025/5/20 14:19:29

图像生成新势力：GPT-Image-1 与 GPT-4o 在智创聚合 API 的较量

在人工智能领域，图像生成技术正迅速发展，OpenAI 推出的 GPT-Image-1 和 GPT-4o 在图像生成方面展现出了强大的能力。智创聚合 API 平台已支持这两个模型，并且其图片生成 / 编辑工作台支持图片的循环编辑等功能，为用户提供了更便捷…...

编程日记 2025/5/26 14:48:37

如何避免爬虫因Cookie过期导致登录失效

1. Cookie的作用及其过期机制 1.1 什么是Cookie？ Cookie是服务器发送到用户浏览器并保存在本地的一小段数据，用于维持用户会话状态。爬虫在模拟登录后，通常需要携带Cookie访问后续页面。 1.2 Cookie为什么会过期？ 会话Cookie&…...

编程日记 2025/5/27 17:07:30

集成方案 | Docusign + 甄零科技，赋能企业海外业务高效增长！

本文将详细介绍 Docusign 与甄零科技的集成步骤及其效果，并通过实际应用场景来展示 Docusign 的强大集成能力，以证明 Docusign 集成功能的高效性和实用性。甄零科技是一家专注于数字化合同管理系统的 SaaS 解决方案提供商，致力于为企业打造“…...

编程日记 2025/5/31 15:16:38

【Arxiv 2025】Single Image Iterative Subject-driven Generation and Editing

文章目录文章标题作者及研究团队介绍01 在论文所属的研究领域，有哪些待解决的问题或者现有的研究工作仍有哪些不足？02 这篇论文主要解决了什么问题？03 这篇论文解决问题采用的关键解决方案是什么？04 这篇论文的主要贡献是什么&am…...

编程日记 2025/5/30 8:33:09

CoOAG：首个捕捉学术研究兴趣动态演变的数据集

2025-04-24，由西安交通大学基于学术合作网络构建一种新的动态图数据集CoOAG，用于研究动态图中的节点分类问题。该数据集通过捕捉作者研究兴趣的动态变化，为动态图学习领域提供了新的研究方向和测试平台，特别是在标签受限的动态节点…...

编程日记 2025/6/1 9:11:24

1. 前序遍历（Pre-order Traversal）

1.1 定义

1.2 访问顺序

1.3 示例

1.4 递归实现

1.5 应用场景

2. 中序遍历（In-order Traversal）

2.1 定义

2.2 访问顺序

2.3 示例

2.4 递归实现

2.5 应用场景

3. 后序遍历（Post-order Traversal）

3.1 定义

3.2 访问顺序

3.3 示例

3.4 递归实现

3.5 应用场景

4. 总结

4.1 递归实现的通用模板

相关文章：