Java 二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。
前序遍历(根 左 右)
先访问根结点,然后前序遍历左子树,再前序遍历右子树
中序遍历(左 根 右)
中序遍历根结点的左子树,然后访问根结点,最后遍历右子树
后序遍历(左 右 根)
从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点
层级遍历(从上到下 从左到右)
从根结点从上往下从左往右依次遍历
思路
非递归:
前序遍历:从根节点开始,首先将根节点压入栈中,栈不为空进行出栈并打印结点的value数值,然后将该结点的不为空的右结点和左结点依次进行入栈操作重复直到栈为空。
后序遍历:从根节点开始,首先将根节点压入栈中,栈不为空进行出栈并入栈到另一个栈中,然后将该结点的不为空的左结点和右结点依次进行入栈操作重复直到栈为空。然后遍历另一个栈进行出栈并打印结点的值。
中序遍历:从根节点开始将该结点以及它的左边界依次进行入栈,当该结点为null时,然后进行出栈操作,打印出栈结点的value数值,并入栈弹出结点的右结点,然后重复上述步骤,继续入栈该结点的左边界直到为空。。。。
层次遍历:从根节点放入队列,队列不为空的时候进行出队列并打印该结点的value数值,然后依次将该结点的左结点和右结点进行放入队列,一直重复直到队列为空。
代码
Node结点
public class Node<V> {V value;public Node(V value) {this.value = value;}public Node left;public Node right;
}
遍历代码
public class Tree {//递归先序遍历public static void preOrder1(Node head){if(head!=null){System.out.print(head.value+" ");preOrder1(head.left);preOrder1(head.right);}}//先序遍历public static void preOrder(Node head){if(head!=null){Stack<Node> stack=new Stack<>();stack.add(head);//压到栈尾while (!stack.empty()){head=stack.pop();System.out.print(head.value+" ");if(head.right!=null)stack.push(head.right);if(head.left!=null)stack.push(head.left);}}System.out.println();}//后序遍历public static void postOrder(Node head){if(head!=null){Stack<Node> stack1=new Stack<>();Stack<Node> stack2=new Stack<>();stack1.push(head);while (!stack1.empty()){head = stack1.pop();stack2.push(head);if(head.left!=null)stack1.push(head.left);if(head.right!=null)stack1.push(head.right);}while (!stack2.empty()){Node pop = stack2.pop();System.out.print(pop.value+" ");}System.out.println();}}//中序遍历public static void inOrder(Node head){Stack<Node> stack=new Stack<>();while (!stack.empty()||head!=null){if(head!=null){stack.push(head);head=head.left;}else {head=stack.pop();System.out.print(head.value+" ");head=head.right;}}System.out.println();}//层次遍历public static void widthOrder(Node head){if(head!=null){Queue<Node> queue=new LinkedList<>();queue.add(head);while (!queue.isEmpty()){Node poll = queue.poll();System.out.print(poll.value+" ");if(poll.left!=null)queue.add(poll.left);if(poll.right!=null){queue.add(poll.right);}}}System.out.println();}}
相关文章:
Java 二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。前序遍历(根 左 右)先访问根结点,然后前序遍历左子树…...
实习日记-C#
数据类型 字符串常量 string a "hello, world"; // hello, world string b "hello, world"; // hello, world string c "hello \t world"; // hello world string d "hello \t wor…...
Tech Lead如何引导团队成员解决问题?
作为一个开发团队的Tech Lead,当团队成员向你寻求帮助时,你有没有说过下面这些话? 你别管了,我来解决这个问题你只要。。。就行了你先做其他的吧,我研究一下,然后告诉你怎么做 当我们说这些话时ÿ…...
07--组件
一、小程序组件分类微信团队为开发者提供了一系列基础组件,开发者可以通过组合这些基础组件进行快速开发。小程序中的组件也是非常丰富的,开发者可以基于组件快速搭建出漂亮的页面结构。小程序中的组件其实相当于网页中的HTML标签,只不过标签…...
怎么做好一个完整的项目复盘
复盘,是运营必不可少的能力,小到一次买菜的经历,大到百亿千亿的投资项目,都可以通过复盘来总结规律、提升水平。简单说来,复盘可以达到的效果有两条:优化弱项,强化强项明确自己的价值࿰…...
浅谈一下mysql8.0与5.7的字符集
修改字符集 修改步骤 在MySQL8.0版本之前,默认字符集为1atin1,utf8字符集指向的是utf8mb3。网站开发人员在数据库设计的时候往往会将编码修改为ut8字符集。如果遗忘修改默认的编码,就会出现乱码的问题。从MySQL8.0开始,数据库的默认编码将改…...
paddle推理部署(cpu)
我没按照官方文档去做,吐槽一下,官方文档有点混乱。。一、概述总结起来,就是用c示例代码,用一个模型做推理。二、示例代码下载https://www.paddlepaddle.org.cn/paddle/paddleinferencehttps://github.com/PaddlePaddle/Paddle-In…...
想开发IM集群?先搞懂什么是RPC!
即时通讯网官方技术群和社区里,经常有开发者在纠结怎么开发IM集群,虽然真正的使用人数,可能用个人电脑单机都能支撑。你也许会说,明明不需要用到IM集群,干吗要自找麻烦?答曰:“老板说这个得有&a…...
案例13-前端对localStorage的使用分析
一:背景介绍 前端在调用后端接口获取某一个人的评论次数、获赞次数、回复次数。调用之后判断后端返回过来的值。如果返回回来的值是0的话,从缓存中获取对应的值,如果从缓存中获取的评论次数为空那么其他两个的次数也为0。 二:思路…...
CNNIC第51次中国互联网络发展状况统计报告用户规模变化发布、解读与白杨SEO看法
一、第51次《中国互联网络发展状况统计报告》发布 3月2日,中国互联网络信息中心(简称CNNIC)在京发布第51次《中国互联网络发展状况统计报告》。《报告》显示,截至2022年12月,我国网民规模达10.67亿,较2021…...
【数据结构】单链表的实现
本篇主要总结单链表是如何实现的,数据结构是如何管理数据的,详细的介绍每一步是如何实现以及各种注意事项。🚀1.单链表的实现🚀🍭1.1单链表的尾插🍭1.2单链表的头插🍭1.3单链表的打印dz…...
从0到1做产品!产品设计的6个步骤
相信不少产品经理在刚入行时,都遇到过这样的情况: 接到需求后不知所措,然后下意识地照着竞品开始盲目地画原型。 其实,这样的设计过程不仅缺乏逻辑性,在后续阶段也很容易出现各种问题。 在此,跟大家分享一下…...
ESP32遥控器软硬件设计
一. 前言 做智能车 或者 四轴飞控怎么能少得了遥控器呢!在这里给大家分享一个简单的基于ESP32遥控器的设计,包括软硬件以及3D外壳。 二. 硬件设计 1. 功能介绍 遥控器嘛,通信方式是最重要的,本设计支持 WIFI、蓝牙 和 2.4G&…...
vue-template-admin的keep-alive缓存与移除缓存
一,场景 A页面是表单页面,填写后需要跳转B页面。如果B页面不操作返回的话,应该能还原A页面的内容,而如果B页面点击提交,再回到A页面的时候,应该清除缓存。 二,实现方法 A页面要缓存数据&…...
【人工智能 AI】机器学习快速入门教程(Google)
目录 机器学习术语 标签 特性 示例 模型 回归与分类 深入了解机器学习:线性回归 深入了解机器学习:训练和损失 平方损失函数:一种常用的损失函数 机器学习术语 预计用时:8 分钟 什么是(监督式ÿ…...
适配器模式
概览 适配器模式是一种结构型设计模式,用于将一个类的接口转换为客户端所期望的另一种接口。通常情况下,这种转换是由一个适配器类完成的,适配器类包装了原始类,并实现了客户端所期望的接口。这种模式非常适用于在不修改现有代码…...
00后跨专业学软件测试,斩获8.5K高薪逆袭职场
我想说的第一句:既然有梦想,就应该去拼搏还记得,我大学毕业前,就已经暗下决心到xxx培训机构接受培训。那个时候,没有任何海同公司的人主动找我或者联系过我,我是自己在网上发现了xxxx培训机构的!…...
数据结构和算法学习
文章目录精通一个领域切题四件套算法算法的五个条件流程图数据结构数据与信息数据信息数据结构和算法数据结构算法时间复杂度空间复杂度数组 Array优点缺点数组和链表的区别时间复杂度链表 Linked List优点缺点时间复杂度单向链表双向链表循环链表双向循环链表堆栈 Stack队列 Q…...
剑指 Offer II 012. 左右两边子数组的和相等
题目链接 剑指 Offer II 012. 左右两边子数组的和相等 easy 题目描述 给你一个整数数组 nums,请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端,那…...
Java货物摆放
题目描述 小蓝有一个超大的仓库,可以摆放很多货物。 现在,小蓝有 � n 箱货物要摆放在仓库,每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向,每箱货物的边都必须严格平行于长、宽、高。 小蓝希望所…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
