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

植物大战 二叉搜索树——C++

这里是目录标题

  • 二叉排序树的概念
  • 模拟二叉搜索树
    • 定义节点类
    • insert非递归
    • Find
    • erase(重点)
  • 析构函数
  • 拷贝构造(深拷贝)
  • 赋值构造
  • 递归
    • FindR
    • InsertR
  • 二叉搜索树的应用
    • k模型
    • KV模型

二叉排序树的概念

单纯的二叉树存储数据没有太大的作用。

搜索二叉树作用很大。

搜索二叉树的一般都是用来查找。也可以用来排序,所以也叫做二叉排序树
叫做二叉排序树的原因是因为他中序遍历是有序的。
因为中序的任何一颗子树,都要先走左子树,根,再走右子树。

搜索树因为数据不能冗余,所以也可以用来在插入的时候去重

因为左子树<根<右子树,所以走中序出来,就是排序好的结果。

搜索二叉树要满足:
任意一颗子树都要满足,左子树的值小于根,右子树的值大于根。

优点:查找速度非常快。查找一个值,最多查找高度次,但是它的查找速度是O(n)。因为它有可能是单边树。所以后面会有一个平衡搜索二叉树,不如AVL树,红黑树。

但是我们要从搜索二叉树学起。

模拟二叉搜索树

搜索树的模板参数喜欢用k。k表示关键词的意思,因为喜欢搜索。

定义节点类

需要先定一个节点类。

template<class K>
struct BSTNode
{BSTNode<K>* _pLeft;BSTNode<K>* _pRight;K _key;
};

然后开始写二叉树的增删查改。

insert非递归

原则上插入不能有相同的数据插入。

搜索二叉树的插入顺序会影响效率。一般有序的话会影响。
为了能够找到cur的上一个结点,所以需要再定义个parent的节点。

template <class K>
class BSTree
{typedef BSTreeNode Node;//名字优化
public:bool Insert(const K& key){//如果根节点为空if (_root == nullptr){//new的时候直接可以填值。_root = new Node(key);return bool;}//否则开始Node* cur = _root;Node* parent = nullptr;while (cur){//如果在左边if (key > cur->_key){parent = cur;cur = cur->_right;}//如果在右边else if(key < cur->_key){parent = cur;cur = cur->_left;}//不允许数据冗余else{return false;}}//循环结束,new一个空间.cur = new Node(key);//不知道链接到父亲的左边和右边。//这时候就需要再比较一次if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}
private:Node* _root = nullptr;//根节点
};

C++的根节点是私有的,封装了。所以没办法访问。
可以提供函数。也可以套一层。用_InOrder。
然后把_InOrder函数设为私有。

这样就不用传参了。
在这里插入图片描述

Find

查找值更简单。

   bool Find(const K& key){Node* cur = _root;while(cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}

erase(重点)

搜索树前面的问题都不算问题,最大的问题在于删除数据。删除数据是一个非常麻烦的事情。

1.删叶子节点最好删。
2.删只有一个孩子的也挺好删。只有一个孩子的话,托付给父亲就行,和Linux的托孤有点相似。

总结:没有孩子或者只有一个孩子的时候可以直接删除。
3.不好删的是:
假如有两个孩子则不好删。
在这里插入图片描述

比如删除3。3有两个孩子。3的父亲8管不了两个孩子,因为8右子树也有孩子。

这时候需要用替换法删除。
替换法删除

找谁替换呢?
找左子树的最大值结点。或者右子树的最小值结点。
为什么?
因为一棵搜索二叉树,最左边就是最小的值。最右边是最大的值。

关键理解左子树的最大值结点做父亲可以满足比左子树的任意一个结点的值都大,同时随便拿出左子树的任意一个结点都比右子树小。

理解了上面的。有人找出了规律。
重点
分三种情况
1.假如删除的节点的左子树为空(包括两个节点都为空的情况)。
2.假如删除的节点的右子树为空。(要注意假如是根节点的情况)
3.假如删除的节点的左右子树都不为空(替换法删除)。

具体遇到的bug需要根据实际图来解决。上面的三种情况只是个大概。

//非递归删除erasebool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while(cur){if(key > cur->_key){parent = cur;cur = cur->_right;}else if(key < cur->_key)  {parent = cur;cur = cur->_left;}else{//一个孩子 假如 左为空if(cur->_left == nullptr){if(cur == _root){_root = cur->_right;}else{if(cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}//假如右为空else if(cur->_right == nullptr){if(cur == _root){_root = cur->_left;}else{if(cur == parent->_left){parent->_left =  cur->_left;}else{parent->_right = cur->_left;}}delete cur;}//两个孩子都不为空else{//右子树最小节点替代Node* minParent = cur;Node* minRight = cur->_right;while(minRight->_left){minParent = minRight;minRight = minRight->_left;}swap(minRight->_key, cur->_key);if(minParent->_left == minRight){minParent->_left = 	minRight->_right;}else{minParent->_right = minRight->_right;}delete minRight;}return true;}}return false;}

析构函数

因为没有参数,无法调用析构函数递归,所以需要套一层进行递归。

private:
void DestortTree(Node* root)
{if(root == nullptr)return;DestoryTree(root->_left);DestoryTree(root->_right);delete root;
}
public:
~BSTree()
{DestoryTree(_root);_root = nullptr;
}

拷贝构造(深拷贝)

注意:只要有了拷贝构造就不会再生成默认的构造函数了,所以为了写拷贝构造函数,需要先写一个构造函数。
这时候就要显式写一个构造函数。或者可以用C++11的关键字default来强制生成默认构造

BSTree() = default;

假如我们不写拷贝构造函数,会默认生成构造函数进行浅拷贝。
为了保证树的形状,只能用前序遍历(根 左子树 右子树)递归拷贝

private:
Node* CopyTree(Node* root)
{if(root == nullptr)return nullptr;Node* copyNode = new Node(root->key);copyNode->_left = CopyTree(root->_left);copyNode->_right = CopyTree(root->_right);return copyNode;
}
public:
BSTree(const BSTree<K>&  t)
{_root = CopyTree(t._root);
}

赋值构造

// t1 = t2

BSTree<K>& operator=(BSTree<K> t)
{swap(_root, t._root);return *this;
}

递归

FindR

返回下表的原因是因为要修改,但是这个树不需要修改,修改会破坏掉结构。所以返回bool值就ok。

C++类只要走递归一般都要套一层。不套一层一般都无法走递归。

InsertR

    bool InsertR(const K& key){return _InsertR(_root, key);}bool _InsertR(Node*& root, const K& key){if(root == nullptr){root = new Node(key);return true;}if(root->_key < key)return _InsertR(root->_right, key);else if(root->_key > key)return _InsertR(root->_left, key);elsereturn false;}

二叉搜索树的应用

k模型

k模型只有key作为关键码,结构中只需要存储key杰克,关键码即为需要搜索到的值,比如给一个单词word,检查该单词是否拼写正确。

实质:就是判断K在不在这个系统中

K模型也可以用来去重+排序,

KV模型

KV模型的每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。

1、比如英汉词典中的英文和中文的对应关系,构成了<word,chinese> 的键值对

2、统计单词出现的次数,<word, count>的关系就是一个键值对。

再比如高铁刷身份证进站。

相关文章:

植物大战 二叉搜索树——C++

这里是目录标题二叉排序树的概念模拟二叉搜索树定义节点类insert非递归Finderase(重点)析构函数拷贝构造(深拷贝)赋值构造递归FindRInsertR二叉搜索树的应用k模型KV模型二叉排序树的概念 单纯的二叉树存储数据没有太大的作用。 搜索二叉树作用很大。 搜索二叉树的一般都是用…...

[MatLab]矩阵运算和程序结构

一、矩阵 1.定义 矩阵以[ ]包含&#xff0c;以空格表示数据分隔&#xff0c;以&#xff1b;表示换行。 A [1 2 3 4 5 6] B 1:2:9 %1-9中的数&#xff0c;中间是步长(不能缺省) C repmat(B,3,2) %将B横向重复2次&#xff0c;纵向重复2次 D ones(2,4) …...

【Leedcode】栈和队列必备的面试题(第四期)

【Leedcode】栈和队列必备的面试题&#xff08;第四期&#xff09; 文章目录【Leedcode】栈和队列必备的面试题&#xff08;第四期&#xff09;一、题目二、思路图解1.声明结构体2.循环链表开辟动态结构体空间3.向循环队列插入一个元素4.循环队列中删除一个元素5. 从队首获取元…...

Windows Server 2016搭建文件服务器

1&#xff1a;进入系统在服务器管理器仪表盘中添加角色和功能。 2&#xff1a;下一步。 3&#xff1a;继续下一步。 4&#xff1a;下一步。 5&#xff1a;勾选Web服务器(IIS) 6&#xff1a;添加功能。 7&#xff1a;下一步。 8&#xff1a;下一步。 9&#xff1a;下一步。 10&a…...

零基础学SQL(十一、视图)

目录 前置建表 一、什么是视图 二、为什么使用视图 三、视图的规则和限制 四、视图的增删改查 五、视图数据的更新 前置建表 CREATE TABLE student (id int NOT NULL AUTO_INCREMENT COMMENT 主键,code varchar(255) NOT NULL COMMENT 学号,name varchar(255) DEFAULT NUL…...

web,h5海康视频接入监控视频流记录三(后台node取流)

前端vue&#xff0c;接入ws视频播放 云台控制 &#xff0c;回放预览&#xff0c;都是需要调对应的海康接口。相当于&#xff0c;点击时&#xff0c;请求后台写好的接口&#xff0c;接口再去请求海康的接口 调用云台控制是&#xff0c;操作一次&#xff0c;不会自己停止&#x…...

网络安全从入门到精通:30天速成教程到底有多狠?你能坚持下来么?

毫无疑问&#xff0c;网络安全是当下最具潜力的编程方向之一。对于许多未曾涉足计算机编程的领域「小白」来说&#xff0c;深入地掌握网络安全看似是一件十分困难的事。至于一个月能不能学会网络安全&#xff0c;这个要看个人&#xff0c;对于时间管理不是很高的&#xff0c;肯…...

世界上最流行的编程语言,用户数超过Python,Java,JavaScript,C的总和!

世界上最流行的编程语言是什么&#xff1f; Python? Java? JavaScript? C&#xff1f;都不是&#xff0c;是Excel&#xff01;外媒估计&#xff0c;全球有12亿人使用微软的Office套件&#xff0c;其中估计有7.5亿人使用Excel&#xff01;可是Excel不就是能写点儿公式&#x…...

杂谈:created中两次数据修改,会触发几次页面更新?

面试题&#xff1a;created生命周期中两次修改数据&#xff0c;会触发几次页面更新&#xff1f; 一、同步的 先举个简单的同步的例子&#xff1a; new Vue({el: "#app",template: <div><div>{{count}}</div></div>,data() {return {count…...

原生JS实现拖拽排序

拖拽&#xff08;这两个字看了几遍已经不认识了&#xff09; 说到拖拽&#xff0c;应用场景不可谓不多。无论是打开电脑还是手机&#xff0c;第一眼望去的界面都是可拖拽的&#xff0c;靠拖拽实现APP或者应用的重新布局&#xff0c;或者拖拽文件进行操作文件。 先看效果图&am…...

Coredump-N: corrupted double-linked list

文章目录 问题安装debuginfo之后分析参数确定确定代码逻辑解决问题 今天碰到一例: #0 0xf7f43129 in __kernel_vsyscall () #1 0xf6942b16 in raise () from /lib/libc.so.6 #2 0xf6928e64 in abort () from /lib/libc.so.6 #3 0xf6986e8c in __libc_message () from /lib/li…...

5个好用的视频素材网站

推荐五个高质量视频素材网站&#xff0c;免费、可商用&#xff0c;赶紧收藏起来&#xff01; 1、菜鸟图库 视频素材下载_mp4视频大全 - 菜鸟图库 网站素材非常丰富&#xff0c;有平面、UI、电商、办公、视频、音频等相关素材&#xff0c;视频素材质量很高&#xff0c;全部都是…...

使用码匠连接一切|二

目录 Elasticsearch Oracle ClickHouse DynamoDB CouchDB 关于码匠 作为一款面向开发者的低代码平台&#xff0c;码匠提供了丰富的数据连接能力&#xff0c;能帮助用户快速、轻松地连接和集成多种数据源&#xff0c;包括关系型数据库、非关系型数据库、API 等。平台提供了…...

3.1.1 表的相关设计

文章目录1.表中实体与实体对应的关系2.实际案例分析3.表的实际创建4.总结1.表中实体与实体对应的关系 一对多 如一个班级对应多名学生&#xff0c;一个客户拥有多个订单等这种类型表的建表要遵循主外键关系原则&#xff0c;即在从表创建一个字段&#xff0c;此字段作为外键指向…...

Vue3 企业级项目实战:认识 Spring Boot

Vue3 企业级项目实战 - 程序员十三 - 掘金小册Vue3 Element Plus Spring Boot 企业级项目开发&#xff0c;升职加薪&#xff0c;快人一步。。「Vue3 企业级项目实战」由程序员十三撰写&#xff0c;2744人购买https://s.juejin.cn/ds/S2RkR9F/ 越来越流行的 Spring Boot Spr…...

Swagger2实现配置Header请求头

效果 实现 大家使用swagger肯定知道在代码中会写一个 SwaggerConfig 配置类&#xff0c;如果没有这个类swagger指定也用不起来&#xff0c;所以在swagger中配置请求头也是在这个 SwaggerConfig 中操作。 1、要实现配置请求头在配置swagger的Docket的bean实例中添加一个 globa…...

4-1 SpringCloud快速开发入门:RestTemplate类详细解读

RestTemplate类详细解读 RestTemplate 的 GET 请求 Get 请求可以有两种方式&#xff1a; 第一种&#xff1a;getForEntity 该方法返回一个 ResponseEntity对象&#xff0c;ResponseEntity是 Spring 对 HTTP 请求响应的封装&#xff0c;包括了几个重要的元素&#xff0c;比如响…...

【IDEA】【工具】幸福感UP!开发常用的工具 插件/网站/软件

IDEA 插件 CodeGlance Pro —— 代码地图 CodeGlance是一款非常好用的代码地图插件&#xff0c;可以在代码编辑区的右侧生成一个竖向可拖动的代码缩略区&#xff0c;可以快速定位代码的同时&#xff0c;并且提供放大镜功能。 使用:可以通过Settings—>Other Settings—&g…...

【蓝桥杯集训·每日一题】AcWing 1562. 微博转发

文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴宽搜BFS一、题目 1、原题链接 1562. 微博转发 2、题目描述 微博被称为中文版的 Twitter。 微博上的用户既可能有很多关注者&#xff0c;也可能关注很多其他用户。 因此&am…...

[busybox] busybox生成一个最精简rootfs(下)

书接上回&#xff1a;[busybox] busybox生成一个最精简rootfs(上) 本篇介绍几个rootfs中用到的“不是那么重要的”几个文件。 9 /etc/shadow 和 /etc/passwd 曾经&#xff0c;/etc/passwd 文件用于存储独立 Linux 系统中的所有登录信息。 后来&#xff0c;由于以下原因&…...

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

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

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...