当前位置: 首页 > news >正文

数据结构-二分搜索树(Binary Search Tree)

一,简单了解二分搜索树

树结构:

问题:为什么要创造这种数据结构

1,树结构本身是一种天然的组织结构,就好像我们的文件夹一样,一层一层的.


2,树结构可以更高效的处理问题

二,二分搜索树的基础

1、二叉树
 

2,二叉树的重要特性

满二叉树

总结:

1. 叶子结点出现在二叉树的最底层,除叶子结点之外的其它结点都有两个孩子结点。
2. 一个层数为k 的满二叉树总结点数为:
3. 第i层上的结点数为:
4. 一个层数为k的满二叉树的叶子结点个数(也就是最后一层):
4、二叉树不一定是“满”的

3,二分搜索树

(注意:存储的元素必须具有可比性)

1,向二分搜索树添加元素

2,向二分搜索树查询操作

1,递归终止的条件 : if(node == null ) return false;
2,递归操作
if (ele.compareTo(node.ele) < 0) {
return search(node.left, ele);
} else if (ele.compareTo(node.ele) > 0) {
return search(node.right, ele);
} else {
return true;
}

3,二分搜索树的遍历操作

遍历操作:把树中所有节点都访问一遍

1前序遍历,

2中序遍历,

3后序遍历

4层序遍历(广度优先)

(代码,会在后面一起展现.)

4,二分搜索树寻找最大值,最小值

同样的原理找出二分搜素树中最大的元素,这里不在过多赘述.

5,删除操作
情况一:(叶子结点)

情况二、(非叶子结点)

删除后


6,删除二分搜索树中的节点

情况一:
 

情况二、
 

情况三:左右孩子都不为空的情况

使用Hibbard Deletion
 

三,用代码实现二分搜索树.实现相关功能.

(由于功能实现较多,代码较长)

其中包含是前面的各种功能操作的实现,包括,前,中,后,层,序把遍历,删除,添加,等等操作.需要的同学可以仔细查看.

mport java.nio.channels.Pipe;
import java.util.*;
import java.util.stream.Collectors;// 二分搜索树
public class BinarySearchTree<T extends Comparable<T>> {// 定义树的结点public class Node {T val;Node left; //  左孩子Node right; // 右孩子public Node(T val) {this.val = val;}}// 定义树的根private Node root;// 树根// 统计树中结点的个数private int size;// 树中结点的个数public BinarySearchTree() {this.root = null;this.size = 0;}// 判断树是否为空public boolean isEmpty() {return this.size == 0;}// 获取树中元素的个数public int getSize() {return this.size;}// 向树中添加元素public void add(T val) {this.size++;this.root = add(this.root, val);}/*** 添加的递归方法** @param node 树的根结点* @param val  添加的值*/private Node add(Node node, T val) {//递归终止的条件if (node == null) {Node leafNode = new Node(val);return leafNode;}// 递归操作if (node.val.compareTo(val) > 0) {node.left = add(node.left, val);} else {node.right = add(node.right, val);}return node;}// 将树中所有结点进行遍历--中序遍历( 深度优先搜索 DFS,使用的栈来实现)public String middleTravel() {List<T> result = new ArrayList<>();middleTravel(this.root, result);return result.stream().map(item -> item.toString()).collect(Collectors.joining(","));}/*** 中序遍历** @param node 树的根结点*/private void middleTravel(Node node, List<T> result) {// 递归终止的条件if (node == null) {return;}// 递归操作// 先遍历左子树middleTravel(node.left, result);//  打印当前值result.add(node.val);//  再遍历右子树middleTravel(node.right, result);}public String beforeTravel() {List<T> result = new ArrayList<>();beforeTravel(this.root, result);return result.stream().map(item -> item.toString()).collect(Collectors.joining(","));}/*** 前序遍历** @param node 树的根结点*/private void beforeTravel(Node node, List<T> result) {// 递归终止的条件if (node == null) {return;}// 递归操作//  打印当前值result.add(node.val);// 先遍历左子树beforeTravel(node.left, result);//  再遍历右子树beforeTravel(node.right, result);}public String afterTravel() {List<T> result = new ArrayList<>();afterTravel(this.root, result);return result.stream().map(item -> item.toString()).collect(Collectors.joining(","));}/*** 后序遍历** @param node 树的根结点*/private void afterTravel(Node node, List<T> result) {// 递归终止的条件if (node == null) {return;}// 递归操作// 先遍历左子树afterTravel(node.left, result);//  再遍历右子树afterTravel(node.right, result);//  打印当前值result.add(node.val);}// 查找的方法public boolean contains(T val) {return contains(this.root, val);}/*** 从以node为根的二分搜索树中查找元素val** @param node 根节点* @param val  要搜索的值* @return*/private boolean contains(Node node, T val) {// 递归到底的情况if (node == null) {return false;}// 递归操作if (node.val.compareTo(val) == 0) {return true;} else if (node.val.compareTo(val) > 0) {return contains(node.left, val);} else {return contains(node.right, val);}}// 树的层序遍历(广度优先搜索  BFS,使用队列来实现)public String levelTravel() {List<String> list = new ArrayList<>();// 1、 创建一个队列Queue<AbstractMap.SimpleEntry<Integer, Node>> queue = new LinkedList<>();// 2、将根结点入入队if (this.root != null) {queue.offer(new AbstractMap.SimpleEntry<>(1, this.root));}// 3、遍历队列while (!queue.isEmpty()) {AbstractMap.SimpleEntry<Integer, Node> temp = queue.poll();Node value = temp.getValue();int key = temp.getKey();//3-1  先将内容保存list.add(value.val.toString() + "------" + key);// 3-2  判断左子树是否为空,不为空就入队if (value.left != null) {queue.offer(new AbstractMap.SimpleEntry<>(key + 1, value.left));}// 3-3 判断右子树是否为空,不为空就入队if (value.right != null) {queue.offer(new AbstractMap.SimpleEntry<>(key + 1, value.right));}}return list.stream().collect(Collectors.joining(","));}public List<List<T>> levelOrder() {// 返回值类型是啥,就创建啥List<List<T>> result = new ArrayList<>();// 1、 创建一个队列Queue<AbstractMap.SimpleEntry<Integer, Node>> queue = new LinkedList<>();// 2、将根结点入入队if (this.root != null) {queue.offer(new AbstractMap.SimpleEntry<>(1, this.root));}while (!queue.isEmpty()) {AbstractMap.SimpleEntry<Integer, Node> temp = queue.poll();Node value = temp.getValue();int key = temp.getKey();//3-1  先将内容保存if(result.get(key-1)==null){result.add(new ArrayList<>());}result.get(key-1).add(value.val);// 3-2  判断左子树是否为空,不为空就入队if (value.left != null) {queue.offer(new AbstractMap.SimpleEntry<>(key + 1, value.left));}// 3-3 判断右子树是否为空,不为空就入队if (value.right != null) {queue.offer(new AbstractMap.SimpleEntry<>(key + 1, value.right));}}return result;}// Pair对public class Pair<Node> {private Node value; // 保存值private int key; // 保存层public Pair(Node value, int key) {this.value = value;this.key = key;}public Node getValue() {return value;}public int getKey() {return key;}}// 从二分搜索树中找最小值(在整棵树的最左边)public T getMinVal() {// 判断树是否为空if (this.root == null) {return null;}Node curNode = this.root;while (curNode.left != null) {curNode = curNode.left;}return curNode.val;}public T getMinValDG() {// 判断树是否为空if (this.root == null) {return null;}return getMinValDG(this.root).val;}/*** 从以node为根的二分搜索树中查找最小值** @param node 树的根节点*/private Node getMinValDG(Node node) {//递归终止的条件if (node.left == null) {return node;}// 递归操作return getMinValDG(node.left);}// 从二分搜索树中找最 大值(在整棵树的最右边)public T getMaxVal() {// 判断树是否为空if (this.root == null) {return null;}Node curNode = this.root;while (curNode.right != null) {curNode = curNode.right;}return curNode.val;}public T getMaxValDG() {// 判断树是否为空if (this.root == null) {return null;}return getMaxValDG(this.root).val;}private Node getMaxValDG(Node node) {//递归终止的条件if (node.right == null) {return node;}// 递归操作return getMinValDG(node.right);}// 从以this.root为根的二分搜索树中删除最小的结点public void removeMinNode() {if (this.root == null) {return;}this.root = removeMinNode(this.root);}/*** 从以node为根的二分搜索树中删除最小的节点** @param node 树的根节点* @return 删除之后的树的根节点*/private Node removeMinNode(Node node) {// 递归终止的条件if (node.left == null) {this.size--;return node.right;}// 递归操作node.left = removeMinNode(node.left);return node;}// 删除操作public void remove(T val) {if (!contains(val)) {return;}this.root = remove(this.root, val);}/*** 从以node为根的二分搜索树中删除元素val的节点** @param node 树的根节点* @param val  删除的值* @return*/private Node remove(Node node, T val) {// 递归终止的条件if (node == null) {return null;}if (node.val.compareTo(val) == 0) {// 更新sizethis.size--;if (node.right == null) {//1、右子树为空return node.left;} else if (node.left == null) {//2、左子树为空return node.right;} else {// 3、左右子树都不为空// 3-1 找到删除节点的后继Node suffixNode = getMinValDG(node.right);// 3-2 更新suffixNode的左右子树
//                suffixNode.right = removeMinNode(node.right);suffixNode.right = remove(node.right, getMinValDG(node.right).val);suffixNode.left = node.left;this.size++;// 3-3 返回suffixNodereturn suffixNode;}}// 递归操作if (node.val.compareTo(val) > 0) {node.left = remove(node.left, val);} else {node.right = remove(node.right, val);}return node;}}

相关文章:

数据结构-二分搜索树(Binary Search Tree)

一,简单了解二分搜索树 树结构: 问题:为什么要创造这种数据结构 1,树结构本身是一种天然的组织结构,就好像我们的文件夹一样,一层一层的. 2,树结构可以更高效的处理问题 二,二分搜索树的基础 1、二叉树 2,二叉树的重要特性 满二叉树 总结: 1. 叶子结点出现在二叉树的最…...

YOLO如何训练自己的模型

目录 步骤 一、打标签 二、数据集 三、跑train代码出模型 四、跑detect代码出结果 五、详细操作 步骤 一、打标签 &#xff08;1&#xff09;在终端 pip install labelimg &#xff08;2&#xff09;在终端输入labelimg打开 如何打标签&#xff1a; 推荐文章&#xf…...

05 EXTI外部中断

一、中断系统 中断系统&#xff1a;管理和执行中断的逻辑结构。中断&#xff1a;在主程序运行过程中&#xff0c;出现了特定的中断触发条件——中断源&#xff0c;使得CPU暂停当前正在运行的程序&#xff0c;转而去处理中断程序&#xff0c;处理完成后又返回原来被暂停的位置继…...

2024.2.23

1.1.1 信号默认、捕获、忽略处理(普通信号) #include <myhead.h> void handler(int signo) {if(signoSIGINT){printf("用户键入 ctrlc\n");} } int main(int argc, const char *argv[]) {//忽略信号if(signal(SIGINT,SIG_IGN)SIG_ERR){perror("signal er…...

PHP实现分离金额和其他内容便于统计计算

得到的结果可以粘贴到excel计算 <?php if($_GET["x"] "cha"){ $tips isset($_POST[tips]) ? $_POST[tips] : ; $pattern /(\d\.\d|\d)/; $result preg_replace($pattern, "\t\${1}\t", $tips); echo "<h2><strong>数…...

基础数据结构和算法《》

递归 1.递归应该一种比较常见的实现一些特殊代码逻辑时需要做的&#xff0c;但常常也是最绕的一种方式&#xff0c;在解释递归 之前&#xff0c;我们用循环和递归来做个比较1.1.如果你打开一扇门后&#xff0c;同样发现前方也有一扇们&#xff0c;紧接着你又打开下一扇门...直…...

[设计模式Java实现附plantuml源码~行为型]对象间的联动~观察者模式

前言&#xff1a; 为什么之前写过Golang 版的设计模式&#xff0c;还在重新写Java 版&#xff1f; 答&#xff1a;因为对于我而言&#xff0c;当然也希望对正在学习的大伙有帮助。Java作为一门纯面向对象的语言&#xff0c;更适合用于学习设计模式。 为什么类图要附上uml 因为很…...

vue3+js 实现记住密码功能

常见的几种实现方式 1 基于spring security 的remember me 功能 ​​​​​​​ localStorage 除非主动清除localStorage 里的信息 &#xff0c;不然永远存在&#xff0c;关闭浏览器之后下次启动仍然存在 存放数据大小一般为5M 不与服务器进行交互通信 cookies 可以…...

基于单片机的太阳能电池板自动跟踪系统的研究

摘要 伴随着人类社会的发展,人口基数越来越大,电量消耗巨大,传统发电原 料污染环境的同时,可用量日益减少,给人类未来生产生活带来了一定的威胁, 因而解决日益剧增的用电量,寻求一种新能源显得极其重要。论文正是基于此 背景下,针对当前太阳能电池板采光率低、自动化水…...

React 模态框的设计(二)

自定义组件是每个前端开发者必备的技能。我们在使用现有框架时难免有一些超乎框架以处的特别的需求&#xff0c;比如关于弹窗&#xff0c;每个应用都会用到&#xff0c;但是有时我们使用的框架中提供的弹窗功能也是功能有限&#xff0c;无法满足我们的应用需求&#xff0c;今天…...

操作符详解3

✨✨ 欢迎大家来到莉莉的博文✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 前面我们已经讲过算术操作符、赋值操作符、逻辑操作符、条件操作符和部分的单目操作 符&#xff0c;今天继续介绍一部分。 目录 1.操作符的分类 2…...

【C语言基础】:操作符详解(一)

文章目录 操作符详解1. 操作符的分类2. 二进制和进制转换2.1 什么是二进制、八进制、十进制、十六进制2.1.1 二进制和进制转换2.1.2 二进制转十进制2.2.3 二进制转八进制2.2.4 二进制转十六进制 3. 源码、反码、补码4. 移位操作符4.1 左移操作符4.2 右移操作符 5. 位操作符&…...

通俗易懂分析:Vite和Webpack的区别

1、对项目构建的理解 先从浏览器出发&#xff0c; 浏览器是由浏览器内核和JS引擎组成&#xff1b;浏览器内核编译解析html代码和css代码&#xff0c;js引擎编译解析JavaScript代码&#xff1b;所以从本质上&#xff0c;浏览器只能识别运行JavaScript、CSS、HTML代码。 而我们在…...

OpenCart程序结构与业务逻辑

一、程序业务逻辑说明 在 OpenCart 中&#xff0c;index.php 文件是整个应用程序的入口文件&#xff0c;它负责初始化应用程序并调度请求。以下是 index.php 文件加载执行的流程&#xff1a; 1. **设置路径常量&#xff1a;** - index.php 首先定义了一些重要的路径常量&…...

软件License授权原理

软件License授权原理 你知道License是如何防止别人破解的吗?本文将介绍License的生成原理,理解了License的授权原理你不但可以防止别人破解你的License,你甚至可以研究别人的License找到它们的漏洞。喜欢本文的朋友建议收藏+关注,方便以后复习查阅。 什么是License? 在…...

C/C++实现老鼠走迷宫

老鼠形象可以辨认&#xff0c;可以用上下左右操纵老鼠;正确检测结果&#xff0c;若老鼠在规定的时间内走到粮仓&#xff0c;提示成功&#xff0c;否则提示失败。代码分为3个文件&#xff1a;main.cpp、play.h、play.cpp。 main.cpp: #include <iostream> #include <…...

[Linux]文件基础-如何管理文件

回顾C语言之 - 文件如何被写入 fopen fwrite fread fclose fseek … 这一系列函数都是C语言中对文件进行的操作&#xff1a; int main() {FILE* fpfopen("text","w");char str[20]"write into text";fputs(str,fp);fclose(fp);return 0; }而上…...

bat 查找文件所在

脚本 在批处理文件&#xff08;.bat&#xff09;中查找文件所在的目录&#xff0c;你可以使用dir命令结合循环和条件语句来实现。以下是一个简单的示例&#xff0c;演示如何在批处理文件中查找指定文件并输出其所在目录&#xff1a; echo off setlocal enabledelayedexpansio…...

程序员的守护神:为何电脑永不熄灭?

在这个信息时代&#xff0c;程序员成了推动社会进步的“隐形英雄”。他们通宵达旦&#xff0c;手指在键盘上跳跃&#xff0c;创造出一个个令人惊叹的数字世界。有趣的是&#xff0c;你可能注意到了一个现象&#xff1a;程序员似乎总是不关电脑。这并非他们对电脑上瘾&#xff0…...

Kafka快速实战以及基本原理详解

Kafka快速实战以及基本原理详解 基本概念 Kafka是一个分布式、支持分区、多副本&#xff0c;基于ZK的分布式消息系统&#xff0c;最大的特性就是可以实时的处理大量数据以满足各种需求场景&#xff0c;比如Hadoop的批处理系统、低延迟的实时系统、Storm/Spark流式处理引擎、日…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...