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

二叉搜索树的实现(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++)

前言 二叉搜索树&#xff08;搜索二叉树&#xff0c;Binary search tree&#xff09;是一种特殊的二叉树。其规则为&#xff1a;左子树的值一定小于等于根&#xff0c;右子树的值一定大于等于根&#xff0c;并且左右子树也为搜索二叉树。 二叉搜索树的插入 1.若树为空&#xf…...

vue2老版本 npm install 安装失败_安装卡主

vue2老版本 npm install 安装失败_安装卡主 特别说明&#xff1a;vue2老版本安装慢、运行慢&#xff0c;建议升级vue3element plus vite 解决方案1&#xff1a; 第一步、修改npm 镜像为国内镜像 使用淘宝镜像&#xff1a; npm config set registry https://registry.npmmir…...

【MySQL】索引篇

1.什么时候适用索引&#xff1f; 字段有唯一限制&#xff0c;比如商品编码经常用于where查询条件的字段经常用于group by和order by 的字段 2.什么时候不需要创建索引&#xff1f; 字段中存在大量重复经常更新的字段表数据太少的时候 where条件、group by&#xff0c;order by里…...

Arduino 第十六章:pir红外人体传感器练习

Arduino 第十六章&#xff1a;PIR 传感器练习 一、引言 在 Arduino 的众多有趣项目中&#xff0c;传感器的应用是非常重要的一部分。今天我们要学习的主角是 PIR&#xff08;被动红外&#xff09;传感器。PIR 传感器能够检测人体发出的红外线&#xff0c;常用于安防系统、自动…...

鸿蒙面试题

1.0penHarmony的系统架构是怎样的? 2.电话服务的框架? 3.OpenHarmony与HarmonyOS有啥区别?...

Rust 语言入门(一):打印与格式化输出

对于初学者来说&#xff0c;掌握 Rust 的基本 I/O 操作是入门的第一步。本篇博客将介绍 Rust 语言的打印机制&#xff0c;包括基本的 print!、println! 宏&#xff0c;格式化输出方式&#xff0c;并探讨其底层原理。 Rust 的基本打印 在 Rust 中&#xff0c;最常见的输出方式…...

vue3.x 的 toRef详细解读

在 Vue 3.x 中&#xff0c;toRef 是一个用于创建响应式引用的工具函数。它可以将一个响应式对象的某个属性转换为一个独立的 ref 对象&#xff0c;同时保持与原始属性的响应式连接。以下是 toRef 的详细解读和示例。 1. toRef 的作用 核心功能 toRef 用于从响应式对象&#x…...

wordpress资讯类网站整站打包

wordpress程序&#xff0c;内置了价值499元的模板.但是有了模板没有全自动采集相信大多数人都搞不懂&#xff0c;目录那么多&#xff0c;全靠原创几乎是不可能的事情&#xff0c;除非你是大公司&#xff0c;每人控制一个板块&#xff0c; 这套源码里面最有价值的应该是这个采集…...

GitHub基本操作及Git简单命令

GitHub简介 GitHub就是一个远程仓库&#xff0c;远程仓库可以理解为就是一个可以保存自己代码的地方&#xff0c;在实际开发当中一个项目往往是有多个人来共同协作开发完成的&#xff0c;那么就需要一个统一代码保存的地方&#xff0c;而GitHub就是起到一个共享和汇总代码的作…...

记一次MySQL故障解决

记一次MySQL故障解决 1 故障现象2 故障排查2.1 查看MySQL服务状态2.2 查看服务日志 3 解决方法3.1 增加 wait_timeout 和 interactive_timeout 参数的值&#xff0c;确保连接不会因超时而被关闭&#xff1a;3.2 检查服务已经恢复正常&#xff0c;不过以上只是临时修改&#xff…...

DeepSeek-R1私有化部署教程 | Linux服务器搭建AI大语言模型

**云服务器用LinuxDockerOllamaOpenWebUI部署DeepSeek-R1大语言模型&#xff08;LLMs&#xff09;&#xff0c;DeepSeek本地化部署教程&#xff08;在自己电脑上部署也可以参考此教程&#xff09;。**超详细教程&#xff0c;手把手。 在当今数字化时代&#xff0c;大型语言模型…...

「软件设计模式」桥接模式(Bridge Pattern)

深入解析桥接模式&#xff1a;解耦抽象与实现的艺术 一、模式思想&#xff1a;正交维度的优雅解耦 桥接模式&#xff08;Bridge Pattern&#xff09;通过分离抽象&#xff08;Abstraction&#xff09;与实现&#xff08;Implementation&#xff09;&#xff0c;使二者可以独立…...

【Flink快速入门-5.流处理之多流转换算子】

流处理之多流转换算子 实验介绍 前面实验中介绍的算子已经能够满足我们的大部分开发需求了&#xff0c;但是在实际工作中有时候还会遇到一些业务场景&#xff0c;例如需要摄入多个输入流并将其合并处理&#xff0c;或者需要将一条输入流分割为多条子流&#xff0c;在不同的子…...

react传递函数与回调函数原理

为什么 React 允许直接传递函数&#xff1f; 回调函数核心逻辑 例子&#xff1a;父组件控制 Modal 的显示与隐藏 // 父组件 (ParentComponent.tsx) import React, { useState } from react; import { Modal, Button } from antd; import ModalContent from ./ModalContent;co…...

华为云kubernetes基于keda自动伸缩deployment副本(监听redis队列长度)

1 概述 KEDA&#xff08;Kubernetes-based Event-Driven Autoscaler&#xff0c;网址是https://keda.sh&#xff09;是在 Kubernetes 中事件驱动的弹性伸缩器&#xff0c;功能非常强大。不仅支持根据基础的CPU和内存指标进行伸缩&#xff0c;还支持根据各种消息队列中的长度、…...

Spring源码分析のBean扫描流程

文章目录 前言一、scanCandidateComponents1.1 isCandidateComponent1.1.1、排除/包含过滤器1.1.2、条件装配1.1.3、重载一1.1.4、重载二1.1.5、补充&#xff1a;Lookup注解 总结 前言 原生的Spring在构造ApplicationContext时&#xff0c;会调用refresh方法。其中就包含了扫描…...

Ubuntu安装docker:docker-desktop : 依赖: docker-ce-cli 但无法安装它、无法定位软件包 docker-ce-cli

具体错误 sudo apt-get install ./docker-desktop-amd64.deb [sudo] password for weiyu: 正在读取软件包列表... 完成 正在分析软件包的依赖关系树... 完成 正在读取状态信息... 完成 注意&#xff0c;选中 docker-desktop 而非 ./docker-desktop-amd64.de…...

基于大数据的奥运会获奖数据分析系统设计与实现

【大数据】基于大数据的奥运会获奖数据分析系统设计与实现&#xff08;完整系统源码开发笔记详细部署教程&#xff09;✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统通过集成先进的数据抓取、处理、存储与可视化技术&#xff0c;为深入理解奥运会…...

数据结构 堆和priority_queue

一、堆的定义 堆&#xff08;heap&#xff09;&#xff0c;是⼀棵有着特殊性质的完全⼆叉树&#xff0c;可以⽤来实现优先级队列&#xff08;priorityqueue&#xff09;。 堆需要满⾜以下性质&#xff1a; 1. 是⼀棵完全⼆叉树&#xff1b; 2. 对于树中每个结点&#xff0c;如…...

Dockerfile 编写推荐

一、导读 本文主要介绍在编写 docker 镜像的时候一些需要注意的事项和推荐的做法。 虽然 Dockerfile 简化了镜像构建的过程&#xff0c;并且把这个过程可以进行版本控制&#xff0c;但是不正当的 Dockerfile 使用也会导致很多问题。 docker 镜像太大。如果你经常使用镜像或者…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...