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

定义
-
前序遍历(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…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...
