C++:二叉搜索树模拟实现(KV模型)

C++:二叉搜索树模拟实现(KV模型)

  • 前言
  • 模拟实现KV模型
  • 1. 节点封装
  • 2、前置工作(默认构造、拷贝构造、赋值重载、析构函数等)
  • 2. 数据插入(递归和非递归版本)
  • 3、数据删除(递归和非递归版本)
    • 3.1 查找待删除节点位置
    • 3.2 删除数据及相关节点调整
    • 3.3 完整代码以及递归和非递归版本
  • 四、查找数据
  • 五、中序遍历
  • 六、所有代码

前言

 二叉搜索树又称二叉排序树,他对数据有严格的要求,具体表现在以下几个方面:

  1. 如果一个根节点的左子树不为空,则左子树中所有节点的值都必须小于根节点的值;如果它的右子树不为空,则右子树中所有节点的值都必须大于根节点的值。
  2. 它的左右子树也都必须是一个二叉搜索树,也都必须满足第一条。
  3. 二叉搜索树中的每个节点都是唯一的,不允许重复!!!
    在这里插入图片描述

 二叉搜索树的实际应用主要分为K模型和KV模型。

  1. K模型即Key作为关键码,二叉搜索树中只存储Key一个数据。而关键码则是待搜索的值。比如:我们经常通过软件查找是否存在某个单词,是否拼写正确。
  2. KV模型存储的数据中,每个Key对应一个Value,即键值对<Key, Value>。 我们经常通过Key去查找对应的Val.比如:我们通过英文来查找对应的中文,就是一个最常见的KV场景。

模拟实现KV模型

1. 节点封装

由于是KV模型,我们需要存储Key和Value俩个值。同时二叉搜索树也是二叉树,我们需要它的左右节点。因此节点疯转如下:

template<class K, class V>
struct BSTreeNode
{K _key;V _value;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;//默认构造函数, 用于后续new创建节点BSTreeNode(const K& key, const V& value):_key(key), _value(value), _right(nullptr), _left(nullptr){}
};

2、前置工作(默认构造、拷贝构造、赋值重载、析构函数等)

接下来是KV模型封装的框架,以及默认构造、拷贝构造、赋值重载、析构函数。比较简单,就直接给出代码了哈。

template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;//节点重命名public://默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(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);}private:Node* _root = nullptr;};
}

2. 数据插入(递归和非递归版本)

首先我们需要查找数据待插入的位置(为了保证插入数据后整体依然是一颗二叉搜索树).。同时查找插入位置时,只有key是有严格要求的,Value只是附带。
即:如果根节点为空,即是待插入数据位置;否则开始查找,如果待插入数据大于根节点往右子树节点走;如果待插入数据小于根节点往左子树节点走。不断循环,直到查找到空节点时,即为数据待插入的位置;如果查找到的大小和待插入数据值相等则返回false(确保二叉搜索树中的每个节点唯一)

【非递归版本】:

bool Insert(const K& key, const V& value)
{if (_root == nullptr)//根节点为空{_root = new Node(key, value);return true;}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//待插入数据等于当前节点,不允许插入{return false;}}//链接Node* newNode = new Node(key, value); //链接时,我们无法确定插入节点时在父节点的左边还是右边,需要进一步比较if (parent->_key > key)parent->_left = newNode;elseparent->_right = newNode;return true;
}

【递归版本】:

bool InsertR(const K& key, const V& value)
{//由于我们查找位置需要从根节点开始查找,所以这里通过另一个函数来传递实现return _InsertR(_root, key, value);
}bool _InsertR(Node*& root, const K& key, const V& value)
{if (root == nullptr){//注意上述我们形参都是引用,所以不用新增Parent节点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);elsereturn false;
}

3、数据删除(递归和非递归版本)

3.1 查找待删除节点位置

删除数据,我们首先需要和插入数据一样,先查找到待删除节点。和插入类似就不多说了。

【查找待删除数据】:

bool Erase(const K& key)
{if (_root == nullptr)//为空即不存在待删除数据return false;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{//当前位置即为待删除节点,装备删除数据	}}return false;//整棵树中不存在待删除数据
}

3.2 删除数据及相关节点调整

插找到待删除数据后,显然如果只是简单将该节点删除,有可能将不满足二叉搜索树的要求,那怎么办呢?
删除数据分为以下三种情况:

  1. 左子树为空

左子树为空主要分为以下情形:右子树为空,左子树不为空;左右子树均为空(省略)。
在这里插入图片描述
 不管上述那种情况,我们发现只需将父节点的下一个节点指向待删除节点的右指针即可。但需要注意的是,如果待删除节点为根节点,它将没有父节点,需要单独处理。

【代码实现】:

if (cur->_left == nullptr)//左子树为空
{if (parent == _root)//cur为根节点{_root = cur->_right;}else{if (parent->_key > cur->_key)//待删除节点在父节点左子树中{parent->_left = cur->_right;}else//待删除节点在父节点右子树中{parent->_right = cur->_right;}}delete cur;
}
  1. 右子树为空

右子树为空分为单纯右子树为空和左右子树均为空(省)。具体处理方式和左子树为空类似就不多说了。
在这里插入图片描述
【代码实现】:

//左右子树均不为空,查找右子树最小元素进行交换后删除
if (parent == _root)//cur为根节点
{_root = cur->_left;}else{if (parent->_key > cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;
}
  1. 左右子树均不为空

这种情况我们可以查找左子树最大值或右子树最小值和待删除删除节点进行交换,交换后我们可以转化为上述两种子问题来删除数据。(接下来博主以交换右子树最小值为例)
在这里插入图片描述

Node* subLeft = cur->_right;
Node* parent = cur;
while (subLeft->_left)
{parent = cur;subLeft = subLeft->_left;
}
//交换
swap(cur->_key, subLeft->_key);
swap(cur->_value, subLeft->_value);
//删除
if (parent->_right = subLeft)
{parent->_right = subLeft->_right;
}
else
{parent->_left = subLeft->_right;
}
delete subLeft;

3.3 完整代码以及递归和非递归版本

递归思路和非递归差球不多,就不一一分析了,下面直接给出两种实现方式代码。

【非递归版本】:

bool Erase(const K& key)
{if (_root == nullptr)return false;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 (parent == _root)//cur为根节点{_root = cur->_right;}else{if (parent->_key > cur->_key){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//右子树为空{if (parent == _root)//cur为根节点{_root = cur->_left;}else{if (parent->_key > cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{//左右子树均不为空,查找右子树最小元素进行交换后删除Node* subLeft = cur->_right;Node* parent = cur;while (subLeft->_left){parent = cur;subLeft = subLeft->_left;}//交换swap(cur->_key, subLeft->_key);swap(cur->_value, subLeft->_value);//删除if (parent->_right = subLeft){parent->_right = subLeft->_right;}else{parent->_left = subLeft->_right;}delete subLeft;}return true;}}return false;
}

【递归版本】:

//删除:递归版本
bool EraseR(const K& key)
{return _EraseR(_root, key);//同理,由于需要根节点,在通过一层函数来实现
}
bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)//非找到return false;if (root->_key > key)//转化成递归子问题,在左子树中删除keyreturn _EraseR(root->_left, key);else if (root->_key < key)//转化成递归子问题,在右子树中删除keyreturn _EraseR(root->_right, key);else{//删除数据if (root->_left == nullptr){Node* del = root;root = root->_right;delete del;return true;}else if (_root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* subLeft = root->_right;while (subLeft->_left){subLeft = subLeft->_left;}//交换swap(root->_key, subLeft->_key);swap(root->_value, subLeft->_value);return _EraseR(root->_right, key); }}
}

四、查找数据

【递归版本】:

//查找:递归版本
Node* FindR(const K& key)
{return _FindR(_root, key);
}
Node* _FindR(Node*& root, const K& key)
{if (root == nullptr)return nullptr;if (root->_key > key)return _FindR(root->_left, key);else if (root->_key < key)return _FindR(root->_right, key);elsereturn root;
}

【非递归版本】:

//查找:非递归版本
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key > key)cur = cur->_left;else if (cur->_key < key)cur = cur->_right;else{//找到了return cur;}}return nullptr;
}

五、中序遍历

//中序遍历
void Inorder()
{_Inorder(_root);cout << endl;
}void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << "->" << root->_value << " " << endl;_Inorder(root->_right);
}

六、所有代码

gitee:所有代码及测试代码

namespace KeyValue
{template<class K, class V>struct BSTreeNode{K _key;V _value;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;//默认构造函数BSTreeNode(const K& key, const V& value):_key(key), _value(value), _right(nullptr), _left(nullptr){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:
////默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(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);}
////插入, 非递归版本bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}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{return false;}}//链接Node* newNode = new Node(key, value); if (parent->_key > key)parent->_left = newNode;elseparent->_right = newNode;return true;}// 插入: 递归遍布bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}
///查找:非递归版本Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key)cur = cur->_left;else if (cur->_key < key)cur = cur->_right;else{//找到了return cur;}}return nullptr;}//查找:递归版本Node* FindR(const K& key){return _FindR(_root, key);}
///删除:非递归版本bool Erase(const K& key){if (_root == nullptr)return false;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 (parent == _root)//cur为根节点{_root = cur->_right;}else{if (parent->_key > cur->_key){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//右子树为空{if (parent == _root)//cur为根节点{_root = cur->_left;}else{if (parent->_key > cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{//左右子树均不为空,查找右子树最小元素进行交换后删除Node* subLeft = cur->_right;Node* parent = cur;while (subLeft->_left){parent = cur;subLeft = subLeft->_left;}//交换swap(cur->_key, subLeft->_key);swap(cur->_value, subLeft->_value);//删除if (parent->_right = subLeft){parent->_right = subLeft->_right;}else{parent->_left = subLeft->_right;}delete subLeft;}return true;}}return false;}//删除:递归版本bool EraseR(const K& key){return _EraseR(_root, key);}
///中序遍历void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << "->" << root->_value << " " << endl;_Inorder(root->_right);}private:Node* Copy(Node*& root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destory(Node*& root){if (root == nullptr)return;Destory(root->_right);Destory(root->_left);delete root;root = nullptr;}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key > key)return _EraseR(root->_left, key);else if (root->_key < key)return _EraseR(root->_right, key);else{//删除数据if (root->_left == nullptr){Node* del = root;root = root->_right;delete del;return true;}else if (_root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* subLeft = root->_right;while (subLeft->_left){subLeft = subLeft->_left;}//交换swap(root->_key, subLeft->_key);swap(root->_value, subLeft->_value);return _EraseR(root->_right, key); }}}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);elsereturn false;}Node* _FindR(Node*& root, const K& key){if (root == nullptr)return nullptr;if (root->_key > key)return _FindR(root->_left, key);else if (root->_key < key)return _FindR(root->_right, key);elsereturn root;}Node* _root = nullptr;};
}

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

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

相关文章

校园墙表白墙系统uniapp微信小程序

配置文件 (自动编号、配置参数名称、配置参数值)&#xff1b; 前端开发:vue 语言&#xff1a;javapythonnodejsphp均支持 运行软件:idea/eclipse/vscode/pycharm/wamp均支持 框架支持:Ssm/django/flask/thinkphp/springboot/springcloud均支持 数据库 mysql 数据库工具&#x…

【C++】C++的简要介绍

简单不先于复杂&#xff0c;而是在复杂之后。 文章目录 1. 什么是C2. C的发展史3. C的重要性3.1 语言的使用广泛度3.2 在工作领域3.3 在校招领域3.3.1 岗位需求3.3.2 笔试题 3.3.3 面试题 4. 如何学习C4.1 别人怎么学&#xff1f; 1. 什么是C C语言是结构化和模块化的语言&…

94.网游逆向分析与插件开发-游戏窗口化助手-地图数据获取的逆向分析与C++代码还原

内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;升级经验数据获取的逆向分析 码云地址&#xff08;游戏窗口化助手 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号&#xff1a;c4351a5b346d8953a1a8e3ec…

文件上传-Webshell

Webshell简介 webshell就是以aspphpjsp或者cgi等网页文件形式存在的一种命令执行环境&#xff0c;也可以将其称做为一种网页木马后门。 攻击者可通过这种网页后门获得网站服务器操作权限&#xff0c;控制网站服务器以进行上传下载文件、查看数据库、执行命令等… 什么是木马 …

Oracle和Mysql数据库

数据库 Oracle 体系结构与基本概念体系结构基本概念表空间(users)和数据文件段、区、块Oracle数据库的基本元素 Oracle数据库启动和关闭Oracle数据库启动Oracle数据库关闭 Sqlplussqlplus 登录数据库管理系统使用sqlplus登录Oracle数据库远程登录解锁用户修改用户密码查看当前语…

【网工】华为设备命令学习(服务器发布)

本次实验主要是内网静态nat配置没&#xff0c;对外地址可以理解为一台内网的服务器&#xff0c;外网设备可以ping通内网的服务器设备&#xff0c;但是ping不通内网的IP。 除了AR1设备配置有区别&#xff0c;其他设备都是基础IP的配置。 [Huawei]int g0/0/0 [Huawei-GigabitEt…

前端框架学习 Vue(3)vue生命周期,钩子函数,工程化开发脚手架CLI,组件化开发,组件分类

Vue 生命周期 和生命周期的四个阶段 Vue生命周期:一个Vue实例从创建 到 销毁 的整个过程 生命周期四个阶段 :(1)创建 (2)挂载 (3)更新 (4)销毁 Vue生命周期函数(钩子函数) Vue生命周期过程中,会自动运行一些函数,被称为[生命周期钩子] ->让开发者可以在[特定阶段] 运行自…

【初识爬虫+requests模块】

爬虫又称网络蜘蛛、网络机器人。本质就是程序模拟人使用浏览器访问网站&#xff0c;并将需要的数据抓取下来。爬虫不仅能够使用在搜索引擎领域&#xff0c;在数据分析、商业领域都得到了大规模的应用。 URL 每一个URL指向一个资源&#xff0c;可以是一个html页面&#xff0c;一…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Span组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Span组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Span组件 鸿蒙&#xff08;HarmonyOS&#xff09;作为Text组件的子组件&#xff0…

【MySQL】:深入理解并掌握DML和DCL

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; MySQL从入门到进阶 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一. DML1.1 添加数据1.2 修改数据1.3 删除数据 二. DCL2.1 管理用户2.2 权限控制…

RabbitMQ-1.介绍与安装

介绍与安装 1.RabbitMQ1.0.技术选型1.1.安装1.2.收发消息1.2.1.交换机1.2.2.队列1.2.3.绑定关系1.2.4.发送消息 1.2.数据隔离1.2.1.用户管理1.2.3.virtual host 1.RabbitMQ 1.0.技术选型 消息Broker&#xff0c;目前常见的实现方案就是消息队列&#xff08;MessageQueue&…

基于AST实现一键自动提取替换国际化文案

背景&#xff1a;在调研 formatjs/cli 使用&#xff08;使用 formatjs/cli 进行国际化文案自动提取 &#xff09;过程中&#xff0c;发现有以下需求formatjs/cli 无法满足&#xff1a; id 需要一定的语义化&#xff1b; defaultMessage和Id不能直接hash转换&#xff1b; 需要…

简化版SpringMVC

简化版SpringMVC web.xml xml version"1.0" encoding"UTF-8"?> <web-app version"2.5" xmlns"http://java.sun.com/xml/ns/javaee" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation&quo…

MySQL学习记录——칠 表操作

文章目录 1、了解2、创建和插入1、基本创建和插入2、插入并更新on duplicate3、插入并替换replace 3、Retrieve1、查询select2、条件查询where3、结果排序order by4、限制行数limit 4、更新Update5、删除delete6、去重7、聚合函数&#xff08;5个&#xff09;1、count2、sum3、…

第十六篇【传奇开心果系列】Python的OpenCV库技术点案例示例:图像质量评估

传奇开心果短博文系列 系列短博文目录Python的OpenCV库技术点案例示例短博文系列博文目录前言一、图像质量评估方法和相关函数的介绍二、均方误差示例代码三、峰值信噪比示例代码四、结构相似性指数示例代码五、视频质量评估示例代码六、OpenCV均方根误差计算示例代码七、OpenC…

Vivado开发FPGA使用流程、教程 verilog(建立工程、编译文件到最终烧录的全流程)

目录 一、概述 二、工程创建 三、添加设计文件并编译 四、线上仿真 五、布局布线 六、生成比特流文件 七、烧录 一、概述 vivado开发FPGA流程分为创建工程、添加设计文件、编译、线上仿真、布局布线&#xff08;添加约束文件&#xff09;、生成比特流文件、烧录等步骤&a…

05 06 Verilog基础语法与应用讲解

05. 1. 位操作 计数器实验升级&#xff0c;设计8个LED灯以每个0.5s的速率循环闪烁&#xff08;跑马灯&#xff09; 1.1 方法1&#xff1a;使用移位操作符<<来控制led灯的循环亮灭 设计代码 Verilog中&#xff0c;判断操作的时候不加位宽限定是可以的&#xff0c;比如i…

MySQL之体系结构

华子目录 MySQL简介MySQL的特性MySQL版本MySQL常见版本 数据库排名网站MySQL结构体系查看最大连接数查询缓存配置情况 一条SQL语句执行流程 MySQL简介 MySQL是一个小型关系数据库管理系统&#xff0c;开发者为瑞典MySQL AB公司。在2008年1月16号被sun公司10亿美金收购。2009年…

IntelliJ IDE 插件开发 | (六)内部模式的使用

系列文章 IntelliJ IDE 插件开发 |&#xff08;一&#xff09;快速入门IntelliJ IDE 插件开发 |&#xff08;二&#xff09;UI 界面与数据持久化IntelliJ IDE 插件开发 |&#xff08;三&#xff09;消息通知与事件监听IntelliJ IDE 插件开发 |&#xff08;四&#xff09;来查收…

Oracle systemstate、gdb、dbx介绍

当数据库出现严重的性能问题或者hang了的时候&#xff0c; 可能最常用的办法就是重启数据库&#xff0c;简单有效解决问题&#xff1b;但是重启后如何追踪问题的根本原因成了难题&#xff0c;很多信息随着重启也消失不见了&#xff0c;让追查问题变的十分棘手&#xff0c;这时就…