当前位置: 首页 > 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…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

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样…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...