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

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

递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。

二叉树图

定义

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

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

  3. 后序遍历(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  

相关文章:

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

递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。 二叉树图 定义 前序遍历&#xff08;Preorder Traversal&#xff09;&#xff1a; 前序遍历的顺序是先访问根节点&#xff0c;然后按照先左后右的顺序访问子节点。对于上面的二叉树&#xff0c;前序遍历的结果是&…...

iPhone 8 Plus透明屏有哪些场景化应用?

iPhone 8 Plus是苹果公司于2017年推出的一款智能手机&#xff0c;它采用了全新的玻璃机身设计&#xff0c;使得手机更加美观和时尚。 而透明屏则是一种新型的屏幕技术&#xff0c;可以使手机屏幕呈现出透明的效果&#xff0c;给人一种科技感十足的视觉体验。 透明屏是通过使用…...

解决 MySQL 删除数据后,ID 自增不连续问题

修复前 除了部分数据&#xff0c;导致后续新增的数据&#xff0c;ID 自增不连续 解决方案 执行下方 SQL 语句即可修复此问题&#xff0c;mbs_order为需要修复的表名 SET i0; UPDATE mbs_order SET id(i:i1); ALTER TABLE mbs_order AUTO_INCREMENT0;...

arcgis--网络分析(理论篇)

1、定义概念 &#xff08;1&#xff09;网络&#xff1a;由一系列相互联通的点和线组成&#xff0c;用来描述地理要素&#xff08;资源&#xff09;的流动情况。 &#xff08;2&#xff09;网络分析&#xff1a;对地理网络&#xff08;如交通网络、水系网络&#xff09;&…...

Linux笔记1(系统状态等)

man命令&#xff1a; man name: man section name: man -k regexp: 在 Linux 中&#xff0c;man 命令用于查看命令、函数或配置文件等的手册页&#xff0c;提供了详细的帮助文档。man 是 "manual" 的缩写。man 命令的用法如下&#xff1a; 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、解决 如果提供了密码还没解决&#xff0c;那可能是…...

需求飙升120%!芭比产品火爆出圈,意大利人争相购买!

据外媒报道&#xff0c;真人版《芭比》成为今年夏天最火的电影&#xff0c;仅在美国和加拿大&#xff0c;该影片的票房收入就超过3.5亿美元。在意大利《芭比》也备受追捧&#xff0c;目前的票房收入突破1670万欧元&#xff0c;成为2023年观看人数第三多的电影。 除了电影界之外…...

echarts-pie---------3D曲状环形饼图实现!!!

示例&#xff08;参考此处饼图修改https://www.isqqw.com/viewer?id37497&#xff09; 话不多说直接上代码 此套代码可以直接再echarts官网中的此处运行 let selectedIndex ; let hoveredIndex ; option getPie3D([{name: 数学,value: 60,itemStyle: {color: #1890FF,},},{…...

合并两个有序链表(leetcode)

题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]思路 每次递归都会比较当前两个节点的值&#xff0c;选择较小的节点作为合并后的链…...

CAS之AtomicReference原理解析

如果你了解了AtomicInteger的工作原理&#xff0c;或者看了如下文章&#xff0c;知道了AtomicInteger只能对当个int类型共享变量做cas的缺点。 CAS之AtomicInteger原理解析_z275598733的博客-CSDN博客 那么AtomicReference就是来解决这个问题的。原理很类似&#xff0c;只是A…...

JS/JQ实现字符串加密成 HEX(十六进制) 字符串

应用场景&#xff1a; 1、数据传输&#xff1a;在网络通信或数据存储中&#xff0c;将字符串转换为十六进制格式可以确保数据的可靠传输和存储。十六进制字符串只包含数字和字母&#xff0c;而不涉及控制字符或其他特殊字符&#xff0c;因此避免了特殊字符在传输过程中引起的问…...

骨传导耳机怎么样?盘点五款适合室外佩戴的骨传导耳机

不知道各位出去玩的时候&#xff0c;有没有觉得外面的世界太喧嚣&#xff0c;需要一副耳机开启自己的小天地&#xff0c;相信有很多人都有这种习惯&#xff0c;在路上戴着耳机享受属于自己的那一片天地&#xff0c;可是市面上种类这么多耳机&#xff0c;该如何选择呢&#xff0…...

【flink】使用flink-web-ui提交作业报错

使用WebUI提交作业出现错误。 错误截图&#xff1a; 弹框信息&#xff1a; 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 提示&#xff1a;全文2.5万字&#xff0c;预计阅读时长2小时&#xff0c;可以先收藏再慢慢阅读。 我们在上一章介绍了chatGPT、大模型的基本概念、核心技术原理等基础知识&#xff0c;有了这些背景知识的铺垫&#xff0c;下面我们来介绍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进行定义接口&#xff0c;这样别人在review你的代码就可以清晰知道你的tabbar包含什么元素。 利用typescript特性进行类型定义&#xff0c;可以省去很多麻烦 import { reactive } from "vue" imp…...

stable diffusion webui 安装

安装环境:cuda10.2-cudnn8-devel-ubuntu18.04 torchtorchvision:[pytorch]pytorch官方安装法_torch1.13.1cu117_FL1623863129的博客-CSDN博客 error&#xff1a;RuntimeError: Couldnt determine Stable Diffusions hash: 69ae4b35e0a0f6ee1af8bb9a5d0016ccb27e36dc. 解决方法…...

csdn文章编辑器必备语法备用

前言 本文是为了记录csdn文章编辑器的必备语法&#xff0c;为写作小白提供更详细的写作规范技巧 csdn的质量分查询地址&#xff1a;质量分查询 这里的跳转链接&#xff0c;可以使用ctrlshift L 来输入链接 亦可以使用 链接: link. &#x1f680;&#x1f680;&#x1f680; &a…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...