二叉搜索树的实现(C++)
前言
二叉搜索树(搜索二叉树,Binary search tree)是一种特殊的二叉树。其规则为:左子树的值一定小于等于根,右子树的值一定大于等于根,并且左右子树也为搜索二叉树。
二叉搜索树的插入
1.若树为空,插入的数据为根节点的数据
2.若树不为空,按照二叉搜索树的性质,判断节点的值与插入值的大小关系。若大于节点的值则往右边走。若小于节点的值则往左边走
二叉搜索树的搜索
1.从根节点开始查找,小于节点值则往左边,大于节点值则往右边。找到就返回
2.若遍历完都没有找到,即返回找不到
二叉搜索树的删除(重点)
1.删除叶子节点(既没有左右孩子),直接删除然后将其父亲节点的指针赋值为nullptr
2.删除只有一个孩子的节点,直接删除然后将孩子连接至父亲节点
3.删除有两个孩子的节点,不能直接删除。从这个节点出发寻找左子树的最大值(既最右节点)或者右子树的最小值(既最左节点)。将找到的值的赋值给要删除的节点,然后删除我们找到的节点,这样就能保证不会破坏二叉搜索树的性质。
补充:若删除根节点的话,要单独处理一下
代码实现
template<class K>
struct BSNode
{K _val;BSNode<K>* _left;BSNode<K>* _right;BSNode(const K& key):_val(key), _left(nullptr), _right(nullptr){ }
};template<class K>
class BSTree
{//typedef BSNode<K> Node;using Node = BSNode<K>;//新的重命名方式
public:void Insert(const K& key)//搜索二叉树的插入(不允许冗余){Node* cur = _root;if (!cur){_root = new Node(key);}else{Node* parent = cur;while (cur){if (cur->_val < key){parent = cur;cur = cur->_right;}else{parent = cur;cur = cur->_left;}}if (parent->_val < key){parent->_right = new Node(key);}else if (parent->_val > key){parent->_left = new Node(key);}elsereturn;}}bool Search(const K& key)//查找{Node* cur = _root;while (cur){if (cur->_val < key){cur = cur->_right;}else if (cur->_val > key){cur = cur->_left;}elsereturn true;}return false;}//搜索二叉树的删除void Erase(const K& key){Node* cur = _root;Node* parent = cur;//先找到相应位置while (cur){if (cur->_val < key){parent = cur;cur = cur->_right;}else if (cur->_val > key){parent = cur;cur = cur->_left;}elsebreak;}if (!cur)return;//进行删除if (!cur->_left && !cur->_right)//没有孩子{if (cur == _root)//若删除根节点{delete _root;_root = nullptr;}else{if (parent->_left == cur)parent->_left = nullptr;elseparent->_right = nullptr;delete cur;cur = nullptr; // 显式置空}}else if (!cur->_left || !cur->_right)//有一个孩子{if (cur == _root)//若删除根节点{if (cur->_left){_root = cur->_left;delete cur;cur = nullptr; // 显式置空}else{_root = cur->_right;delete cur;cur = nullptr; // 显式置空}}else{if (!cur->_left){if (parent->_left == cur){parent->_left = cur->_right;delete cur;cur = nullptr; // 显式置空}else{parent->_right = cur->_right;delete cur;cur = nullptr; // 显式置空}}else{if (parent->_left == cur){parent->_left = cur->_left;delete cur;cur = nullptr; // 显式置空}else{parent->_right = cur->_left;delete cur;cur = nullptr; // 显式置空}}}}else//有两个孩子{//寻找左子树最大值(或右子树最小值)来替换curNode* Replace = cur->_left;Node* Replacep = cur;while (Replace->_right){Replacep = Replace;Replace = Replace->_right;}swap(Replace->_val, cur->_val);if(Replacep->_right == Replace)Replacep->_right = Replace->_left;elseReplacep->_left = Replace->_left;delete Replace;}}void Inorder()//中序遍历{_Inorder(_root);cout << endl;}private:void _Inorder(Node* root)//中序遍历{if (!root)return;_Inorder(root->_left);cout << root->_val<<" ";_Inorder(root->_right);}Node* _root = nullptr;
};
相关文章:
二叉搜索树的实现(C++)
前言 二叉搜索树(搜索二叉树,Binary search tree)是一种特殊的二叉树。其规则为:左子树的值一定小于等于根,右子树的值一定大于等于根,并且左右子树也为搜索二叉树。 二叉搜索树的插入 1.若树为空…...
vue2老版本 npm install 安装失败_安装卡主
vue2老版本 npm install 安装失败_安装卡主 特别说明:vue2老版本安装慢、运行慢,建议升级vue3element plus vite 解决方案1: 第一步、修改npm 镜像为国内镜像 使用淘宝镜像: npm config set registry https://registry.npmmir…...
【MySQL】索引篇
1.什么时候适用索引? 字段有唯一限制,比如商品编码经常用于where查询条件的字段经常用于group by和order by 的字段 2.什么时候不需要创建索引? 字段中存在大量重复经常更新的字段表数据太少的时候 where条件、group by,order by里…...
Arduino 第十六章:pir红外人体传感器练习
Arduino 第十六章:PIR 传感器练习 一、引言 在 Arduino 的众多有趣项目中,传感器的应用是非常重要的一部分。今天我们要学习的主角是 PIR(被动红外)传感器。PIR 传感器能够检测人体发出的红外线,常用于安防系统、自动…...
鸿蒙面试题
1.0penHarmony的系统架构是怎样的? 2.电话服务的框架? 3.OpenHarmony与HarmonyOS有啥区别?...
Rust 语言入门(一):打印与格式化输出
对于初学者来说,掌握 Rust 的基本 I/O 操作是入门的第一步。本篇博客将介绍 Rust 语言的打印机制,包括基本的 print!、println! 宏,格式化输出方式,并探讨其底层原理。 Rust 的基本打印 在 Rust 中,最常见的输出方式…...
vue3.x 的 toRef详细解读
在 Vue 3.x 中,toRef 是一个用于创建响应式引用的工具函数。它可以将一个响应式对象的某个属性转换为一个独立的 ref 对象,同时保持与原始属性的响应式连接。以下是 toRef 的详细解读和示例。 1. toRef 的作用 核心功能 toRef 用于从响应式对象&#x…...
wordpress资讯类网站整站打包
wordpress程序,内置了价值499元的模板.但是有了模板没有全自动采集相信大多数人都搞不懂,目录那么多,全靠原创几乎是不可能的事情,除非你是大公司,每人控制一个板块, 这套源码里面最有价值的应该是这个采集…...
GitHub基本操作及Git简单命令
GitHub简介 GitHub就是一个远程仓库,远程仓库可以理解为就是一个可以保存自己代码的地方,在实际开发当中一个项目往往是有多个人来共同协作开发完成的,那么就需要一个统一代码保存的地方,而GitHub就是起到一个共享和汇总代码的作…...
记一次MySQL故障解决
记一次MySQL故障解决 1 故障现象2 故障排查2.1 查看MySQL服务状态2.2 查看服务日志 3 解决方法3.1 增加 wait_timeout 和 interactive_timeout 参数的值,确保连接不会因超时而被关闭:3.2 检查服务已经恢复正常,不过以上只是临时修改ÿ…...
DeepSeek-R1私有化部署教程 | Linux服务器搭建AI大语言模型
**云服务器用LinuxDockerOllamaOpenWebUI部署DeepSeek-R1大语言模型(LLMs),DeepSeek本地化部署教程(在自己电脑上部署也可以参考此教程)。**超详细教程,手把手。 在当今数字化时代,大型语言模型…...
「软件设计模式」桥接模式(Bridge Pattern)
深入解析桥接模式:解耦抽象与实现的艺术 一、模式思想:正交维度的优雅解耦 桥接模式(Bridge Pattern)通过分离抽象(Abstraction)与实现(Implementation),使二者可以独立…...
【Flink快速入门-5.流处理之多流转换算子】
流处理之多流转换算子 实验介绍 前面实验中介绍的算子已经能够满足我们的大部分开发需求了,但是在实际工作中有时候还会遇到一些业务场景,例如需要摄入多个输入流并将其合并处理,或者需要将一条输入流分割为多条子流,在不同的子…...
react传递函数与回调函数原理
为什么 React 允许直接传递函数? 回调函数核心逻辑 例子:父组件控制 Modal 的显示与隐藏 // 父组件 (ParentComponent.tsx) import React, { useState } from react; import { Modal, Button } from antd; import ModalContent from ./ModalContent;co…...
华为云kubernetes基于keda自动伸缩deployment副本(监听redis队列长度)
1 概述 KEDA(Kubernetes-based Event-Driven Autoscaler,网址是https://keda.sh)是在 Kubernetes 中事件驱动的弹性伸缩器,功能非常强大。不仅支持根据基础的CPU和内存指标进行伸缩,还支持根据各种消息队列中的长度、…...
Spring源码分析のBean扫描流程
文章目录 前言一、scanCandidateComponents1.1 isCandidateComponent1.1.1、排除/包含过滤器1.1.2、条件装配1.1.3、重载一1.1.4、重载二1.1.5、补充:Lookup注解 总结 前言 原生的Spring在构造ApplicationContext时,会调用refresh方法。其中就包含了扫描…...
Ubuntu安装docker:docker-desktop : 依赖: docker-ce-cli 但无法安装它、无法定位软件包 docker-ce-cli
具体错误 sudo apt-get install ./docker-desktop-amd64.deb [sudo] password for weiyu: 正在读取软件包列表... 完成 正在分析软件包的依赖关系树... 完成 正在读取状态信息... 完成 注意,选中 docker-desktop 而非 ./docker-desktop-amd64.de…...
基于大数据的奥运会获奖数据分析系统设计与实现
【大数据】基于大数据的奥运会获奖数据分析系统设计与实现(完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统通过集成先进的数据抓取、处理、存储与可视化技术,为深入理解奥运会…...
数据结构 堆和priority_queue
一、堆的定义 堆(heap),是⼀棵有着特殊性质的完全⼆叉树,可以⽤来实现优先级队列(priorityqueue)。 堆需要满⾜以下性质: 1. 是⼀棵完全⼆叉树; 2. 对于树中每个结点,如…...
Dockerfile 编写推荐
一、导读 本文主要介绍在编写 docker 镜像的时候一些需要注意的事项和推荐的做法。 虽然 Dockerfile 简化了镜像构建的过程,并且把这个过程可以进行版本控制,但是不正当的 Dockerfile 使用也会导致很多问题。 docker 镜像太大。如果你经常使用镜像或者…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
