C++笔记17•数据结构:二叉搜索树(K模型/KV模型实现)•

2024-09-04 23:04

本文主要是介绍C++笔记17•数据结构:二叉搜索树(K模型/KV模型实现)•,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉搜索树

1.二叉搜索树

1. 二叉搜索树的查找
a 、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
b 、最多查找高度次,走到到空,还没找到,这个值不存在。
2. 二叉搜索树的插入
插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给 root 指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点
3.二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回 , 否则要删除的结点可能分下面四种情 况:
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有 4 中情况,实际情况 a 可以与情况 b 或者 c 合并起来,因此真正的删除过程如下:
情况 b :删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除
情况 c :删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除
情况 d:在它的右子树中寻找中序下的第一个结点( 也就是删除节点的左子树中最大的值或者删除节点的右子树中最小的值 ),用它的值填补到被删除节点 中,再来处理该结点的删除问题 -- 替换法删除

删除9、16、3、10节点

其中:节点9和16可以直接删除。3、10节点需要用替换法删除

节点3:需要用2节点或7节点来替换

节点10:需要用9节点或12节点来替换

 2.二叉搜索树-K模型

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;//二叉搜索树BinarySearchTree
//struct BinarySearchTreeNodetemplate<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;//一定不要写成BSTreeNode*<K>  _left;  这样编译器无法识别BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef struct BSTreeNode<K> Node;
public:bool insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//准备从parent插入Node* node = new Node(key);if (parent->_key > key)//插左子树{parent->_left = node;}else//插右子树{parent->_right = node;}//cur = new Node(key);//if (parent->_key > key)//插左子树//{//	parent->_left = cur;//}//else//插右子树//{//	parent->_right = cur;//}return true;}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}void Inorder(){_Inorder(_root);cout << endl;}void find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){cout << "找到了!" << endl;return;}else if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}}cout << "找不到!" << endl;return;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else   //找到了开始删除  1.左为空  2.右为空  3.左右都不为空{if (cur->_left == nullptr) //1.左为空{if (cur == _root) //判断删除的节点是否是根节点 根的左为空 让根的右成为根就可以了 _root = cur->_right{_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else     //parent->_right == cur{parent->_right = cur->_right;}}delete cur;                   //不要忘记手动释放节点}else if (cur->_right == nullptr)//2.右为空{if (cur == _root)//判断删除的节点是否是根节点 根的右为空 让根的左成为根就可以了 _root = cur->_left{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else   //parent->_right == cur{parent->_right = cur->_left;}}delete cur;}else   //3.左右都不为空 用删除节点的左子树中最大的值或者删除节点的右子树中最小的值  此处用删除节点的左子树最大值{//Node* Lbignode_pre = nullptr;//不能置空 后面如果直接跳出循环Lbignode_pre还是空,会出bug;Lbignode_pre->_right  空指针不能这样访问Node* Lbignode_pre = cur;Node* Lbignode = cur->_left;while (Lbignode->_right){Lbignode_pre = Lbignode;Lbignode = Lbignode->_right;}cur->_key = Lbignode->_key;//替换节点中的值,删除cur转换为删除Lbignodeif (Lbignode == Lbignode_pre->_right){Lbignode_pre->_right = Lbignode->_left;}else{Lbignode_pre->_left = Lbignode->_left;}delete Lbignode;}return true;}}return false;}private:Node* _root = nullptr;
};void test1()
{BSTree<int> bt;bt.insert(1);bt.insert(10);bt.insert(2);bt.insert(5);bt.insert(4);bt.insert(6);bt.insert(8);bt.insert(9);bt.insert(7);bt.insert(3);bt.insert(0);bt.insert(0);bt.Inorder();bt.find(8);bt.find(20);bt.erase(20);bt.erase(0);bt.erase(10);bt.erase(8);bt.Inorder();}
void test2()
{char arr[] = { 10,9,8,7,6,5,4,3,2,1,0 };BSTree<int> bt;for (auto e : arr){bt.insert(e);}cout << "插入:" << endl;bt.Inorder();cout << "依次删除:" << endl;for (auto e : arr){bt.erase(e);bt.Inorder();}
}
int main()
{//test1();test2();return 0;}

 3.二叉搜索树-KV模型

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
using namespace std;//二叉搜索树BinarySearchTree
//struct BinarySearchTreeNodetemplate<class K,class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;//一定不要写成BSTreeNode*<K>  _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 struct BSTreeNode<K,V> Node;
public:bool insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//准备从parent插入Node* node = new Node(key, value);if (parent->_key > key)//插左子树{parent->_left = node;}else//插右子树{parent->_right = node;}//cur = new Node(key, value);//if (parent->_key > key)//插左子树//{//	parent->_left = cur;//}//else//插右子树//{//	parent->_right = cur;//}return true;}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << ":"<<root->_value << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);cout << endl;}Node* find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){//cout << "找到了!" << endl;return cur;}else if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}}//cout << "找不到!" << endl;return nullptr;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else   //找到了开始删除  1.左为空  2.右为空  3.左右都不为空{if (cur->_left == nullptr) //1.左为空{if (cur == _root) //判断删除的节点是否是根节点 根的左为空 让根的右成为根就可以了 _root = cur->_right{_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else     //parent->_right == cur{parent->_right = cur->_right;}}delete cur;                   //不要忘记手动释放节点}else if (cur->_right == nullptr)//2.右为空{if (cur == _root)//判断删除的节点是否是根节点 根的右为空 让根的左成为根就可以了 _root = cur->_left{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else   //parent->_right == cur{parent->_right = cur->_left;}}delete cur;}else   //3.左右都不为空 用删除节点的左子树中最大的值或者删除节点的右子树中最小的值  此处用删除节点的左子树最大值{//Node* Lbignode_pre = nullptr;不能置空 后面如果直接跳出循环Lbignode_pre还是空,会出bug;Lbignode_pre->_right  空指针不能这样访问Node* Lbignode_pre = cur;Node* Lbignode = cur->_left;while (Lbignode->_right){Lbignode_pre = Lbignode;Lbignode = Lbignode->_right;}cur->_key = Lbignode->_key;//替换节点中的值,删除cur转换为删除Lbignodeif (Lbignode == Lbignode_pre->_right){Lbignode_pre->_right = Lbignode->_left;}else{Lbignode_pre->_left = Lbignode->_left;}delete Lbignode;}return true;}}return false;}private:Node* _root = nullptr;
};void test1()
{BSTree<string,string> Dictionary;Dictionary.insert("apple", "苹果");Dictionary.insert("pear", "梨");Dictionary.insert("left", "左");Dictionary.insert("right", "右");string str;while (cin >> str){BSTreeNode<string, string>* ret = Dictionary.find(str);if(ret)cout << ret->_value << endl;elsecout << "词典没有此单词!" << endl;}}
void test2()
{string arr[] = { "徐香猕猴桃","葡萄", "梨", "哈密瓜", "西瓜", "苹果", "橙子", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};BSTree<string, int> countfruit;BSTreeNode<string, int>* ret =nullptr;for (auto e : arr){//BSTreeNode<string, int>* ret =countfruit.find(e);ret = countfruit.find(e);if (ret == nullptr)countfruit.insert(e, 1);elseret->_value++;}delete ret;//这里可能会有双重释放节点 ret属于树节点 应在树中析构函数中进行节点的释放的管理,这里一般不需要自己手动释放,自己释放可能会遇到内存泄漏countfruit.Inorder();delete ret;
}
int main()
{//test1();test2();return 0;}

这篇关于C++笔记17•数据结构:二叉搜索树(K模型/KV模型实现)•的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137284

相关文章

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组