颠仆流离学二叉树2 (Java篇)

本篇会加入个人的所谓鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言

而是理解过并总结出来通俗易懂的大白话,

小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.

🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 !!!

在这里插入图片描述

前言

在上篇中我们学习了 二叉树的基本概念 以及他们的特性结论,并运用到了 具体的题目 中去解决问题 。

而在本篇中,小编讲继续学习 二叉树 的基本操作, 主要围绕着我们 遍历二叉树 来讲解 , 人狠话不多,下面让我们切入主题吧 💥 💥 💥

目录

  1. 二叉树的遍历初识

  2. 前序遍历

  3. 中序遍历

4.后序遍历

  1. 层序遍历

  2. 二叉树遍历的应用

一. 二叉树的遍历初识

学习二叉树的结构,最简单的方式就是遍历,所谓遍历 是指 沿着某条搜索路线,依次树中的某个节点均做一次访问, 访问节点所做的操作 依赖于要解决的各种实际问题。

遍历是二叉树是最重要的操作之一,是 二叉树上进行其他运算 的基础

1. 二叉树的遍历简介

在这里插入图片描述

在遍历二叉树时, 如果没有进行某种约定,每个人都按照自己的方式来遍历, 得到的结果就比较乱, 如果我们按照某个规则 来遍历, 则每个人对于遍历结果都是相同的 , 如果 N 代表 根节点,L 代表左节点, R 代表 右节点, 那根据遍历的的节点有以下的遍历方式。

  • NLR: 前序遍历 (先序遍历) 根据 根——》 左 ——》 右 的顺序对二叉树进行遍历

  • LNR : ==中序遍历 ==: 根据 左——》 根——》 右 的顺序 对二叉树进行遍历

  • LRN 后序遍历 : 根据 左——》 右 ——》 根 的顺序对二叉树进行遍历

详细的遍历方式, 小编下面细讲哦 💖 💖 💖 💖

在遍历二叉树之前, 我们先用一下代码简单的 构建一颗二叉树

public class MyBinaryTree {public static class TreeNode {public TreeNode left;public TreeNode right;public  char val;public TreeNode(char val) {this.val = val;}}private TreeNode  root;// 构造二叉树public TreeNode createBinaryTree() {root=new TreeNode('A');TreeNode B=new TreeNode('B');TreeNode D=new TreeNode('D');TreeNode E=new TreeNode('E');TreeNode H=new TreeNode('H');TreeNode C=new TreeNode('C');TreeNode F=new TreeNode('F');TreeNode G=new TreeNode('G');root.left=B;B.left=D;B.right=E;E.right=H;root.right=C;C.left=F;C.right=G;return root;}// 前序遍历
void preOrder(Node root);
// 中序遍历
void inOrder(Node root);
// 后序遍历
void postOrder(Node root);}

二. 前序遍历

1. 前序遍历的特点

在这里插入图片描述

按照从左子树开始走,一直 往下递归,每一步所走的路径成为我们的根,先遍历完根之后。

按照根左右的顺序, 当我们走完每个根节点的左子树 时, 先往下, 再往回归 , 左节点成为新的根, 会到最初的根节点之后,再向右子树进行 先递后归 的操作,

动画演示

请添加图片描述

2. 前序遍历的实现

因为前序遍历有 递归 和 非递归 的两种方式, 但 遍历的原理和方向都是一致的

在本篇文章中,。小编都会带着小伙伴们 一 一 实现 💥 💥 💥 💥

在这里插入图片描述

<1>. 前序遍历的递归实现

   // 前序遍历public void FirstDisplay(TreeNode root) {if (root==null) {return;}System.out.print(root.val+" ");FirstDisplay(root.left);FirstDisplay(root.right);}

在这里插入图片描述

这里的代码的递归思路就是完美的按照我们遍历方向来的, 先访问,后递归

<2>. 前序遍历的非递归实现

// 非递归的前序遍历public  void  FirstDisplayNo(TreeNode root) {// 先创建一个栈来存放树的每个节点Stack<TreeNode> stack=new Stack<>();// 先把艮节点创建一遍TreeNode cur=root;/*** 外循环主要遍历 右边的节点* 用于出栈的数据* 并让节点向右移动*/while (cur != null || !stack.empty()) {/*** 在这个内循环中* 当往左走就添加数据,一直到为 null 结束*  并进行打印*/while (cur != null) {// 先打印System.out.print(cur.val+" ");// 打印完就入栈stack.add(cur);// 节点向左移动cur=cur.left;}// 出栈存放数据cur=stack.pop();// 并向右走cur=cur.right;// 当再次循环时,如果左边还有节点就会继续存放}System.out.println();}

在这里插入图片描述

非递归的 实现步骤

  1. 先定义一个栈 , 来记录我们每次遍历过的 根节点
  1. 先让根节点一直 向左走 ,当遍历完我们的 左子树 (也就是我们的 root = null 时候), 并且入栈, 记录下来以便后面我们遍历 右子树
  1. 然后出栈, 开始 向右走 , 遍历我们的 右子树
  1. 当整个栈为 null 并且到达的这个节点 cur 也为 null , 就意味着遍历完整个 二叉树所有的节点

鱼式疯言

无论是 递归还是非递归前序遍历 , 我们的 前序遍历思路就是

先走根根走完走左左走完回到根再走右一层一层的走一步一步的回

细节处理

在代码上我们要注意的就是这个当节点为 null ,也就意味着我们要开始 回退上一个节点

二. 中序遍历

在这里插入图片描述

1. 中序遍历的特点

我们知道 中序遍历 , 是以 左- 根-右的顺序 进行遍历

我们先从 走左边, 还是让每个左节点先成为新的根, 当这个新的根的 左子树 都走完之后, 才能真正访问我们当前 新的节点

以此类推,我们新的节点访问结束后,就会进行回退到前一个旧的节点,继续访问,最终当整个 左子树走完 , 并且 访问完我们的根 , 就遍历我们的右子树 ,最终回到我们整颗树的 根节点

动画演示

请添加图片描述

2.中序遍历的实现

在这里插入图片描述

<1>.中序遍历的递归实现

// 中序遍历
public void middleDisplay(TreeNode root) {if (root==null) {return;}middleDisplay(root.left);System.out.print(root.val+" ");middleDisplay(root.right);
}

在这里插入图片描述

这里的代码的递归思路就是完美的按照我们遍历方向来的, 先递归,后访问 ,小编在这里就 不赘述

<2>. 中序遍历的非递归实现

// 非递归的中序遍历public  void  middleDisplayNo (TreeNode root) {// 创建一个栈用于回退节点Stack<TreeNode> stack=new Stack<>();// 先放根节点TreeNode cur=root;/*** 外循环主要用于遍历 右边* 更是用于出栈的回退*/while (cur != null || !stack.empty()) {/*** 内循环先遍历下去* 边遍历边存放*/while (cur != null) {stack.add(cur);cur=cur.left;}// 出栈最后一个无左节点的左子树cur=stack.pop();// 打印该节点System.out.print(cur.val+" ");// 再往右走cur=cur.right;}System.out.println();}

在这里插入图片描述

非递归的实现步骤

我们先定义一个 ,用来存储走过的每个 左子树的节点

  1. 往左边 的节点走,先整个左子树 的每个节点都入栈, 当 这个节点 为 null停止入栈

  2. 然后进行出栈, 出栈的时候,我们就可以对该节点进行打印(访问) , 并且向 右子树节点 开始走

  3. 当整个栈为 null 并且 该节点也为 null , 也就意味着遍历完二叉树 所有的节点

鱼式疯言

中序遍历的最核心的要点就是

无论是 递归 还是 非递归中序遍历

一定要先走完每个左子树, 当我们进行 回退 的时候。 才轮的到该 根节点去遍历, 最后才走 右子树的一种 顺序.

三. 后序遍历

1. 后序遍历的特点

在这里插入图片描述

后序遍历的顺序就是 : 左-右-根 的顺序,

还是先走左边的节点,让 左边的节点 成为 新的根 , 直到找到走完整个 左子树 ,回退后继续走 右子树,当 右子树走完之后,回去的根节点就是我们要 访问

动画演示

请添加图片描述

2. 后序遍历的实现

在这里插入图片描述

<1>. 后序遍历的递归实现

   // 后序遍历public void lastDisplay(TreeNode root) {if (root==null) {return;}lastDisplay(root.left);lastDisplay(root.right);System.out.print(root.val+" ");}

在这里插入图片描述

这里的代码的递归思路就是完美的按照我们遍历方向来的, 先递归,后访问 ,小编在这里就 不赘述

<2>. 后序遍历的非递归实现

 // 非递归的后序遍历public  void  lastDisplayNo (TreeNode root) {Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;TreeNode flg=null;while (cur != null || !stack.empty()) {while (cur != null) {stack.add(cur);cur=cur.left;}TreeNode top=stack.peek();if (top.right == null || flg==top.right) {System.out.print(top.val+" ");flg=top;stack.pop();} else {cur=top.right;}}System.out.println();}

在这里插入图片描述

非递归的实现思路

我们先定义一个栈,用来存放节点, 而这里存放的节点有可能是 左子树的节点,也有可能是 右子树的节点

  1. 先向左走,让左子树的节点先入栈
  1. 然后 查看栈顶元素,如果栈顶元素的右节点 null , 我们就 打印(访问) 该节点,
  1. 如果栈顶元素的 右节点 不为 null , 我们就 让 该节点 向右走 , 并且入栈
  1. 以此循环往复,当 栈为 null 并且 节点 cur 也为 null , 说明我们已经遍历完这个 二叉树所有的节点

鱼式疯言

无论是 非递归还是递归实现 对二叉树的 后序遍历

  • 小伙伴们只需要记住一点: 后序遍历 一定是 两边先走完 ,最后回到我们的根节点才 访问

  • 小伙伴们一定要把每个节点都看出一颗独立的树每个节点 都是一个 独立的根节点 来理解我们的 三大遍历

TreeNode flg =nullif (top.right == null || flg==top.right) {System.out.print(top.val+" ");flg=top;stack.pop();} 

细节处理: 我们需要用一个 flg 来记录上一个已经 访问过 的节点,判断 是否访问过, 防止再次让 top 向右走,继续入栈, 否则会进入 死循环

四. 层序遍历

谈及完前面的 三大遍历, 这些是我们 操作二叉树的根本 ,但还有还要介绍一种 比较特殊的遍历

在这里插入图片描述

1. 层序遍历的特点

二叉树 层序遍历 的方向是从 根节点,按照 从上而下,从左到右 的顺序进行遍历 二叉树的每一个节点

动画演示

请添加图片描述

2. 层序遍历的实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/class Solution {List<List<Integer>> S=new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {if(root==null) {return S;}creatOrder(root,0);return S;}public void creatOrder(TreeNode root,int i) {if(root==null) {return ;}if(S.size()==i) {S.add(new ArrayList<Integer>());}S.get(i).add(root.val);creatOrder(root.left,i+1);creatOrder(root.right,i+1);}
}

在这里插入图片描述

具体实现步骤:

  1. 我们用一个 二维数组(二维顺序表) 来存储每一个节点,二叉树 每一层代表是二维数组的 每一行, 在这二叉树每一层的行中,从左往右的节点 代表二维数组的 每一列

  2. 当二叉树从 左子树 开始递归, 意味着先存储 每一行二叉树的节点

  3. 当二叉树向 右子树 开始递归, 意味着存储 每一列二叉树的节点

  4. 最终当整个二叉树完全递归就意味着 全部的节点都存储在 这个二维数组 (二维顺序表) 中

鱼式疯言

  if(S.size()==i) {S.add(new ArrayList<Integer>());}

细节处理

每新添加 一行数据 ,需要 扩容 ,就是需要再 实例化一个顺序表 ,已有的行数就 不需要了

小伙伴们有没有发现,二叉树的层序遍历,本质上和我们的 完全二叉树的定义 是一样的,都是满足 自上而下,自左而右 的特点

六. 二叉树遍历的应用

学习完了 二叉树遍历,小伙伴们是时候 牛刀小试 一下了 💞 💞 💞

1. 习题一:

1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为()

A: ABDHECFG

B: ABCDEFGH

C: HDBEAFCG

D: HDEBFGCA

题目解析

我们知道了二叉树的 层序遍历 , 并且小伙伴们还有没有注意一个条件就是 完全二叉树

完全二叉树的特点就是 自上而下自左而右 节点不间断

那么我们不妨画个草图

在这里插入图片描述

画出草图,我们就很明显的知道了,答案选: A

2. 习题二:

2.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()

A: E

B: F

C: G

D: H

题目解析:

此题题目就是 答案, 我们知道前序遍历, 是从 根节点 开始的 , 所以 第一个访问出来的节点 就是我们的 根节点

故:答案选:A

3. 习题三:

3.设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为()

A: adbce

B: decab

C: debac

D: abcde

题目解析:

此题的精髓就在于,我们要根据 中序遍历 和 后序遍历画出草图, 根据草图得到我们的 前序遍历

在这里插入图片描述
画草图的方法:

方法: 先根据后序遍历寻找 根节点

对于 后序遍历 来说:根节点是从右往左 , 然后结合 中序遍历的特点 来确定 左右节点 的位置

故此题答案选: D

4. 习题四:

4.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列为()

A: FEDCBA

B: CBAFED

C: DEFCBA

D: ABCDEF

题目解析 :

此题的精髓就在于,我们要根据 中序遍历 和 后序遍历画出草图, 根据草图得到我们的 层序遍历

在这里插入图片描述

依照上一题的方法,我们成功画出草图,最终得到我们的层序遍历

故答案选: A

鱼式疯言

独家秘方:

  1. 对于我们已知 前序和中序 遍历,我们的方法就是根据 前序遍历从左往右 找根节点,然后结合 中序遍历 画出草图
  1. 对于 我们已知的 后序和中序 遍历, 我们的方法是 根据 后序遍历 从右往左找根节点 , 然后结合中序遍历 画出草图

对于上述题目来说, 画图是 根本

总结

  • . 二叉树的遍历初识: 我们通过基本的概念知道了二叉树是通过一定 规则和方向 来遍历我们 每一个节点

  • . 前序遍历 : 本源是 根-左-右的方向遍历

  • . 中序遍历: 本源是 左-根-右的方向遍历

  • .后序遍历 : 本质上还是根据 左-右-根的方向遍历

  • . 层序遍历: 遵循一个 自上而下, 自左而右 的顺序遍历

  • . 二叉树遍历的应用 : 我们主打一个对于这四种遍历的性质的理解和应用,来画图解题

如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正

希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力 💖 💖 💖

在这里插入图片描述

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

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

相关文章

Linux入门攻坚——24、BIND编译安装、Telnet和OpenSSH

BIND编译安装 对于没有rpm包&#xff0c;需要源代码编译安装。 1、下载源代码&#xff1a;bind-9.12.2-P1.tar.gz&#xff0c;解压&#xff1a;tar -xf bind-9.12.2-P1.tar.gz 2、完善环境&#xff1a; 1&#xff09;增加用户组named&#xff1a;groupadd -g 53 named 2&…

正邦科技(day4)

烧录 一、烧录固件二、 通讯模块升级1&#xff1a;USB的方式升级固件2&#xff1a;通过mqtt的方式升级固件3&#xff1a;切换环境 三、 烧录WiFi1&#xff1a;短接2&#xff1a;烧录脚本 设备注意事项&#xff1a; 第一种方式&#xff1a;通信模组和MCU都可以统一烧录BoodLoade…

Vue进阶之Vue无代码可视化项目(一)

Vue无代码可视化项目 项目搭建初始步骤拓展:工程项目从0-1项目规范化package.jsoncpell.jsoncustom-words.txtts-eslint规则.eslintrc.cjsgit钩子检查有没有问题type-checkspellchecklint:stylehusky操作安装pre-commitpnpm的commit规范package.json:commitlint.config.cjs安装…

11.3 冒泡排序

目录 11.3 冒泡排序 11.3.1 算法流程 11.3.2 效率优化 11.3.3 算法特性 11.3 冒泡排序 冒泡排序&#xff08;bubble sort&#xff09;通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样&#xff0c;因此得名冒泡排序。 如图 11-4 所示…

数据结构与算法笔记:基础篇 - 链表(上):如何实LRU缓存淘汰算法

概述 本章聊聊 “链表” 这个数据结构。学习链表有什么作用&#xff1f; 我们先来讨论一个经典的链表应用场景&#xff0c;那就是 LRU 缓存淘汰算法。 缓存是一种提高数据读取性能的技术&#xff0c;在硬件设计、软件开发中有着非常广泛地应用&#xff0c;比如场景的 CPU 缓…

登录安全分析报告:小米官网注册

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …

[12] 使用 CUDA 加速排序算法

使用 CUDA 加速排序算法 排序算法被广泛用于计算应用中有很多排序算法&#xff0c;像是枚举排序或者说是秩排序、冒泡排序和归并排序&#xff0c;这些排序算法具有不同的&#xff08;时间和空间&#xff09;复杂度&#xff0c;因此对同一个数组来说也有不同的排序时间&#xf…

使用Streamlit和MistralAI创建AI聊天机器人应用

大家好&#xff0c;创建交互式和用户友好型的应用程序通常需要复杂的框架和耗时的开发过程。Streamlit是一个Python库&#xff0c;它简化了以数据为重点的网络应用程序的创建过程&#xff0c;使开发人员和数据科学家能够快速将他们的想法转化为交互式仪表盘和原型。本文将介绍使…

使用autodl服务器进行模型训练

1.注册并且选择一个服务器租用 2.点击jupyter lab进入服务器内部 3.把yolov5-master这个的压缩文件上传到jupyter的文件列表中 4.打开终端 (1)查看目录 ls (2)解压yolov5-master(1) unzip "yolov5-master (1).zip" 可以看到解压成功&#xff01; (3)进入yolov5-m…

开源与闭源 AI 模型:发展路径的比较与前瞻

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

VB.net进行CAD二次开发(四)

netload不能弹出对话框&#xff0c;参考文献2 参考文献1说明了自定义菜单的问题&#xff0c;用的是cad的系统命令 只要加载了dll&#xff0c;自定义的命令与cad的命令同等地位。 这时&#xff0c;可以将自定义菜单的系统命令替换为自定义命令。 <CommandMethod("Add…

【如何在日志中输出精确到毫秒的时间戳】

1. 需求 在日志中输出精确到毫秒级的时间戳&#xff0c; 格式为&#xff1a;%Y-%m-%d %H:%M:%S.%MS 如&#xff1a;2024-05-30 22:33:25.821 2. 代码实现 #include <iostream> #include <chrono> #include <iomanip> #include <sstream> #include &…

HTTP请求拦截器链

文章目录 HTTP请求拦截器链需求定义写一个Controller方法接口写三个http请求拦截器把拦截器加入到配置中&#xff0c;并且配置拦截规则在postman里面发送请求&#xff0c;看下测试结果是否正确第三个参数的作用 HTTP请求拦截器链 需求定义 我们写一个包含三个HTTP请求拦截器的…

硬币检测电路设计

一、来源&#xff1a;凡亿教育 第一场&#xff1a;硬币检测装置原理分析、电路设计以及器件选型_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Zh4y1V7Px/?p1&vd_source43eb1cb50ad3175d7f3b9385905cd88f 二、开发软件&#xff1a;KEIL MDK 三、主控芯片&#…

vs2019 c++20 规范 STL库中关于时间的模板

在学习线程的时候&#xff0c;一些函数会让线程等待或睡眠一段时间。函数形参是时间单位&#xff0c;那么在 c 中是如何记录和表示时间的呢&#xff1f;以下给出模板简图&#xff1a; 谢谢

CMake的作用域:public/private/interface

在 CMake 中&#xff0c;public、private和 interface是用来指定目标属性的作用域的关键字&#xff0c;这三个有什么区别呢&#xff1f;这些关键字用于控制属性的可见性和传递性&#xff0c;影响了目标之间的依赖关系和属性传递。 public 如果在一个目标上使用 public关键字时…

mysql去除重复数据

需求描述 doc表有很多重复的title,想去除掉重复的记录 表结构 CREATE TABLE doc (id INT PRIMARY KEY,title VARCHAR(255),content TEXT );去重SQL -- 创建临时表 CREATE TEMPORARY TABLE temp_doc AS SELECT * FROM doc WHERE 10;-- 插入唯一的记录&#xff08;每个title最…

FPGA定点数FFT过后转换为浮点数与Matlab计算的FFT结果进行比对

目录 1.前言2.FPGA的testbench中如何读取数据文件3.FPGA的testbench中如何将输出数据存储在文件中4.Matlab去读取testbench存储的文件数据4.1纯数字不带编码4.2 带编码的数据&#xff0c;如定点数 微信公众号获取更多FPGA相关源码&#xff1a; 1.前言 前面一篇文章讲了&…

基础—SQL—DCL(数据控制语言)小结

一、总结 在SQL分类中的DCL语句部分&#xff0c;主要讲到了两个部分的知识。 1、用户管理 用户管理&#xff0c;主要是管理哪些用户可以访问当前 mysql 数据库。 包括&#xff1a;创建用户、修改用户密码以及删除用户 2、权限控制 权限管理&#xff0c;主要是控制我们当前用户…

iOS App Tech Support(URL)

咪萌是一个语音类交友直播App&#xff0c;分成红艳知己&#xff0c;点唱大厅&#xff0c;歌手驻唱等不同房间分类&#xff0c;广场可以看到其他人发的一些动态&#xff0c;一个非常不错的App 如果您有任何疑问&#xff0c;您可以留言或者将问题发送至我们的邮箱。 我们会第一时…