【数据结构|二叉树遍历】递归与非递归实现前序遍历、中序遍历、后序遍历
递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。
二叉树图

定义
-
前序遍历(Preorder Traversal): 前序遍历的顺序是先访问根节点,然后按照先左后右的顺序访问子节点。对于上面的二叉树,前序遍历的结果是:4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7。
-
中序遍历(Inorder Traversal): 中序遍历的顺序是按照先左后根再右的顺序访问子节点。对于上面的二叉树,中序遍历的结果是:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
-
后序遍历(Postorder Traversal): 后序遍历的顺序是按照先左后右再根的顺序访问子节点。对于上面的二叉树,后序遍历的结果是:1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4。
通俗易懂

如果上面的定义看着有点晕,看这里,如上图,在这三个节点中,观察根节点2的遍历位置
前序遍历:213
中序遍历:123
后序遍历:132
总结:不管哪个遍历方式,左右相比,都是左先,1在前,3在后,根节点2依次是前、中、后,递归时把子树看成整体,逻辑同理。
代码
public class BinaryTree {public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 6, 7};TreeNode root = TreeNode.buildTree(nums);System.out.print("前序遍历(递归):");preorderTraversal(root);System.out.println();System.out.print("中序遍历(递归):");inorderTraversal(root);System.out.println();System.out.print("后序遍历(递归):");postorderTraversal(root);System.out.println();System.out.print("前序遍历(栈):");preorderTraversal1(root);System.out.println();System.out.print("中序遍历(栈):");inorderTraversal1(root);System.out.println();System.out.print("后序遍历(栈):");postorderTraversal1(root);System.out.println();}//前序遍历(递归)public static void preorderTraversal(TreeNode root) {if (root == null) {return;}System.out.print(root.val + " "); // 访问根节点preorderTraversal(root.left); // 访问左子树preorderTraversal(root.right); // 访问右子树}// 中序遍历(递归)public static void inorderTraversal(TreeNode root) {if (root == null) {return;}inorderTraversal(root.left); // 访问左子树System.out.print(root.val + " "); // 访问根节点inorderTraversal(root.right); // 访问右子树}// 后序遍历(递归)public static void postorderTraversal(TreeNode root) {if (root == null) {return;}postorderTraversal(root.left); // 访问左子树postorderTraversal(root.right); // 访问右子树System.out.print(root.val + " "); // 访问根节点}// 前序遍历(栈)public static void preorderTraversal1(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " "); // 打印当前节点的值if (node.right != null) {stack.push(node.right); // 先将右子节点入栈}if (node.left != null) {stack.push(node.left); // 再将左子节点入栈}}}// 中序遍历(栈)public static void inorderTraversal1(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();TreeNode node = root;while (node != null || !stack.isEmpty()) {while (node != null) {stack.push(node);node = node.left; // 先将左子节点入栈}node = stack.pop();System.out.print(node.val + " "); // 打印当前节点的值node = node.right; // 再处理右子节点}}// 后序遍历(栈)public static void postorderTraversal1(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.push(root);while (!stack1.isEmpty()) {TreeNode node = stack1.pop();if (node.left != null) {stack1.push(node.left); // 先将左子节点入栈}if (node.right != null) {stack1.push(node.right); // 再将右子节点入栈}stack2.push(node); // 将当前节点入栈(用于后序遍历)}while (!stack2.isEmpty()) {System.out.print(stack2.pop().val + " "); // 打印栈中的节点值(即后序遍历结果)}}
}
TreeNode
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }// 构建二叉树public static TreeNode buildTree(int[] nums) {if (nums == null || nums.length == 0) {return null;}return buildTree(nums, 0, nums.length - 1);}private static TreeNode buildTree(int[] nums, int left, int right) {if (left > right) {return null;}int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = buildTree(nums, left, mid - 1);root.right = buildTree(nums, mid + 1, right);return root;}
}
运行结果
前序遍历(递归):4 2 1 3 6 5 7
中序遍历(递归):1 2 3 4 5 6 7
后序遍历(递归):1 3 2 5 7 6 4
前序遍历(栈):4 2 1 3 6 5 7
中序遍历(栈):1 2 3 4 5 6 7
后序遍历(栈):1 3 2 5 7 6 4
相关文章:
【数据结构|二叉树遍历】递归与非递归实现前序遍历、中序遍历、后序遍历
递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。 二叉树图 定义 前序遍历(Preorder Traversal): 前序遍历的顺序是先访问根节点,然后按照先左后右的顺序访问子节点。对于上面的二叉树,前序遍历的结果是&…...
iPhone 8 Plus透明屏有哪些场景化应用?
iPhone 8 Plus是苹果公司于2017年推出的一款智能手机,它采用了全新的玻璃机身设计,使得手机更加美观和时尚。 而透明屏则是一种新型的屏幕技术,可以使手机屏幕呈现出透明的效果,给人一种科技感十足的视觉体验。 透明屏是通过使用…...
解决 MySQL 删除数据后,ID 自增不连续问题
修复前 除了部分数据,导致后续新增的数据,ID 自增不连续 解决方案 执行下方 SQL 语句即可修复此问题,mbs_order为需要修复的表名 SET i0; UPDATE mbs_order SET id(i:i1); ALTER TABLE mbs_order AUTO_INCREMENT0;...
arcgis--网络分析(理论篇)
1、定义概念 (1)网络:由一系列相互联通的点和线组成,用来描述地理要素(资源)的流动情况。 (2)网络分析:对地理网络(如交通网络、水系网络)&…...
Linux笔记1(系统状态等)
man命令: man name: man section name: man -k regexp: 在 Linux 中,man 命令用于查看命令、函数或配置文件等的手册页,提供了详细的帮助文档。man 是 "manual" 的缩写。man 命令的用法如下: man [选项] [命令名]例如&…...
Set-up ESP-AT Environment on Windows using CMD
Before you start, the following environments need to be installed: Git BashPython environment, suggest Python version: 3.8.7. Please ensure the installation of Python v3.8 version environment, and remember to select the option “add to PATH” during the in…...
SpringBoot中Redis报错:NOAUTH Authentication required
1、问题 org.springframework.dao.InvalidDataAccessApiUsageException: NOAUTH Authentication required.; nested exception is redis.clients.jedis.exceptions.JedisDataException: NOAUTH Authentication required. … 2、解决 如果提供了密码还没解决,那可能是…...
需求飙升120%!芭比产品火爆出圈,意大利人争相购买!
据外媒报道,真人版《芭比》成为今年夏天最火的电影,仅在美国和加拿大,该影片的票房收入就超过3.5亿美元。在意大利《芭比》也备受追捧,目前的票房收入突破1670万欧元,成为2023年观看人数第三多的电影。 除了电影界之外…...
echarts-pie---------3D曲状环形饼图实现!!!
示例(参考此处饼图修改https://www.isqqw.com/viewer?id37497) 话不多说直接上代码 此套代码可以直接再echarts官网中的此处运行 let selectedIndex ; let hoveredIndex ; option getPie3D([{name: 数学,value: 60,itemStyle: {color: #1890FF,},},{…...
合并两个有序链表(leetcode)
题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 输入:l1 [1,2,4], l2 [1,3,4] 输出:[1,1,2,3,4,4]思路 每次递归都会比较当前两个节点的值,选择较小的节点作为合并后的链…...
CAS之AtomicReference原理解析
如果你了解了AtomicInteger的工作原理,或者看了如下文章,知道了AtomicInteger只能对当个int类型共享变量做cas的缺点。 CAS之AtomicInteger原理解析_z275598733的博客-CSDN博客 那么AtomicReference就是来解决这个问题的。原理很类似,只是A…...
JS/JQ实现字符串加密成 HEX(十六进制) 字符串
应用场景: 1、数据传输:在网络通信或数据存储中,将字符串转换为十六进制格式可以确保数据的可靠传输和存储。十六进制字符串只包含数字和字母,而不涉及控制字符或其他特殊字符,因此避免了特殊字符在传输过程中引起的问…...
骨传导耳机怎么样?盘点五款适合室外佩戴的骨传导耳机
不知道各位出去玩的时候,有没有觉得外面的世界太喧嚣,需要一副耳机开启自己的小天地,相信有很多人都有这种习惯,在路上戴着耳机享受属于自己的那一片天地,可是市面上种类这么多耳机,该如何选择呢࿰…...
【flink】使用flink-web-ui提交作业报错
使用WebUI提交作业出现错误。 错误截图: 弹框信息: Server Response Message: org.apache.flink.runtime.rest.handler.RestHandlerException: Could not execute application.at org.apache.flink.runtime.webmonitor.handlers.JarRunHandler.lambda$h…...
「从零入门推荐系统」22:chatGPT、大模型在推荐系统中的应用
作者 | gongyouliu 编辑 | gongyouliu 提示:全文2.5万字,预计阅读时长2小时,可以先收藏再慢慢阅读。 我们在上一章介绍了chatGPT、大模型的基本概念、核心技术原理等基础知识,有了这些背景知识的铺垫,下面我们来介绍ch…...
机器学习---概述(一)
文章目录 1.人工智能、机器学习、深度学习2.机器学习的工作流程2.1 获取数据集2.2 数据基本处理2.3 特征工程2.3.1 特征提取2.3.2 特征预处理2.3.3 特征降维 2.4 机器学习2.5 模型评估 3.机器学习的算法分类3.1 监督学习3.1.1 回归问题3.1.2 分类问题 3.2 无监督学习3.3 半监督…...
概念解析 | AutoFed:面向异构数据的联邦多模态自动驾驶的学习框架
AutoFed:面向异构数据的联邦多模态自动驾驶的学习框架 注1:本文系“概念解析”系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:面向异构数据的联邦学习在自动驾驶中的应用。 参考文献:Zheng T, Li A, Chen Z, et al. AutoFed: Heterogeneity-Aware F…...
vue3+uniapp自定义tabbar
首先把tabbar中的元素写在一个list中用v-for进行渲染 用一个interface进行定义接口,这样别人在review你的代码就可以清晰知道你的tabbar包含什么元素。 利用typescript特性进行类型定义,可以省去很多麻烦 import { reactive } from "vue" imp…...
stable diffusion webui 安装
安装环境:cuda10.2-cudnn8-devel-ubuntu18.04 torchtorchvision:[pytorch]pytorch官方安装法_torch1.13.1cu117_FL1623863129的博客-CSDN博客 error:RuntimeError: Couldnt determine Stable Diffusions hash: 69ae4b35e0a0f6ee1af8bb9a5d0016ccb27e36dc. 解决方法…...
csdn文章编辑器必备语法备用
前言 本文是为了记录csdn文章编辑器的必备语法,为写作小白提供更详细的写作规范技巧 csdn的质量分查询地址:质量分查询 这里的跳转链接,可以使用ctrlshift L 来输入链接 亦可以使用 链接: link. 🚀🚀🚀 &a…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
