＜JavaDS＞ 二叉树遍历各种遍历方式的代码实现 -- 前序、中序、后序、层序遍历

目录

有以下二叉树：

一、递归

1.1 前序遍历-递归

1.2 中序遍历-递归

1.3 后序遍历-递归

二、递归--使用链表

2.1 前序遍历-递归-返回链表

2.2 中序遍历-递归-返回链表

2.3 后序遍历-递归-返回链表

三、迭代--使用栈

3.1 前序遍历-迭代-使用栈

3.2 中序遍历-迭代-使用栈

3.3 后序遍历-迭代-使用栈

四、层序遍历

4.1 层序遍历-迭代-使用队列

4.2 层序遍历-迭代-返回二维链表

有以下二叉树：

一、递归

逻辑/思路：
递归思想是将大问题分解为解法相似的小问题。
已知根节点有左右子树，根节点的子节点又各有自己的左右子树，不断地对每棵子树进行左右分解，这就是从大问题到小问题。
递归有两大关键条件：递推条件和回归条件，前者作用于递，后者作用于归。
递推条件在方法中，不断将左右子节点分别作为参数，重复调用本方法，每轮调用方法都在访问更深地子节点，达成了递归中的推进条件；
回归条件当访问到的节点为null时(如上图)，就不能继续往下访问了，所以节点为null时，就return，这是回归条件；
二叉树的前中后序递归遍历，思路基本相同，区别只在于调用方法和打印的顺序不同。
以下分别是二叉树的前序、中序、后序递归遍历的代码：

1.1 前序遍历-递归

    public static void PreorderTraversal1(TreeNode root) { //当前节点为null，则return；if(root == null){return;}//打印当前节点；System.out.print(root.val+" ");//找左子节点；PreorderTraversal1(root.left);//找右子节点；PreorderTraversal1(root.right);}//运行结果：
1 2 3 4 5 6 7 

1.2 中序遍历-递归

    public static void InorderTraversal1(TreeNode root) {//当前节点为null，则return；if(root == null){return;}//找左子节点；InorderTraversal1(root.left);//打印当前节点；System.out.print(root.val+" ");//找右子节点；InorderTraversal1(root.right);}//运行结果：
3 2 4 1 5 7 6 

1.3 后序遍历-递归

    public static void PostorderTraversal1(TreeNode root) {//当前节点为null，则return；if(root == null){return;}//找左子节点；PostorderTraversal1(root.left);//找右子节点；PostorderTraversal1(root.right);//打印当前节点；System.out.print(root.val+" ");}//运行结果：
3 4 2 7 6 5 1 

二、递归--使用链表

逻辑/思路：
        同样是使用递归的逻辑思想，只是由于使用了链表的数据结构，所以在递归的过程中需要将元素加入到链表中。

2.1 前序遍历-递归-返回链表

    public static List<Integer> preorderTraversal2(TreeNode root){//新建链表；List<Integer> list = new ArrayList<>();//当前节点为null，则return；if(root == null){return list;}//add当前节点；list.add(root.val);//找当前节点的左子节点，并存储在新链表中；List<Integer> listLeft = preorderTraversal2(root.left);//将代表左子树的新链表中的元素全部添加到list中；list.addAll(listLeft);//找当前节点的右子节点，并存储在新链表中；List<Integer> listRight = preorderTraversal2(root.right);//将代表右子树的新链表中的元素全部添加到list中；list.addAll(listRight);//返回代表这个子树的list；return list;}//运行结果：
1 2 3 4 5 6 7 

2.2 中序遍历-递归-返回链表

    public static List<Integer> InorderTraversal2(TreeNode root){//新建链表；List<Integer> list = new ArrayList<>();//当前节点为null，则return；if(root == null){return list;}//找当前节点的左子节点，并存储在新链表中；List<Integer> listLeft = InorderTraversal2(root.left);//将代表左子树的新链表中的元素全部添加到list中；list.addAll(listLeft);//add当前节点；list.add(root.val);//找当前节点的右子节点，并存储在新链表中；List<Integer> listRight = InorderTraversal2(root.right);//将代表右子树的新链表中的元素全部添加到list中；list.addAll(listRight);//返回代表这个子树的list；return list;}//运行结果：
3 2 4 1 5 7 6 

2.3 后序遍历-递归-返回链表

    public static List<Integer> PostorderTraversal2(TreeNode root){//新建链表；List<Integer> list = new ArrayList<>();//当前节点为null，则return；if(root == null){return list;}//找当前节点的左子节点，并存储在新链表中；List<Integer> listLeft = PostorderTraversal2(root.left);//将代表左子树的新链表中的元素全部添加到list中；list.addAll(listLeft);//找当前节点的右子节点，并存储在新链表中；List<Integer> listRight = PostorderTraversal2(root.right);//将代表右子树的新链表中的元素全部添加到list中；list.addAll(listRight);//add当前节点；list.add(root.val);//返回代表这个子树的list；return list;}//运行结果：
3 4 2 7 6 5 1 

三、迭代--使用栈

逻辑/思路：

        迭代是使用栈来帮助遍历二叉树。这种遍历方式利用了栈“后进先出”的特点，来达到对二叉树中的父节点进行回溯的目的。

        也就是说，当遍历到一个节点即将该节点压栈，当完成对左子树的访问之后，利用弹出并记录栈顶元素的方式，得到左子树的父节点，并通过这个父节点访问右子树。

        因为压栈的第一个元素必然为根节点，因此，当栈为空时，必然全部节点都遍历完成了。

3.1 前序遍历-迭代-使用栈

    public static void PreorderTraversal3(TreeNode root){//如果root为null，return；if(root == null){return;}//新建一个栈；Stack<TreeNode> stack = new Stack<>();//将根节点压栈；stack.push(root);//如果栈不为空；while (!stack.isEmpty()){//弹出栈顶元素，并记录为cur；TreeNode cur = stack.pop();//因为是前序遍历，打印当前节点，再进行后续操作；System.out.print(cur.val+" ");//如果cur的右子节点不为空，则将其压栈；if(cur.right != null){stack.push(cur.right);}//如果cur的左子节点不为空，则将其压栈；if(cur.left != null){stack.push(cur.left);}}}//运行结果：
1 2 3 4 5 6 7 
为什么压栈先压右子节点，再压左子节点？
        因为要按前序遍历打印，而栈是后进先出，所以后压左子节点，等下先弹出的也是左子节点，先弹出先打印。

3.2 中序遍历-迭代-使用栈

    public static void InorderTraversal3(TreeNode root){//如果root为null，return；if(root == null){return;}//新建一个栈；Stack<TreeNode> stack = new Stack<>();//用一个临时“指针”记录root(因为要移动指针，不然等下根节点跑哪去都不知道了)TreeNode cur = root;//如果cur不为空或者栈不为空；while (cur != null || !stack.isEmpty()){//如果节点不为空，则将节点压栈，并让指针不断向左子节点移动，直到节点为空；//当循环停下时，此时栈顶元素必然是树中最左边且未被遍历过的节点；while (cur != null){stack.push(cur);cur = cur.left;}//弹出栈顶元素，并记录为pre；TreeNode pre = stack.pop();//因为是中序遍历，打印当前节点，再进行后续操作；System.out.print(pre.val+" ");//如果pre的右子节点不为空，则将指针cur移动到右子节点上；if(pre.right != null){cur = pre.right;}}}//运行结果：
3 2 4 1 5 7 6 
为什么进入循环的判断条件是cur != null || !stack.isEmpty()？

        cur不为空的判断条件是为了让一开始栈中还没有元素时，能够顺利进入循环。

        栈不为空代表还有元素没有遍历。

3.3 后序遍历-迭代-使用栈

    public static void PostorderTraversal3(TreeNode root){//如果root为null，return；if(root == null){return;}//新建一个栈；Stack<TreeNode> stack = new Stack<>();//用一个临时“指针”记录root(因为要移动指针，不然等下根节点跑哪去都不知道了)TreeNode cur = root;//将根节点压栈；stack.push(root);//如果栈不为空；while (!stack.isEmpty()) {//查看并记录栈顶元素这个节点；TreeNode peek = stack.peek();//根据以下条件，进行后续操作；if (peek.left != null && peek.left != cur && peek.right != cur) {stack.push(peek.left);} else if (peek.right != null && peek.right != cur) {stack.push(peek.right);} else {System.out.print(stack.pop().val + " ");cur = peek;}}}//运行结果：
3 4 2 7 6 5 1 
上述代码中的 if...else if..else 为什么这样设置条件？

if (peek.left != null && peek.left != cur && peek.right != cur) { stack.push(peek.left); }

判断peek有没有左子节点，且peek的左右子节点有没有被处理过；

如果左右子节点都没有被处理过，那么将peek的左子节点压栈；
else if (peek.right != null && peek.right != cur) { stack.push(peek.right); }

再判断peek有没有右子节点，且peek的右子节点有没有被处理过；

在这里不能对左子节点判断是否操作过，因为是先遍历的左子节点，如果存在左子节点必然是操作过的。所以如果加入左子节点的判断，则必然进不了这个else if；

如果右子节点没有被处理过，那么将peek的右子节点压栈；
通过前两个条件可以看出，只要有左子节点，必然先处理左子节点，没有左子节点或者左子节点被处理完了，才开始处理右子节点；处理方法如下：
else {
                System.out.print(stack.pop().val + " ");
                cur = peek;
            }
直到所有左右子节点处理完毕，最后一个弹出栈并被处理的，必然是一开始压栈的根节点root。

四、层序遍历

逻辑/思路：

        层序遍历与前序、中序、后序遍历都不同，层序遍历使用的是队列的数据结构进行遍历。

        核心思想是利用队列“先进先出”和“队头出，队尾入”的特点，分层遍历二叉树。

        如果需要返回一个二维链表，则是将二叉树每层的节点按顺序添加到各个链表中，每个链表代表一层，最终链表将作为元素，被添加到二维链表中；

4.1 层序遍历-迭代-使用队列

    public static void SequenceTraversal1(TreeNode root){//如果root为null，return；if(root == null){return;}//创建队列，root入队列；Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//如果队列中还有元素；while (queue.size() != 0){//队首出队列并记录cur；TreeNode cur = queue.poll();//打印cur的值；System.out.print(cur.val + " ");//如果cur有左子节点，将左子节点入队列；if(cur.left != null){queue.offer(cur.left);}//如果cur有右子节点，将右子节点入队列；if(cur.right != null){queue.offer(cur.right);}}}//运行结果：
1 2 5 3 4 6 7

4.2 层序遍历-迭代-返回二维链表

    public static List<List<Integer>> SequenceTraversal2(TreeNode root){//创建二维链表diList；List<List<Integer>> diList = new LinkedList<>();//如果root为空则return；if(root == null){return diList;}//创建队列，root入队列；Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//如果队列中还有元素；while(!queue.isEmpty()){//计算队列中的元素数量；int size = queue.size();//创建链表，用于存储每层的节点；List<Integer> list = new LinkedList<>();//根据上面的size确定需要循环多少次，即处理多少个节点；while (size>0){//队首出队列；TreeNode cur = queue.poll();//出队列一个size就--；size--;//把出队列的元素添加到list中；list.add(cur.val);//如果cur有左子节点，将左子节点入队列；if(cur.left != null){queue.offer(cur.left);}//如果cur有右子节点，将右子节点入队列；if(cur.right != null){queue.offer(cur.right);}}//把链表list添加到diList中；diList.add(list);}//返回diList；return diList;}//运行结果：
1 2 5 3 4 6 7

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/204311.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【Python3】【力扣题】367. 有效的完全平方数

【Python3】【力扣题】367. 有效的完全平方数

【力扣题】题目描述&#xff1a; 【Python3】代码&#xff1a; 1、解题思路&#xff1a;Python函数。num的平方根 或者 num的0.5次幂。 知识点&#xff1a;float.is_integer(...)&#xff1a;判断浮点数的值是否等于整数。也可以&#xff1a;浮点数.is_integer()。 pow(a,b)&…
阅读更多...
【SpringCloud】微服务的扩展性及其与 SOA 的区别

【SpringCloud】微服务的扩展性及其与 SOA 的区别

一、微服务的扩展性 由上一篇文章&#xff08;没看过的可点击传送阅读&#xff09;可知&#xff0c; 微服务具有极强的可扩展性&#xff0c;这些扩展性包含以下几个方面&#xff1a; 性能可扩展&#xff1a;性能无法完全实现线性扩展&#xff0c;但要尽量使用具有并发性和异步…
阅读更多...
【Intel FPGA】D5005 使用笔记

【Intel FPGA】D5005 使用笔记

项目总目标&#xff0c;在AFU中实现xx算法DDR 1.FPGA device &#xff1a;1SX280HN2F43E2VG 2 .硬件架构图 3.DDR信息 4.FIM &#xff08;FPAG Interface Manager&#xff09; The FIM contains the FPGA logic to support the accelerators, including the PCIe IP core, …
阅读更多...
UDS 相关时间参数

UDS 相关时间参数

文章目录 UDS 全部时间参数UDS 应用层诊断时间参数1、P2 Client P2 Server P2* Client P2* Server 图例2、S3 Client S3 Server 图例 UDS CNA-TP网络层时间参数1、N_As/N_Ar 图例2、N_Bs 图例3、 N_Br 图例4、N_Cs 图例N_Cr 图例 UDS 网络层流控制时间参数 UDS 全部时间参数 UD…
阅读更多...
Java17(LTS Long Term Support)特性

Java17(LTS Long Term Support)特性

支持JDK17的主流技术框架 spring framework 6.xspringboot 3.xkafka 3.0(不在支持jdk8)jenkins 2.357&#xff08;必须jdk11起步&#xff09;James Gosling表示赶紧弃用Java8&#xff0c;使用性能最好的JDK17Chart GPT也推荐JDK17&#xff0c;从长期到性能来说。 JDK17的特性 …
阅读更多...
【古月居《ros入门21讲》学习笔记】15_ROS中的坐标系管理系统

【古月居《ros入门21讲》学习笔记】15_ROS中的坐标系管理系统

目录 说明&#xff1a; 1. 机器人中的坐标变换 tf功能包能干什么&#xff1f; tf坐标变换如何实现 2. 小海龟跟随实验 安装 ros-melodic-turtle-tf 实验命令 运行效果 说明&#xff1a; 1. 本系列学习笔记基于B站&#xff1a;古月居《ROS入门21讲》课程&#xff0c;且使…
阅读更多...
数据治理框架和成熟度模型

数据治理框架和成熟度模型

数据治理成熟度模型 一个企业的数据治理能力越高&#xff0c;所享受到数据治理带来的价值也会越多&#xff0c;如增加收入、减少成本、降低风险等。于是&#xff0c;很多企业想要准确地评估本公司的数据治理能力&#xff0c;可以利用数据治理成熟度模型方法&#xff0c;包括 D…
阅读更多...
求和（打表题）

求和（打表题）

题目 打个表发现当 n 时答案为 p &#xff0c;否则为 1 &#xff0c;然后套板子。 #include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <cmath>using namespace std;#define int long long using i64 …
阅读更多...
直线（蓝桥杯）

直线（蓝桥杯）

直线 题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 在平面直角坐标系中&#xff0c;两点可以确定一条直线。如果有多点在一条直线上&#xff0c; 那么这些点中任意两点确定的直线是同一条。 给定平面上 2 3 个…
阅读更多...
万字解析设计模式之模板方法与解释器模式

万字解析设计模式之模板方法与解释器模式

一、模板方法模式 1.1概述 定义一个操作中算法的框架&#xff0c;而将一些步骤延迟到子类中&#xff0c;模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 例如&#xff0c;去银行办理业务一般要经过以下4个流程&#xff1a;取号、排队、办理具体业…
阅读更多...
戴尔科技推出全新96核Precision 7875塔式工作站

戴尔科技推出全新96核Precision 7875塔式工作站

工作站行业一直是快节奏且充满惊喜的。在过去25年中,戴尔Precision一直处于行业前沿,帮助创作者、工程师、建筑师、研究人员等将想法变为现实,并对整个世界产生影响。工作站所发挥的作用至关重要,被视为化不可能为可能的必要工具。如今,人工智能(AI)和生成式AI(GenAI)的浪潮正在…
阅读更多...
【JavaEE初阶】认识线程、创建线程

【JavaEE初阶】认识线程、创建线程

1. 认识线程&#xff08;Thread&#xff09; 1.1 概念 1) 线程是什么 一个线程就是一个 "执行流". 每个线程之间都可以按照顺序执行自己的代码. 多个线程之间 "同时" 执行着多份代码. 举例&#xff1a; 还是回到我们之前的银⾏的例⼦中。之前我们主要描…
阅读更多...
业务逻辑漏洞

业务逻辑漏洞

业务逻辑漏洞 扫描器扫不出来 漏洞包括 暴力破解任意用户/密码登陆短信/邮箱轰炸验证码绕过/爆破/重放/回传用户名/手机号枚举(用户名枚举&#xff1a;当用户登录时&#xff0c;显示用户名不存在&#xff0c;或密码不正确&#xff0c;两个其中一个不正确就称为用户名枚举)越…
阅读更多...
Python中的datetime库

Python中的datetime库

1. datetime datetime是Python中用于处理日期和时间的类&#xff0c;它包含在datetime模块中。使用datetime类&#xff0c;我们可以创建表示特定日期和时间的对象&#xff0c;以及进行日期和时间的计算和操作。 from datetime import datetime, timedelta# 获取当前日期和时间…
阅读更多...
20 章 多线程

20 章 多线程

20.1线程简介. 20.2创建线程 2.1继承Thread类 Thread 类是java.lang包中的一个类&#xff0c;从这个类中实例化的对象代表线程&#xff0c;程序员启动一个新线程需要建立Thread 实例。Thread类中常用的两个构造方法如下: public Thread():创建一个新的线程对象。 public Thre…
阅读更多...
用C++和python混合编写数据采集程序？

用C++和python混合编写数据采集程序？

之前看过一篇文章&#xff0c;主要阐述的就是多种语言混合编写爬虫程序&#xff0c;结合各种语言自身优势写一个爬虫代码是否行得通&#xff1f;觉得挺有意思的&#xff0c;带着这样的问题&#xff0c;我尝试着利用我毕生所学写了一段C和python混合爬虫程序&#xff0c;目前运行…
阅读更多...
LeetCode Hot100 84.柱状图中最大的矩形

LeetCode Hot100 84.柱状图中最大的矩形

题目&#xff1a; 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 方法&#xff1a; 代码&#xff1a; class Solution {public int largestRectang…
阅读更多...
成为AI产品经理——模型评估概述

成为AI产品经理——模型评估概述

目录 一、模型宣讲和评估的原因 二、模型宣讲 三、模型评估 1. 重要特征 ① 特征来源 ②特征意义 2.选择测试样本 3.模型性能和稳定性 一、模型宣讲和评估的原因 刘海丰老师提到他们在做一个金融AI产品未注重模型指标&#xff0c;过于注重业务指标&#xff0c;导致产生…
阅读更多...
Python小知识

Python小知识

个人学习笔记&#xff0c;用于记录使用过程中好用的技巧、好用的库。 1 小知识 1.1 相对路径 1.2 打包Exe文件 命令&#xff1a; pyinstaller -F main.py其中-F&#xff1a;覆盖之前打包的文件 mian.py&#xff1a;需要打包的Python文件 PS&#xff1a;使用pyinstaller 5.1…
阅读更多...
Docker，从入门到精通

Docker，从入门到精通

1、DockerFile 介绍 dockerfile 是啥?dockerfile 用来构建 docker 镜像的文件。 具体步骤&#xff1a; 1、编写一个 dockerfile 文件 2、docker build 构造一个镜像 3、docker run 运行镜像 4、docker push 发布镜像 DockerFile 构建过程 1、每个保留关键字都必须是大…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023