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

二叉树遍历

二叉树的遍历是二叉树操作中的一个基本且重要的概念,它指的是按照一定的规则访问二叉树中的每个节点,并且每个节点仅被访问一次。常见的二叉树遍历方式有四种:前序遍历(Pre-order Traversal)、中序遍历(In-order Traversal)、后序遍历(Post-order Traversal)和层序遍历(Level-order Traversal)。

1. 前序遍历(Pre-order Traversal)

前序遍历的顺序是:根节点 -> 左子树 -> 右子树。对于每个节点,都遵循这个顺序进行遍历。

  • 递归实现
    void preorderTraversal(TreeNode root) {  if (root == null) return;  System.out.print(root.val + " "); // 访问根节点  preorderTraversal(root.left); // 遍历左子树  preorderTraversal(root.right); // 遍历右子树  
    }
  • 非递归(迭代)实现(使用栈):
    void preorderTraversalIterative(TreeNode root) {  Stack<TreeNode> stack = new Stack<>();  if (root != null) 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);  }  
    }

    2. 中序遍历(In-order Traversal)

    中序遍历的顺序是:左子树 -> 根节点 -> 右子树。这常用于二叉搜索树(BST)中,因为这样可以得到一个有序的节点序列。

  • 递归实现
    void inorderTraversal(TreeNode root) {  if (root == null) return;  inorderTraversal(root.left); // 遍历左子树  System.out.print(root.val + " "); // 访问根节点  inorderTraversal(root.right); // 遍历右子树  
    }
  • 非递归(迭代)实现(使用栈):
    void inorderTraversalIterative(TreeNode root) {  Stack<TreeNode> stack = new Stack<>();  TreeNode curr = root;  while (curr != null || !stack.isEmpty()) {  while (curr != null) {  stack.push(curr);  curr = curr.left; // 遍历到最左节点  }  curr = stack.pop(); // 弹出栈顶元素  System.out.print(curr.val + " "); // 访问节点  curr = curr.right; // 转向右子树  }  
    }

    3. 后序遍历(Post-order Traversal)

    后序遍历的顺序是:左子树 -> 右子树 -> 根节点。

  • 递归实现
    void postorderTraversal(TreeNode root) {  if (root == null) return;  postorderTraversal(root.left); // 遍历左子树  postorderTraversal(root.right); // 遍历右子树  System.out.print(root.val + " "); // 访问根节点  
    }
  • 非递归(迭代)实现(使用栈):
    void postorderTraversalIterative(TreeNode root) {  Stack<TreeNode> stack = new Stack<>();  TreeNode prev = null; // 用于记录上一次访问的节点  while (root != null || !stack.isEmpty()) {  while (root != null) {  stack.push(root);  root = root.left; // 遍历到最左节点  }  root = stack.peek(); // 弹出栈顶元素但不移除  // 如果右子树为空或者右子树已经访问过,则访问当前节点  if (root.right == null || root.right == prev) {  stack.pop();  System.out.print(root.val + " "); // 访问节点  prev = root;  root = null; // 回到上层循环,检查是否有其他节点需要访问  } else {  root = root.right; // 否则,转向右子树  }  }  
    }

    4. 层序遍历

  • 非递归(迭代)实现(使用队列)

    import java.util.LinkedList;  
    import java.util.Queue;  class TreeNode {  int val;  TreeNode left;  TreeNode right;  TreeNode(int x) { val = x; }  
    }  public class BinaryTreeLevelOrderTraversal {  public void levelOrderTraversal(TreeNode root) {  if (root == null) return;  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root); // 将根节点加入队列  while (!queue.isEmpty()) {  TreeNode currentNode = queue.poll(); // 从队列中取出一个节点  System.out.print(currentNode.val + " "); // 访问该节点  // 如果左子节点不为空,则将其加入队列  if (currentNode.left != null) {  queue.offer(currentNode.left);  }  // 如果右子节点不为空,则将其加入队列  if (currentNode.right != null) {  queue.offer(currentNode.right);  }  }  }  
    }

  • 非递归(迭代)实现

  • 实际上,层序遍历不常使用递归实现,因为递归本质上是栈的操作,而层序遍历需要的是队列。但我们可以借助一些额外的数据结构(如数组或链表)来模拟层序遍历的效果,但这通常不是推荐的做法,因为它违背了层序遍历的本意。

相关文章:

二叉树遍历

二叉树的遍历是二叉树操作中的一个基本且重要的概念&#xff0c;它指的是按照一定的规则访问二叉树中的每个节点&#xff0c;并且每个节点仅被访问一次。常见的二叉树遍历方式有四种&#xff1a;前序遍历&#xff08;Pre-order Traversal&#xff09;、中序遍历&#xff08;In-…...

uni app 调用前置摄像头

uniapp开发app并没有相关Api调用前置摄像头。只能使用5app的api 调用前置摄像头拍照 plus.camera.getCamera(index) 获取需要操作的摄像头对象&#xff0c;如果要进行拍照或摄像操作&#xff0c;需先通过此方法获取摄像头对象 index指定要获取摄像头的索引值&#xff0c;1表…...

哈工大李治军老师OS课程笔记(4)——内存管理

一 内存使用与分段&#xff08;实验六&#xff09; 内存是如何用起来的&#xff1f; 内存使用&#xff1a;将程序放在内存中&#xff0c;PC指向开始地址 重定位&#xff1a;修改程序中的地址&#xff08;是相对地址&#xff09; 什么时候完成重定位&#xff1f; 编译时加基址…...

代码随想录算法训练营第43天:动态规划part10:子序列问题

300.最长递增子序列 力扣题目链接(opens new window) 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&#xff0c;[3,6,2…...

传智教育引通义灵码进课堂,为技术人才教育学习提效

7 月 17 日&#xff0c;阿里云与传智教育在阿里巴巴云谷园区签署合作协议&#xff0c;双方将基于阿里云智能编程助手通义灵码在课程共建、品牌合作及产教融合等多个领域展开合作&#xff0c;共同推进 AI 教育及相关业务的发展&#xff0c;致力于培养适应未来社会需求的高素质技…...

企业信息化建设搞得好了叫系统工程,搞不好叫面子工程

2024-06-13 09:26贝格前端工场...

程序员如何平衡日常编码工作与提升式学习?

在快速变化的编程领域中&#xff0c;平衡日常编码工作与个人成长确实是一个重要且富有挑战性的议题。以下是我对这一问题的看法和建议&#xff1a; 1. 认识到平衡的重要性 首先&#xff0c;理解两者之间的平衡并非零和游戏&#xff0c;而是相辅相成的。高效的编码工作能够为个…...

Linux---文件系统和日志分析

文章目录 文件系统和日志分析inode和block概述inode包含文件的元信息用stat命令可以查看某个文件的inode信息Linux系统文件三个主要的时间属性 目录文件的结构用户通过文件名打开文件时&#xff0c;系统内部的过程查看inode号码的方法硬盘分区后的结构访问文件的简单流程inode的…...

MySQL 体系架构

文章目录 一. MySQL 分支与变种1. Drizzle2. MariaDB3. Percona Server 二. MySQL的替代1. Postgre SQL2. SQLite 三. MySQL 体系架构1.连接层2 Server层&#xff08;SQL处理层&#xff09;3. 存储引擎层1&#xff09;MySQL官方存储引擎概要2&#xff09;第三方引擎3&#xff0…...

跨站脚本攻击漏洞

1.JavaScript JavaScript 是一种脚本&#xff0c;一门编程语言&#xff0c;它可以在网页上实现复杂的功能&#xff0c;网页展现给你的不再是简单的静态信息&#xff0c;而是实时的内容更新&#xff0c;交互式的地图&#xff0c;2D/3D动画&#xff0c;滚动播放的视频等等。 &a…...

RabbitMQ入门与进阶

RabbitMQ入门与进阶 基础篇1. 为什么需要消息队列?2. 什么是消息队列?3. RabbitMQ体系结构介绍4. RabbitMQ安装5. HelloWorld6. RabbitMQ经典用法(工作模式)7. Work Queues8. Publish/Subscribe9. Routing10. Topics 进阶篇1. RabbitMQ整合SpringBoot2. 消息可靠性投递故障情…...

Unity新输入系统 之 InputActions(输入配置文件)

本文仅作笔记学习和分享&#xff0c;不用做任何商业用途 本文包括但不限于unity官方手册&#xff0c;unity唐老狮等教程知识&#xff0c;如有不足还请斧正​ 首先你应该了解新输入系统的基本单位Unity新输入系统 之 InputAction&#xff08;输入配置文件最基本的单位&#xff0…...

Linux运维篇-误删/bin,/sbin目录怎么修复系统

这里写自定义目录标题 前言实例挂载镜像&#xff0c;重启系统进入救援模式拷贝镜像系统中的/bin和/sbin目录到原系统重启系统 总结 前言 当你看到这篇文章的时候&#xff0c;你的系统可能已经无法登录&#xff0c;或者正在处于登录状态但是不能执行任何常规的命令&#xff0c;…...

构建高效外贸电商系统的技术探索与源码开发

在当今全球化的经济浪潮中&#xff0c;外贸电商作为连接国内外市场的桥梁&#xff0c;其重要性日益凸显。一个高效、稳定、功能全面的外贸电商系统&#xff0c;不仅能够助力企业突破地域限制&#xff0c;拓宽销售渠道&#xff0c;还能提升客户体验&#xff0c;增强品牌竞争力。…...

Java设计模式:中介者模式详解与最佳实践

Java设计模式&#xff1a;中介者模式详解与最佳实践 1. 引言 在软件开发过程中&#xff0c;特别是复杂系统的构建中&#xff0c;模块间的交互往往成为影响代码质量的重要因素。当模块之间耦合度过高时&#xff0c;系统的维护、扩展和理解成本都会显著增加。为了降低模块之间的…...

Matlab绘制像素风字母颜色及透明度随机变化动画

本文是使用 Matlab 绘制像素风字母颜色及透明度随机变化动画的教程 实现效果 实现代码 如果需要更改为其他字母组合&#xff0c;在下面代码的基础上简单修改就可以使用。 步骤&#xff1a;(1) 定义字母形状&#xff1b;(2) 给出字母组合顺序&#xff1b;(3) 重新运行程序&#…...

C:每日一题:二分查找

1、知识介绍&#xff1a; 1.1 概念&#xff1a; 二分查找是一种在有序数组中查找某一特定元素的搜索算法 1.2 基本思想&#xff1a; 每次将待查找的范围缩小一半&#xff0c;通过比较中间元素与目标元素的大小&#xff0c;来决定是在左半部分还是右半部分继续查找。 举个生…...

python Django中使用ORM进行分组统计并降序排列

python Django中使用ORM进行分组统计并降序排列 # 使用supplier和Count进行分组统计,其中supplier为MyModel的一个字段 supplier_counts MyModel.objects.values(supplier).annotate(countCount(supplier)).order_by(-count) # 输出统计结果 for supplier_count in supplier_…...

QT C++ 编写modbus 总结

[开源库的使用]libModbus编译及使用_libmodbus库-CSDN博客 libmodbus的下载与编译_modbus库文件下载-CSDN博客 【QT5】解决 QT 界面中文显示乱码问题_qt5输出中文乱码解决方法-CSDN博客 Qt&#xff1a;解决qt修改完ui文件起不到作用_qt ui文件修改后不生效-CSDN博客...

基于SpringBoot的网络海鲜市场系统的设计与实现

TOC springboot219基于SpringBoot的网络海鲜市场系统的设计与实现 绪论 1.1 选题背景 当人们发现随着生产规模的不断扩大&#xff0c;人为计算方面才是一个巨大的短板&#xff0c;所以发明了各种计算设备&#xff0c;从结绳记事&#xff0c;到算筹&#xff0c;以及算盘&…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...

【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法

使用 ROS1-Noetic 和 mavros v1.20.1&#xff0c; 携带经纬度海拔的话题主要有三个&#xff1a; /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码&#xff0c;来分析他们的发布过程。发现前两个话题都对应了同一…...