C++------利用C++实现二叉搜索树【数据结构】

文章目录

  • 二叉搜索树
    • 概念
    • 二叉搜索树的操作
      • 查找
      • 插入
      • 删除
    • 二叉搜索树的应用

二叉搜索树

概念

什么是二叉搜索树，二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。
在这里插入图片描述
上面的就是一棵二叉搜索树，我们还可以发现这棵树走一个中序遍历序列是有序的，所以它又被称为二叉排序树。

二叉搜索树的操作

二叉搜索树的操作主要分为以下几点，查找， 插入，删除。

查找

算法思想：二叉搜索树的查找算法是这样的，从根的地方开始找，如果要找的key比根大就到右子树去找，如果比根小就到左子树找。时间复杂度最差为O(N)最优为O(logn)，如果一棵树走完了还没有找到说明这个数字不在这棵树内。
O(N)时间复杂度是下面这棵树的查找产生的。
在这里插入图片描述
我们要使树的高度保持为logN就必须引入平衡二叉搜索树的概念，这个部分我们在后面的AVL和红黑树部分讲解。
非递归算法：

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

递归算法：
key小于就递归找左树，大于就递归找右树

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

插入

插入分为两种情况：
1、如果树为空，则直接新增节点，赋值给_root指针。
2、树不为空，按二叉搜索树性质查找插入位置，插入新节点。
在这里插入图片描述
非递归算法

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

递归算法

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

删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可能分下面四种情况：
a.要删除的节点无孩子节点
b.要删除的节点只有左孩子节点
c.要删除的节点只有右孩子节点
d.要删除的节点有左右孩子节点
情况b，c可以合成一个情况，那就是只有一个孩子节点。
情况b：删除该节点且是被删除节点的双亲节点指向被删除节点的左孩子节点—直接删除
在这里插入图片描述

情况c：删除该节点且是被删除节点的双亲节点指向被删除节点的右孩子节点—直接删除
在这里插入图片描述

情况d：在它的左子树中寻找最大节点，用它的值填补到被删除节点中，再来处理该节点的删除问题—替换法删除。
在这里插入图片描述
非递归算法：

bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//左边为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else{//左右都不为空//找到左树中的最大值为替代节点Node* parent = cur;Node* leftmax = _root->_left;while (leftmax->_right != nullptr){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_key, leftmax->_key);if (parent->_left == leftmax){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}cur = leftmax;}delete cur;return true;}}return false;}

非递归算法：

//Node*& 引用是关键，没有引用就不会链接起来，不用引用也可以用二级指针。
bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_left){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}

完整代码

namespace name
{template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template <class K>class BSTree{typedef BSTreeNode<K> Node;public://构造函数BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//左边为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else{//左右都不为空//找到左树中的最大值为替代节点Node* parent = cur;Node* leftmax = _root->_left;while (leftmax->_right != nullptr){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_key, leftmax->_key);if (parent->_left == leftmax){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}cur = leftmax;}delete cur;return true;}}return false;}void Inorder(){_Inorder(_root);cout << endl;}bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}private:void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyroot = new Node(root->_key);copyroot->_left = Copy(root->_left);copyroot->_right = Copy(root->_right);return copyroot;}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){return _InsertR(root->_left, key);}else if (root->_key < key){return _InsertR(root->_right, key);}else{return false;}}bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->_key < key){_FindR(root->_right, key);}else if (root->_key > key){_FindR(root->_left, key);}else{return true;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_left){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}Node* _root;};
}

二叉搜索树的应用

应用主要是分为了K模型和KV模型，后面的set为K模型，map为KV模型，具体是这样的：

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
  2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word,chinese>就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word,count>就构成一种键值对。
    上面的代码时K模型的，下面的代码时KV模型的。
namespace name1
{template<class K,class V>struct BSTreeNode{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;BSTreeNode(const K& key,const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}};template <class K,class V>class BSTree{typedef BSTreeNode<K,V> Node;public://构造函数BSTree():_root(nullptr){}BSTree(const BSTree<K,V>& t){_root = Copy(t._root);}BSTree<K,V>& operator=(BSTree<K,V> t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);}void Inorder(){_Inorder(_root);cout << endl;}Node* FindR(const K& key){return _FindR(_root,key);}bool InsertR(const K& key,const V& value){return _InsertR(_root, key,value);}bool EraseR(const K& key){return _EraseR(_root, key);}private:void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyroot = new Node(root->_key);copyroot->_left = Copy(root->_left);copyroot->_right = Copy(root->_right);return copyroot;}bool _InsertR(Node*& root,const K& key,const V& value){if (root == nullptr){root = new Node(key,value);return true;}if (root->_key > key){return _InsertR(root->_left, key, value);}else if (root->_key < key){return _InsertR(root->_right, key, value);}else{return false;}}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_left){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}void _Inorder(Node* root){if (root==nullptr){return;}_Inorder(root->_left);cout << root->_key << ":" << root->_value << endl;_Inorder(root->_right);}Node* _root;};
}

KV模型的测试：

void Test_BSTree7()
{string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };name1::BSTree<string, int> countTree;for (auto& str : arr){//没有找到证明是第一次出现auto ret = countTree.FindR(str);if (ret == nullptr){countTree.InsertR(str, 1);}else{ret->_value++;}}countTree.Inorder();
}
int main()
{//Test_BSTree();//Test_BSTree1();//Test_BSTree2();//Test_BSTree3();//Test_BSTree4();//Test_BSTree5();//Test_BSTree6();Test_BSTree7();return 0;
}

在这里插入图片描述
好的我们下一篇再见！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/97876.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

大语言模型与语义搜索；钉钉个人版启动内测，提供多项AI服务

大语言模型与语义搜索；钉钉个人版启动内测，提供多项AI服务

&#x1f989; AI新闻 &#x1f680; 钉钉个人版启动内测&#xff0c;提供多项AI服务 摘要&#xff1a;钉钉个人版正式开始内测&#xff0c;面向小团队、个人用户、高校大学生等人群。该版本具有AI为核心的功能&#xff0c;包括文生文AI、文生图AI和角色化对话等。用户可通过…
阅读更多...
LeetCode 2236. 判断根结点是否等于子结点之和

LeetCode 2236. 判断根结点是否等于子结点之和

【LetMeFly】2236.判断根结点是否等于子结点之和 力扣题目链接&#xff1a;https://leetcode.cn/problems/root-equals-sum-of-children/ 给你一个 二叉树 的根结点 root&#xff0c;该二叉树由恰好 3 个结点组成&#xff1a;根结点、左子结点和右子结点。 如果根结点值等于…
阅读更多...
学习网络编程No.3【socket理论实战】

学习网络编程No.3【socket理论实战】

引言&#xff1a; 北京时间&#xff1a;2023/8/12/15:32&#xff0c;自前天晚上更新完文章&#xff0c;看了一下鹅厂新出的《扫毒3》摆烂至现在&#xff0c;不知道是长大了&#xff0c;还是近年港片就那样&#xff0c;给我的感觉不是很好&#xff0c;也可能是国内市场对港片不…
阅读更多...
通过微软Azure调用GPT的接口API-兼容平替OpenAI官方的注意事项

通过微软Azure调用GPT的接口API-兼容平替OpenAI官方的注意事项

众所周知&#xff0c;我们是访问不通OpenAI官方服务的&#xff0c;但是我们可以自己通过代理或者使用第三方代理访问接口 现在新出台的规定禁止使用境外的AI大模型接口对境内客户使用&#xff0c;所以我们需要使用国内的大模型接口 国内的效果真的很差&#xff0c;现在如果想使…
阅读更多...
计算机视觉掩模区域与二值图像

计算机视觉掩模区域与二值图像

掩模区域 在图像处理中&#xff0c;我们经常需要对图像中的某些特定区域进行操作&#xff0c;例如对某个区域进行滤波、变换、裁剪或者其他处理。为了实现这些操作&#xff0c;我们需要明确指定这些区域&#xff0c;这就是掩模区域的作用。 掩模区域通常由一个二值图像表示&…
阅读更多...
Android Alarm闹钟API使用心得

Android Alarm闹钟API使用心得

前言 有什么办法可以在不打开App的时候&#xff0c;也能够触发一些操作呢&#xff1f;比如说发送通知&#xff0c;解决这个需求的办法有很多种选择&#xff0c;比如说官方推荐的WorkManager API&#xff0c;可以在后台执行一次性、耗时、定时的任务&#xff0c;但WorkManager是…
阅读更多...
【开源项目】Stream-Query的入门使用和原理分析

【开源项目】Stream-Query的入门使用和原理分析

前言 无意间发现了一个有趣的项目&#xff0c;Stream-Query。了解了一下其基本的功能&#xff0c;可以帮助开发者省去Mapper的编写。在开发中&#xff0c;我们会编写entity和mapper来完成业务代码&#xff0c;但是Stream-Query可以省去mapper&#xff0c;只写entity。 快速入…
阅读更多...
Beats：安装及配置 Metricbeat （一）- 8.x

Beats：安装及配置 Metricbeat （一）- 8.x

在我之前的文章&#xff1a; Beats&#xff1a;Beats 入门教程 &#xff08;一&#xff09;Beats&#xff1a;Beats 入门教程 &#xff08;二&#xff09; 我详细描述了如何在 Elastic Stack 7.x 安装及配置 Beats。在那里的安装&#xff0c;它通常不带有安全及 Elasticsearc…
阅读更多...
OCR相关模块——版面分析技术、表格文本识别

OCR相关模块——版面分析技术、表格文本识别

OCR相关模块——版面分析技术、表格文本识别 版面分析技术表格识别技术 版面分析技术 版面分析模型&#xff1a;飞桨用到了yolov2检测模型&#xff0c;对文档图片中的文本、表格、图片、标题与列表区域进行检测。当前主流是用分割做。 表格识别技术 参考博文
阅读更多...
Matplotlib数据可视化（一）

Matplotlib数据可视化（一）

目录 1.Matplotlib简介 2.Matplotlib绘图基础 2.1 创建画布与子图 2.2 添加画布属性 2.3 绘图的保存与显示 1.Matplotlib简介 Matplotlib是一个用于绘制数据可视化图表的Python库。它提供了广泛的功能和灵活性&#xff0c;可以创建各种类型的图表&#xff0c;包括折线图、…
阅读更多...
MAC QT开发攻略

MAC QT开发攻略

文章目录 基础步骤安装QT、QTCreator安装CMakeNinja 安装Clion编译器在QTCreator中新建项目更改CMake生成器 导入Clion CMake生成文件 基础步骤 安装QT、QTCreator 安装CMake 由于clion需要使用cmake构建 Ninja Ninja下载 安装Clion编译器 Clion 2023.1.3 破解版安装教程…
阅读更多...
微服务中间件--分布式事务

微服务中间件--分布式事务

分布式事务 a.理论基础1) CAP定理2) BASE理论 b.Seata1) XA模式1.a) 实现XA模式 2) AT模式3) TCC模式3.a) 代码实现 4) Saga模式5) 四种模式对比6) TC的异地多机房容灾架构 a.理论基础 1) CAP定理 分布式系统有三个指标&#xff1a; Consistency&#xff08;一致性&#xff…
阅读更多...
基于Java/springboot铁路物流数据平台的设计与实现

基于Java/springboot铁路物流数据平台的设计与实现

摘要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;铁路物流数据平台当然也不能排除在外&#xff0c;从文档信息、铁路设计的统计和分析&#xff0c;在过程中会产生大量的、各…
阅读更多...
GuLi商城-前端基础Vue-使用Vue脚手架进行模块化开发

GuLi商城-前端基础Vue-使用Vue脚手架进行模块化开发

自己亲自实践&#xff1a; mac安装webpack webpack 简介Webpack 是一个非常流行的前端构建工具&#xff0c;它可以将多个模块&#xff08;包括CSS、JavaScript、图片等&#xff09;打包成一个或多个静态资源文件&#xff08;bundle&#xff09;&#xff0c;以便用于部署到生产…
阅读更多...
TiDB 多集群告警监控-中章-融合多集群 Grafana

TiDB 多集群告警监控-中章-融合多集群 Grafana

作者&#xff1a; longzhuquan 原文来源&#xff1a; https://tidb.net/blog/ac730b0f 背景 随着公司XC改造步伐的前进&#xff0c;越来越多的业务选择 TiDB&#xff0c;由于各个业务之间需要物理隔离&#xff0c;避免不了的 TiDB 集群数量越来越多。虽然每套 TiDB 集群均有…
阅读更多...
Elasticsearch复合查询之Boosting Query

Elasticsearch复合查询之Boosting Query

前言 ES 里面有 5 种复合查询&#xff0c;分别是&#xff1a; Boolean QueryBoosting QueryConstant Score QueryDisjunction Max QueryFunction Score Query Boolean Query在之前已经介绍过了&#xff0c;今天来看一下 Boosting Query 用法&#xff0c;其实也非常简单&…
阅读更多...
【Android】设置-显示-屏保-启用时机-去除插入基座相关（不支持该功能的话）

【Android】设置-显示-屏保-启用时机-去除插入基座相关（不支持该功能的话）

设置-显示-屏保-启用时机-去除插入基座相关&#xff08;不支持该功能的话&#xff09; 1-项目场景&#xff1a;2-问题描述3-解决方案&#xff1a;4-代码修改前后效果对比图&#xff1a;代码修改前&#xff1a;代码修改后&#xff1a; 1-项目场景&#xff1a; 展锐平台 2-问题描…
阅读更多...
【Redis】什么是缓存穿透，如何预防缓存穿透？

【Redis】什么是缓存穿透，如何预防缓存穿透？

【Redis】什么是缓存穿透&#xff0c;如何预防缓存穿透&#xff1f; 缓存穿透是指查询一个一定不存在的数据&#xff0c;由于缓存中不存在&#xff0c;这时会去数据库查询查不到数据则不写入缓存&#xff0c;这将导致这个不存在的数据每次请求都要到数据库去查询&#xff0c;这…
阅读更多...
IDEA 如何制作代码补丁？IDEA 生成 patch 和使用 patch

IDEA 如何制作代码补丁？IDEA 生成 patch 和使用 patch

什么是升级补丁&#xff1f; 比如你本地修复的 bug&#xff0c;需要把增量文件发给客户&#xff0c;很多场景下大家都需要手工整理修改的文件&#xff0c;并整理好目录&#xff0c;这个很麻烦。那有没有简单的技巧呢&#xff1f;看看 IDEA 生成 patch 和使用 patch 的使用。 介…
阅读更多...
聊聊智慧城市的发展

聊聊智慧城市的发展

目录 1.智慧城市应该是什么样子 2.智慧城市的实现方案 3.智慧城市会给人们造成的影响 1.智慧城市应该是什么样子 智慧城市是一种基于信息和通信技术的先进城市管理模式&#xff0c;旨在提高城市的运行效率、居民生活质量和可持续发展。智慧城市整合了各种智能设备、传感器、…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023