数据结构--二叉树的创建和遍历
目录
引入
定义
性质
二叉树的创建
迭代法
注意事项：
递归法
注意事项：
二叉树的遍历
深度优先
广度优先
先序遍历（前序遍历）
中序遍历
后序遍历
层序遍历
查找树结构中是否存在某数值
方法一：
方法二：
引入
二叉树（Binary Tree）是数据结构中的一种重要类型。
定义
二叉树是指树中节点的度不大于2的有序树，即每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉树可以是空树，或者由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。
性质
在二叉树的第i层上至多有2^(i-1)个节点（i≥1）。
深度为h的二叉树中至多含有2^h-1个节点（h≥1）。当二叉树为满二叉树时，节点数达到最大值。
若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
具有n个节点的满二叉树深为log2(n+1)（这里的log是以2为底的对数）。
对于完全二叉树，若其节点按从上至下从左至右的顺序编号，则对于任意节点i：
- 若i=1，则该节点为根节点，无双亲节点。
- 若2i≤n（n为节点总数），则有编号为2i的左节点，否则没有左节点。
- 若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。
二叉树的创建
如下就是一个二叉树 ，那么如何去构建这么一个二叉树呢？
如上，A、B、C、D......等都是一个节点，要想去构建二叉树，那么就要有额外的类或方法去创建这些节点，在此给出一个 TreeNode类：
public class TreeNode{public int data;public TreeNode left;public TreeNode right;public TreeNode(int data){this.data=data;}//重写toString()方法@Overridepublic String toString(){return "data:"+data+"left:"+left+"right:"+right;}//数据的类型决定数据在内存中的存储形式
}
在这里给出两种方式去构建二叉树：迭代法和递归法。
迭代法
public class BinaryTree {public TreeNode root;public void insert(int data) {//新建一个节点TreeNode newNode = new TreeNode(data);//放入第一个节点if (root == null) {root = newNode;return;}TreeNode currentNode = root;while (true) {if (newNode.data < currentNode.data) {if (currentNode.left != null) {currentNode = currentNode.left;} else {currentNode.left = newNode;return;}} else {if (currentNode.right != null) {currentNode = currentNode.right;} else {currentNode.right = newNode;return;}}}}
}注意事项：
-
TreeNode类的定义：上述代码中假设已经存在一个名为
TreeNode的类，它应该包含一个名为data的整型字段，以及两个名为left和right的TreeNode类型字段（分别表示左子节点和右子节点）。这个类通常还会包含一个构造函数来初始化这些字段。 -
二叉树的性质：上述
insert方法实现的是一个二叉搜索树（Binary Search Tree, BST）的插入操作。在二叉搜索树中，每个节点的左子树只包含小于节点值的元素，而右子树只包含大于或等于节点值的元素。这种性质使得二叉搜索树在查找、插入和删除操作上具有较高的效率。 -
无限循环的安全性：虽然上述代码中使用了一个无限循环（
while (true)），但由于在每个条件分支中都有return语句来终止方法，因此这个循环是安全的。在实际编程中，如果循环条件不是显而易见的，或者循环体中的逻辑比较复杂，那么使用明确的循环条件（如do-while循环或带有break语句的while循环）可能会使代码更加清晰易懂。
递归法
//递归实现树的构建
// 递归插入方法
public void build(int data) {root = insertRec(root, data);
}// 辅助递归函数
private TreeNode insertRec(TreeNode root, int data) {// 如果当前节点为空，创建一个新节点并返回它if (root == null) {root = new TreeNode(data);return root;}// 否则，递归地将数据插入到左子树或右子树中if (data < root.data) {root.left = insertRec(root.left, data);} else {root.right = insertRec(root.right, data);}// 返回（未修改的）当前节点（对于递归调用者很重要）return root;
}注意事项：
-
递归的基本情况和递归情况：在
insertRec方法中，基本情况是当当前节点为空时创建一个新节点。递归情况是当当前节点不为空时，根据数据的大小将数据插入到左子树或右子树中。 -
返回当前节点：在递归方法中，返回当前节点（即使它可能没有被修改）是非常重要的。这是因为递归调用需要返回更新后的子树的根节点，以保持树的结构。
-
Java的引用传递：在Java中，对象是通过引用传递的。这意味着当我们将一个对象传递给一个方法时，我们实际上是在传递对象的引用（而不是对象本身）。因此，当我们在
insertRec方法中修改root.left或root.right时，我们实际上是在修改调用者传递的引用所指向的对象。 -
构建二叉搜索树：这段代码实现了一个二叉搜索树的构建过程。在二叉搜索树中，每个节点的左子树只包含小于节点值的元素，而右子树只包含大于或等于节点值的元素。这种性质使得二叉搜索树在查找、插入和删除操作上具有较高的效率。
二叉树的遍历
二叉树的遍历分为深度优先和广度优先两大类。
深度优先
- 先序遍历：按照“根节点-左子树-右子树”的顺序遍历二叉树。
- 中序遍历：按照“左子树-根节点-右子树”的顺序遍历二叉树。在二叉搜索树（BST）中，中序遍历的结果是一个有序序列。
- 后序遍历：按照“左子树-右子树-根节点”的顺序遍历二叉树。
广度优先
- 层序遍历：按照二叉树的层次从上到下、从左到右遍历节点。
接下来实现上述遍历算法：
先序遍历（前序遍历）
//先序遍历
public void beforOrder(TreeNode root){if(root==null){return;}System.out.println(" "+root.data);beforOrder(root.left);beforOrder(root.right);
}中序遍历
//中序遍历
public void inOrder(TreeNode root){if(root==null){return;}inOrder(root.left);System.out.println(" "+root.data);inOrder(root.right);
}后序遍历
//后序遍历
public void afterOrder(TreeNode root){if(root==null){return;}afterOrder(root.left);afterOrder(root.right);System.out.println(" "+root.data);
}层序遍历
//广度优先
public void leveOrder(){LinkedList<TreeNode> queue=new LinkedList<>();queue.add(root);while(!queue.isEmpty()){root=queue.pop();System.out.println(" "+root.data);if(root.left!=null){queue.add(root.left);}if(root.right!=null){queue.add(root.right);}}
}查找树结构中是否存在某数值
方法一：
//查询是否存在某个数值（true/false）
public boolean isNode(TreeNode root,int data){if(root==null){return false;}if(root.data==data){return true;}return isNode(root.left,data) || isNode(root.right,data);
}方法二：
// 递归搜索方法
public boolean search(int data) {return searchRec(root, data);
}private boolean searchRec(TreeNode root, int data) {// 如果当前节点为空，说明没有找到目标值if (root == null) {return false;}// 如果当前节点的值等于目标值，返回trueif (root.data == data) {return true;}// 如果目标值小于当前节点的值，递归地在左子树中搜索if (data < root.data) {return searchRec(root.left, data);}else{// 如果目标值大于当前节点的值，递归地在右子树中搜索return searchRec(root.right, data);}}上述就是二叉树相关操作啦！o(*￣▽￣*)ブ
相关文章：
数据结构--二叉树的创建和遍历
目录 引入 定义 性质 二叉树的创建 迭代法 注意事项： 递归法 注意事项： 二叉树的遍历 深度优先 广度优先 先序遍历（前序遍历） 中序遍历 后序遍历 层序遍历 查找树结构中是否存在某数值 方法一： 方法…...
)
CEF127 编译指南 Linux篇 - 安装Git和Python(三)
1. 引言 在前面的文章中，我们已经完成了基础开发工具的安装和配置。接下来，我们需要安装两个同样重要的工具：Git 和 Python。这两个工具在 CEF 的编译过程中扮演着关键角色。Git 负责管理和获取源代码，而 Python 则用于运行各种编…...
计算机网络的类型
目录 按覆盖范围分类 个人区域网（PAN） 局域网（LAN） 城域网（MAN） 4. 广域网（WAN） 按使用场景和性质分类 公网（全球网络） 外网 内网（私有网…...
)
Web入门(学习笔记)
Web入门 文章目录 Web入门SpringSpringBootWeb入门HTTP协议HTTP-概述HTTP特点 HTTP-请求协议HTTP-请求数据格式 HTTP-响应协议响应状态码 HTTP-协议解析 Web服务器-TomcatWeb服务器简介基本使用Tomcat文件夹目录解析常见问题Tomcat部署项目 入门程序解析**内嵌的Tomcat服务器**…...
mind+自定义库编写注意事项
在mind图形化命令编写中，main.ts 文件是通过图形化编程工具生成 C 代码，然后将生成的 C 代码上传到 Arduino Uno 上执行。 这些由main.ts定义的图形化代码通过生成的代码，需要包含调用arduinoc/libraries文件夹的*.h和*.cpp文件&#…...
jQuery零基础入门速通（上）
大家好，我是小黄。 在前端开发的世界里，jQuery以其简洁的语法和强大的功能，一直是许多开发者手中的利器。它不仅简化了HTML文档遍历和操作、事件处理、动画以及Ajax交互，还极大地提高了开发效率。本文将带你走进jQuery的世界&…...
计算机网络-Wireshark探索IPv4
使用工具 Wiresharkcurl(MacOS)traceroute: This lab uses “traceroute” to find the router level path from your computer to a remote Internet host. traceroute is a standard command-line utility for discovering the Internet paths that your computer uses. It i…...
【05】Selenium+Python 两种文件上传方式（AutoIt）
上传文件的两种方式 一、input标签上传文件 可以用send_keys方法直接上传文件 示例代码 input标签上传文件import time from selenium import webdriver from chromedriver_py import binary_path # this will get you the path variable from selenium.webdriver.common.by i…...
《构建 C++分布式计算框架：赋能人工智能模型并行训练》
在人工智能迅猛发展的今天，模型训练所需的计算资源呈指数级增长。为了高效地支持人工智能模型在多节点、多 GPU/CPU 集群上的并行训练，基于 C构建分布式计算框架成为了关键之举。 一、分布式计算框架的核心意义 随着人工智能模型复杂度的不断攀升&…...
分支定价算法Branch and price
分支定价算法是进阶版的列生成算法，是用来专门求解整数规划问题的。 目录 1.整数规划与线性规划的关系 2.限制主问题（RLMP）求得整数解 3.B&P用法：以VRPTW为例 列生成是求解线性规划问题的算法，通过不断往限制主…...
【信息系统项目管理师】第5章：信息系统工程 考点梳理
文章目录 5.1 软件工程5.1.1 架构设计1、软件架构风格2、软件架构评估 5.1.2 需求分析1、需求的层次2、需求过程（重点）3、UML事务、关系和视图4、面向对象分析 5.1.3 软件设计1、结构化设计2、面向对象设计3、设计模式 5.1.4 软件实现1、软件配置管理2、…...
kdump调试分析（适用于麒麟，ubuntu等OS）
1. kdump基本原理 1.1 内核崩溃处理机制 当 Linux 系统内核发生崩溃时，通常会触发 panic，系统停止正常运行。Kdump 在这种情况下： 使用一个备用的内核（称为 crash kernel）来启动最小化的环境。从崩溃的主内核中复制内存内容（转储文件）。将转储文件保存到预定义的存储位…...
Ubuntu在NVME硬盘使用Systemback安装记录
问题 使用Systemback重装系统找不到NVME硬盘。 0.使用Systemback制作iso后，制作启动盘 1.插入启动盘进入live mode模式 2.安装gparted sudo apt-get update sudo apt-get install gparted3.使用gparted对待分区硬盘进行分区 gparted按照你希望的分区方式分区即…...
C++多态的实现原理
【欢迎关注编码小哥，学习更多实用的编程方法和技巧】 1、类的继承 子类对象在创建时会首先调用父类的构造函数 父类构造函数执行结束后，执行子类的构造函数 当父类的构造函数有参数时，需要在子类的初始化列表中显式调用 Child(int i) : …...
com.github.gavlyukovskiy依赖是做什么的呢？
p6spy-spring-boot-starter 是一个Spring Boot的starter，用于集成P6Spy库。P6Spy是一个开源的数据库连接池代理工具，它可以拦截和记录所有的SQL语句及其执行时间，从而帮助开发者进行SQL性能分析和调试。 功能概述 SQL日志记录： P…...
QChart数据可视化
目录 一、QChart基本介绍 1.1 QChart基本概念与用途 1.2 主要类的介绍 1.2.1 QChartView类 1.2.2 QChart类 1.2.3QAbstractSeries类 1.2.4 QAbstractAxis类 1.2.5 QLegendMarker 二、与图表交互 1. 动态绘制数据 2. 深入数据 3. 缩放和滚动 4. 鼠标悬停 三、主题 …...
离线安装 Docker-IO：详细步骤指南
离线安装 Docker-IO：详细步骤指南 一、准备工作1.1 下载 Docker 离线安装包1.2 准备安装环境1.3 配置防火墙和 SELinux（可选）二、上传和解压离线安装包2.1 上传安装包2.2 解压安装包三、安装 Docker-IO3.1 移动 Docker 文件到系统目录3.2 配置 Docker 服务3.3 赋予服务文件执…...
梯度爆炸与消失
梯度爆炸和梯度消失 一、概念解析 （一）梯度爆炸 定义 在深度神经网络训练的反向传播过程中，梯度爆炸是指梯度的值过大的现象。这会使模型的参数更新出现异常。 产生原因 深层网络与链式法则：深度神经网络按链式法则计算某层权重…...
动捕 动作捕捉学习笔记
2024.11.28 实时动作捕捉 ThreeDPoseTracker VRMLiveViewer 实现虚拟主播跳舞自由_哔哩哔哩_bilibili blender 手工操作，不能渲染到原视频 【快速有效】三分钟学会，通过blender把网上视频武术动作捕捉绑定到3D角色上,需要使用Auto-rig Pro(ARP…...
spark3.x之后时间格式数据偶发报错org.apache.spark.SparkUpgradeException
3.x之后如果你去处理2.x生成的时间字符串数据，很容易遇到一个问题 Error operating ExecuteStatement: org.apache.spark.SparkUpgradeException: You may get a different result due to the upgrading of Spark 3.0: Fail to parse 20200725__cb90fcc3_8006_46…...
计算机网络（二）
ip地址：11010010：01011110:00100100:00010100 子网掩码:11111111:11111111:11111111:11000000 and ：11010010：01011110：00100100：00000000 210.94.36.0的下一站为R1 因为255为11111111 192为ÿ…...
如何在Spark中使用gbdt模型分布式预测
这目录 1 训练gbdt模型2 第三方包python环境打包3 Spark中使用gbdt模型3.1 spark配置文件3.2 主函数main.py 4 spark任务提交 1 训练gbdt模型 我们可以基于lightgbm快速的训练一个gbdt模型，训练相对比较简单，只要把训练样本处理好，几行代码可…...
llamaindex实战-ChatEngine-ReAct Agent模式
概述 ReAct 是一种基于Agent的聊天模式，构建在数据查询引擎之上。对于每次聊天交互，代理都会进入一个 ReAct 循环： 首先决定是否使用查询引擎工具并提出适当的输入 （可选）使用查询引擎工具并观察其输出 决定是否重复…...
关于音频 DSP 的接口种类以及其应用场景介绍
在音频系统中，DSP（数字信号处理器）扮演着重要角色，通常会通过不同的接口与音频系统中的其他组件（如功放、扬声器、音频源等）进行连接。以汽车应用场景为例，以下是一些常见的接口类型分类及其介绍…...
DLL中的inline static成员变量：Windows开发中的常见陷阱
在Windows平台进行C开发时，DLL（动态链接库）是一个非常重要的概念。它让我们能够实现代码的模块化和动态加载，提高了程序的灵活性和维护性。然而，当我们在DLL中使用C17引入的inline static成员变量时，可能会…...
7. 现代卷积神经网络
文章目录 7.1. 深度卷积神经网络（AlexNet）7.2. 使用块的网络（VGG）7.3. 网络中的网络（NiN）7.4. 含并行连结的网络（GoogLeNet）7.5. 批量规范化7.5.1. 训练深层网络7.5.2. 批量规范化层…...
软件测试丨Pytest生命周期与数据驱动
Pytest的生命周期概述 Pytest 是一个强大的测试框架，提供了丰富的特性来简化测试执行。它的生命周期包括多个阶段，涉及从准备测试、执行测试到报告结果的完整流程。因此，理解Pytest的生命周期将帮助我们更好地设计和管理测试用例。 开始阶段…...
Python 网页控制自动化 getEdgeDriver
透过python 使用 edge 执行自动化时，原来的代码 出现报错了 执行报错啦：message info 如下显示 HTTPSConnectionPool(hostmsedgedriver.azureedge.net, port443): Max retries exceeded with url: /130.0.2849/edgedriver_win64.zip (Caused by NewConn…...
白鹿 Hands-on：消除冷启动——基于 Amazon Lambda SnapStart 轻松打造 Serverless Web 应用（二）
文章目录 前言一、前文回顾二、在 Lambda 上运行2.1、查看 Amazon SAM template2.2、编译和部署到 Amazon Lambda2.3、功能测试与验证 三、对比 Snapstart 效果四、资源清理五、实验总结总结 前言 在这个环节中，我们将延续《白鹿 Hands-on：消除冷启动——…...
pandas read_csv读取中文内容文件报错UnicodeDecodeError: ‘utf-8‘ codec can‘t decode byte
先用如下代码检查编码格式 import chardet# 检测文件编码 with open("data.csv", "rb") as f:result chardet.detect(f.read())print(result["encoding"]) # 打印检测到的编码我检查后我的文件编码格式是ISO-8859-1，因此读取文件时…...
LoRA微调原理 代码实践
LoRA（Low-Rank Adaptation）作为一种用于微调 LLM（大语言模型）的流行技术，最初由来自微软的研究人员在论文《 LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS 》中提出。不同于其他技术，LoRA 不是调整…...
数据结构--树二叉树顺序结构存储的二叉树（堆）
前言 前面我们学习了顺序表、链表、栈和队列，这些都是线性的数据结构。今天我们要来学习一种非线性的数据结构——树。 树的概念及结构 树的概念 树是一种非线性的数据结构，是由n（n≥0）个有效结点组成的一个具有层次关系的集合…...
mongodb shard 分片集群基础概念
目录 一、shard 集群 二、Config Server 1、config.shards 2、config.database 3、config.collection 4、config.chunks 5、config.settings 6、其他 三、shard机制 1、Primary Shard 2、Shard Key 2.1 范围分片 2.2 哈希分片 2.3 Shard Key重定义 2.4 版本约束…...
Streamlit 应用从本地部署到服务器并进行访问
目录 1 部署 Streamlit 应用到服务器2 配置服务器允许远程访问3 使用反向代理4 使用 HTTPS5 总结 1 部署 Streamlit 应用到服务器 1 选择一个服务器平台 首先，你需要选择一个服务器平台来部署你的 Streamlit 应用。常见的选择包括： 云服务器：…...
大数据新视界 -- 大数据大厂之 Hive 数据压缩：优化存储与传输的关键（上）（19/ 30）
💖💖💖亲爱的朋友们，热烈欢迎你们来到 青云交的博客！能与你们在此邂逅，我满心欢喜，深感无比荣幸。在这个瞬息万变的时代，我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
Java开发中对List＜Map＜String, Object＞＞集合去重并按大小拆分子列表
Java开发中对List< Map< String, Object > >集合去重并按大小拆分子列表 一、使用场景二、实现步骤三、相关知识四、代码示例 一、使用场景 在处理大量List<Map<String, Object>>集合的数据时，为确保数据的唯一性，需要先根据Ma…...
vue3项目搭建-6-axios 基础配置
axios 基础配置 安装 axios npm install axios 创建 axios 实例，配置基地址，配置拦截器,目录：utils/http.js 基地址：在每次访问时，自动作为相对路径的根 // axios 基础封装 import axios from "axios";…...
git 学习笔记
目录 一、git 前期准备 1、托管平台的账号注册（以gitee码云为demo） 2、本地个人电脑配置 （1）配置用户属性 （2）配置SSH密钥 二、git 工作流程图 三、git 提交命令 （1）git ini…...
Y20030019 基于java+jsp+mysql的微信小程序校园二手交易平台的设计与实现 源代码 文档
旅游度假区微信小程序 1.摘要2. 系统开发的目的和意义3.系统功能4.界面展示5.源码获取 1.摘要 随着移动互联网的发展，微信小程序已经成为人们生活中不可或缺的一部分。微信小程序的优点在于其快速、轻量、易用，用户无需下载即可使用，节省了用…...
Cookie跨域
跨域：跨域名（IP） 跨域的目的是共享Cookie。 session操作http协议，每次既要request，也要response，cookie在创建的时候会产生一个字符串然后随着response返回。 全网站的各个页面都会带着登陆的时候的cookie …...
Mybatis：CRUD数据操作之删除一行数据
Mybatis基础环境准备请看：Mybatis基础环境准备 本篇讲解Mybati数据CRUD数据操作之单条删除数据 当用户点击了该按钮，就会将改行数据删除掉。那我们就需要思考，这种删除是根据什么进行删除呢？是通过主键id删除，因为id是…...
【机器学习】CatBoost 模型实践：回归与分类的全流程解析
一. 引言 本篇博客首发于掘金 https://juejin.cn/post/7441027173430018067。 PS：转载自己的文章也算原创吧。 在机器学习领域，CatBoost 是一款强大的梯度提升框架，特别适合处理带有类别特征的数据。本篇博客以脱敏后的保险数据集为例&#x…...
MySQL中如何减少回表
在MySQL中，回表是指在使用非聚集索引进行查询时，如果需要获取的数据不在索引页中，就需要根据索引页中的指针返回到数据表中查找实际数据行的过程。这个过程会增加额外的磁盘I/O操作，降低查询性能，特别是在查询大量数据…...
10. 函数
一、什么是函数 函数也是对象，对象是内存中专门用来存储数据的一块区域。函数可以用来保存一些可执行代码的，并且可以在需要时，对这些语句进行多次调用。 二、创建函数 创建函数也称为定义函数。我们可以使用 def 关键字来定义函数ÿ…...
计算机网络：数据链路层（二）
网课资源： 湖科大教书匠 1、网络适配器和MAC地址 习题1 1 以下哪个地址是广播MAC地址 A. 00-00-00-00-00-00 B. AB-CD-EF-11-22-33 C. FF-FF-FF-FF-FF-FF D. 29-29-29-29-29-29 2 以下哪个地址是多播MAC地址 A. 00-00-00-00-00-00 B. A9-8B-7C-6D-5E-4F C. FF-FF-…...
一万台服务器用saltstack还是ansible?
一万台服务器用saltstack还是ansible? 选择使用 SaltStack 还是 Ansible 来管理一万台服务器，取决于几个关键因素，如性能、扩展性、易用性、配置管理需求和团队的熟悉度。以下是两者的对比分析，帮助你做出决策： SaltStack&…...
设计模式学习之——观察者模式
观察者模式是一种行为型设计模式，它用于在对象之间建立一对多的依赖关系。 一、定义与角色 定义： 观察者模式定义了一种一对多的依赖关系，让多个观察者对象同时监听某一个主题对象。这个主题对象在状态发生变化时，会通知所有观察…...
服务器实现ssh证书登录
1.生成公钥和私钥 ssh-keygen -t rsa 提示默认生成位置为/root/.ssh/id_rsa ,直接回车。(也可以自己修改) 提示输入证书的密码，可以留空，建议输入，如果输入了，则需要再次确认，记住这个证书密码（证书再加…...
python基础知识精讲
Python基础知识精讲 Python是一种广泛使用的高级编程语言，以其清晰的语法和代码可读性而闻名。它支持多种编程范式，包括面向对象、命令式、函数式和过程式编程。以下是Python基础知识的详细讲解。 1. Python简介 Python由Guido van Rossum创建&#x…...
分页查询日期格式不对
方式一:在属性上加入注解，对日期进行格式化 方式二:在 WebMvcConfiguration 中扩展Spring MVC的消息转换器，统一对日期类型进行格式化处理 /*** 统一转换处理扩展spring mvc* 后端返回前端的进行统一转化处理* param converters*/Overrideprotected voi…...