当前位置: 首页 > 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;以及算盘&…...

Rust GraphQL实战:async-graphql深度解析

Rust GraphQL实战&#xff1a;async-graphql深度解析 引言 在Rust开发中&#xff0c;GraphQL是构建灵活API的重要技术。作为一名从Python转向Rust的后端开发者&#xff0c;我深刻体会到async-graphql在构建GraphQL服务方面的优势。async-graphql提供了类型安全的Schema定义和异…...

5D动感影院|打造沉浸式体验的新一代互动影院解决方案

随着数字技术与沉浸式体验的不断发展&#xff0c;传统影院已经无法完全满足现代观众对互动性与真实感的需求。在这一背景下&#xff0c;5D动感影院应运而生&#xff0c;凭借多维度感官融合技术&#xff0c;为观众带来前所未有的沉浸式观影体验。作为集视觉、听觉、触觉及环境特…...

如何让PT下载像点外卖一样简单?3个场景教你玩转PT-Plugin-Plus

如何让PT下载像点外卖一样简单&#xff1f;3个场景教你玩转PT-Plugin-Plus 【免费下载链接】PT-Plugin-Plus PT 助手 Plus&#xff0c;为 Microsoft Edge、Google Chrome、Firefox 浏览器插件&#xff08;Web Extensions&#xff09;&#xff0c;主要用于辅助下载 PT 站的种子。…...

南京数字化申报实战开启:提交材料后,如何确保您的技术底座不被“合规性审计”一票否决?

【行动指南&#xff1a;从填报到过审】截至 2026年5月12日&#xff0c;南京市中小企业数字化转型城市试点的线上申报通道已正式运行。在首批提交材料的企业反馈中&#xff0c;一个核心细节引起了市场的高度关注&#xff1a;申报系统不仅要求填写投入金额&#xff0c;更强化了对…...

流式Markdown解析器:实现实时渲染与性能优化的核心技术

1. 项目概述&#xff1a;一个实时渲染的Markdown流式解析器如果你经常需要处理动态生成的Markdown内容&#xff0c;比如从API接口实时获取、从数据库流式读取&#xff0c;或者构建一个支持用户边输入边预览的编辑器&#xff0c;那你一定遇到过这样的痛点&#xff1a;传统的Mark…...

ToDesk、向日葵、UU远程横评:谁才是2026国产远控首

ToDesk、向日葵、UU远程横评&#xff1a;谁才是2026国产远控首选一、前言&#xff1a;国产远控崛起&#xff0c;2026 怎么选&#xff1f;远程控制早已从 “小众工具” 变成个人、办公、游戏、运维的刚需。2026 年国产远控阵营已全面崛起&#xff0c;ToDesk、向日葵、UU 远程成为…...

企业级应用如何利用Taotoken多模型能力优化AI服务调用

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 企业级应用如何利用Taotoken多模型能力优化AI服务调用 在构建依赖大语言模型的企业级应用时&#xff0c;开发团队常面临模型选型单…...

【限时公开】ElevenLabs企业级有声书工作台搭建指南:Webhook自动触发+Notion项目看板+音频质量AI评分模型(含开源评估脚本)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;ElevenLabs企业级有声书工作台全景概览 ElevenLabs 企业级有声书工作台&#xff08;Enterprise Audiobook Studio&#xff09;是一套面向出版机构、教育平台与内容工厂的端到端语音生成协同平台&#x…...

Illustrator脚本自动化终极指南:如何节省设计师90%重复工作时间

Illustrator脚本自动化终极指南&#xff1a;如何节省设计师90%重复工作时间 【免费下载链接】illustrator-scripts Adobe Illustrator scripts 项目地址: https://gitcode.com/gh_mirrors/il/illustrator-scripts Adobe Illustrator脚本自动化是每个设计师都应该掌握的生…...

开源协作平台Octopal:整合Git、文档与任务的项目管理利器

1. 项目概述&#xff1a;一个为开发者量身定制的开源协作平台如果你是一名开发者&#xff0c;或者是一个小型技术团队的负责人&#xff0c;那么你一定对这样的场景不陌生&#xff1a;手头有几个并行的项目&#xff0c;团队成员分散&#xff0c;沟通主要靠即时通讯工具&#xff…...