【C++】实现一个搜索二叉树（BSTree）：从定义到操作全解析

news/2024/7/27 8:25:26/文章来源:https://blog.csdn.net/Colorful___/article/details/136439217

文章目录

  • BSTreeNode类的定义
  • BSTree类的实现
    • 插入操作
    • 查找操作
    • 删除操作
    • 中序遍历
  • 递归实现
  • 完整代码和测试
  • 总结

搜索二叉树（Binary Search Tree，简称BST）是一种特殊的二叉树，它满足任一节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。这使得BST在查找、插入和删除操作上具有较高的效率。本文将详细介绍如何从零开始实现一个搜索二叉树，包括其节点结构的定义和一系列基本操作的实现。

BSTreeNode类的定义

首先，我们需要定义树的节点BSTreeNode，它将作为树的基础结构：

template<class K, class V>
class BSTreeNode {
public:K _key;     // 节点存储的键V _value;   // 节点存储的值BSTreeNode* _left;   // 左子节点BSTreeNode* _right;  // 右子节点BSTreeNode(const K& key, const V& value): _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

BSTree类的实现

接着，我们来实现BSTree类，它包含了一系列操作二叉搜索树的方法：

插入操作

插入操作Insert的核心思想是比较待插入节点的键与当前节点的键，决定向左子树还是右子树递归地进行插入操作。

	bool Insert(const K& key, const V& value) {if (!_root) {_root = new Node(key, value);return true;}Node* parent = nullptr;Node* current = _root;while (current) {parent = current;if (key < current->_key) {current = current->_left;}else if (key > current->_key) {current = current->_right;}else {return false; // key已经存在}}if (key < parent->_key) {parent->_left = new Node(key, value);}else {parent->_right = new Node(key, value);}return true;}

查找操作

查找操作Find通过逐层比较键值，沿树向下移动，直到找到匹配的节点或达到叶子节点。

Node* Find(const K& key) {Node* current = _root;while (current) {if (key < current->_key) {current = current->_left;}else if (key > current->_key) {current = current->_right;}else {return current; // 找到了}}return nullptr; // 没有找到
}

删除操作

删除操作Erase是最复杂的，它需要处理三种情况：被删除节点是叶子节点、只有一个子节点、有两个子节点。

  1. 被删除节点是叶子节点：直接删除该节点，并将其父节点的相应指针设置为nullptr。
  2. 被删除节点只有一个子节点：删除该节点，并将其父节点的相应指针指向其子节点。
  3. 被删除节点有两个子节点：找到该节点的中序后继节点（右子树中的最小节点），用它来替换被删除节点的键和值，然后删除中序后继节点。

下面是Erase函数的实现代码：

bool Erase(const K& key) {Node* parent = nullptr;Node* current = _root;// 查找key对应的节点，同时记录其父节点while (current != nullptr && current->_key != key) {parent = current;if (key < current->_key) {current = current->_left;}else {current = current->_right;}if (current == nullptr) {// 没有找到对应的节点return false;}}//case1&2: 没有孩子或者只有一个孩子if (current->_left == nullptr || current->_right == nullptr) {Node* child = (current->_left == nullptr) ? current->_right : current->_left;if (parent == nullptr) {// 删除的是根节点_root = child;}else {if (parent->_left == current) {parent->_left = child;}else {parent->_right = child;}}delete current;}else {// case 3: 两个孩子// 找到右子树最小节点， 即中序后继节点Node* successor = current->_right;Node* successorParent = current;while (successor->_left != nullptr) {successorParent = successor;successor = successor->_left;}// 替换current 的节点和键值current->_key = successor->_key;current->_value = successor->_value;if (successorParent->_left = successor) {successorParent->_left = successor->_right;}else {successorParent->_right = successor->_right;}delete successor;}
}

中序遍历

中序遍历InOrder按照左子树-根节点-右子树的顺序访问树中的每个节点，对于BST来说，这将以升序方式访问所有节点。

	void _InOrder(Node* root) {if (!root) return;_InOrder(root->_left);cout << root->_key << " : " << root->_value << endl;_InOrder(root->_right);}void InOrder() {_InOrder(_root);}

递归实现

对于插入、查找和删除操作，我们还提供了递归版本的实现方法，以更直观地展示这些操作的逻辑。

// 递归版本 //bool 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:bool _FindR(Node* root, const K& key) {if (root == nullptr)return false;if (root->_key < key) {return _FindR(root->_right, key);}else if (root->_key > key) {return _FindR(root->_left, key);}else {return true;}};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->_right, key, value);}else if (root->_key > key) {return _InsertR(root->_left, key, value);}else {return false;}}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 {//case1&2: 没有孩子或者只有一个孩子Node* del = root;if (root->_right == nullptr) {root = root->_left;} else if (root->_left == nullptr){root = root->_right;}else {// case 3: 两个孩子// 找到右子树最小节点，即中序后继节点Node* successor = root->_right;while (successor->_left != nullptr) {successor = successor->_left;}// 将中序后继节点的值复制到当前节点root->_key = successor->_key;// 递归删除中序后继节点_EraseR(root->_right, successor->_key);}delete del;return true;}}

完整代码和测试

文章最后给出了BSTree类的完整实现代码，并提供了几个简单的测试用例来验证我们的实现。

#pragma once
#include <iostream>
#include <string>
using namespace std;template<class K, class V>
class BSTreeNode {
public:K _key;	// 节点存储的键V _value;	// 节点存储的值BSTreeNode* _left; //左子节点BSTreeNode* _right; //右子节点BSTreeNode(const K& key, const V& value): _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public://强制生成默认构造BSTree() = default;BSTree(const BSTree<K,V>& t) {_root = Copy(t._root);}BSTree<K,V>& operator=(BSTree<K,V>& t) {swap(_root, t._root);}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;}~BSTree(){Destroy(_root);}void Destroy(Node* root) {if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}bool Insert(const K& key, const V& value) {if (!_root) {_root = new Node(key, value);return true;}Node* parent = nullptr;Node* current = _root;while (current) {parent = current;if (key < current->_key) {current = current->_left;}else if (key > current->_key) {current = current->_right;}else {return false; // key已经存在}}if (key < parent->_key) {parent->_left = new Node(key, value);}else {parent->_right = new Node(key, value);}return true;}Node* Find(const K& key) {Node* current = _root;while (current) {if (key < current->_key) {current = current->_left;}else if (key > current->_key) {current = current->_right;}else {return current; // 找到了}}return nullptr; // 没有找到}bool Erase(const K& key) {Node* parent = nullptr;Node* current = _root;// 查找key对应的节点，同时记录其父节点while (current != nullptr && current->_key != key) {parent = current;if (key < current->_key) {current = current->_left;}else {current = current->_right;}if (current == nullptr) {// 没有找到对应的节点return false;}}//case1&2: 没有孩子或者只有一个孩子if (current->_left == nullptr || current->_right == nullptr) {Node* child = (current->_left == nullptr) ? current->_right : current->_left;if (parent == nullptr) {// 删除的是根节点_root = child;}else {if (parent->_left == current) {parent->_left = child;}else {parent->_right = child;}}delete current;}else {// case 3: 两个孩子// 找到右子树最小节点， 即中序后继节点Node* successor = current->_right;Node* successorParent = current;while (successor->_left != nullptr) {successorParent = successor;successor = successor->_left;}// 替换current 的节点和键值current->_key = successor->_key;current->_value = successor->_value;if (successorParent->_left = successor) {successorParent->_left = successor->_right;}else {successorParent->_right = successor->_right;}delete successor;}}void InOrder() {_InOrder(_root);}// 递归版本 //bool 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:bool _FindR(Node* root, const K& key) {if (root == nullptr)return false;if (root->_key < key) {return _FindR(root->_right, key);}else if (root->_key > key) {return _FindR(root->_left, key);}else {return true;}};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->_right, key, value);}else if (root->_key > key) {return _InsertR(root->_left, key, value);}else {return false;}}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 {//case1&2: 没有孩子或者只有一个孩子Node* del = root;if (root->_right == nullptr) {root = root->_left;} else if (root->_left == nullptr){root = root->_right;}else {// case 3: 两个孩子// 找到右子树最小节点，即中序后继节点Node* successor = root->_right;while (successor->_left != nullptr) {successor = successor->_left;}// 将中序后继节点的值复制到当前节点root->_key = successor->_key;// 递归删除中序后继节点_EraseR(root->_right, successor->_key);}delete del;return true;}}void _InOrder(Node* root) {if (!root) return;_InOrder(root->_left);cout << root->_key << " : " << root->_value << endl;_InOrder(root->_right);}Node* _root = nullptr;
};void TestBSTree1()
{BSTree<string, string> dict;dict.InsertR("insert", "插入");dict.InsertR("erase", "删除");dict.InsertR("left", "左边");dict.InsertR("string", "字符串");dict.InOrder();string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}cout << "删除： " << ret->_key << " : " << ret->_value << endl;dict.EraseR(ret->_key);dict.InOrder();}
}void TestBSTree2()
{string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}void TestBSTree3() {BSTree<int, string> t;t.Insert(8, "八");t.Insert(3, "三");t.Insert(1, "一");t.Insert(10, "十");t.Insert(6, "六");t.Insert(4, "四");t.Insert(7, "七");t.Insert(14, "十四");t.Insert(13, "十三");t.InOrder();BSTree<int, string> t1(t);t1.InOrder();
}

总结

通过本文的介绍，我们了解了二叉搜索树的基本概念、节点结构的定义以及如何实现插入、查找、删除和中序遍历等基本操作。实现一个搜索二叉树不仅能够加深对数据结构和算法的理解，也能够提升编程能力和问题解决能力。

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

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

相关文章

【C++从0到王者】第五十一站：B+树

【C++从0到王者】第五十一站：B+树

文章目录 一、B树1.B树的概念2.B树的特性3.B树的插入的过程4.总结 二、B*树1. B*树的概念2.B*树的分裂 三、总结四、B树系列和哈希和平衡搜索树作对比五、B树的一些应用1.索引2.MySQL索引3.MyISAM2.InnoDB 一、B树 1.B树的概念 B树是B树的变形&#xff0c;是在B树基础上优化的…
阅读更多...
C++ 链表OJ

C++ 链表OJ

目录 1、2. 两数相加 2、24. 两两交换链表中的节点 3、143. 重排链表 4、23. 合并 K 个升序链表 5、25. K 个一组翻转链表 解决链表题目常用方法&#xff1a; 1、画图 2、引入虚拟"头”结点 便于处理边界情况方便我们对链表操作 3、大胆定义变量&#xff0c;减少连接…
阅读更多...
2024-3-7 市场分歧视角

2024-3-7 市场分歧视角

昨天安奈儿市场带领市场情绪一致&#xff0c;新型工业化方向独占鳌头&#xff0c;日内高潮节点尾盘老龙 克来机电涨停&#xff0c;昨晚很多老师在YY老龙是不是要二波了&#xff0c;呵呵。 今天市场分歧从竞价就开始了&#xff0c;隔夜单我记忆中 天奇股份88亿&#xff0c;上海…
阅读更多...
python71-Python的函数入门，定义函数和调用函数

python71-Python的函数入门，定义函数和调用函数

在使用函数之前必须先定义函数&#xff0c;定义函数的语法格式如下&#xff1a; def 函数名(形参列表)://由零条到多条可执行语句组成的函数[return [返回值]] Python声明函数必须使用def关键字&#xff0c;对函数语法格式的详细说明如下。 1&#xff09;函数名:从语法角度来…
阅读更多...
力扣--从前序与中序遍历序列构造二叉树

力扣--从前序与中序遍历序列构造二叉树

题目&#xff1a; 思想&#xff1a; 首先先序遍历能确定根节点的值&#xff0c;此时查看该值在中序遍历中的位置&#xff08;如果索引为i&#xff09;&#xff0c;那么i左侧为左子树&#xff0c;i 右侧为右子树。从中序数组中即可看出左子树结点个数为 i&#xff0c;右子树节点…
阅读更多...
Pytorch学习 day06（torchvision中的datasets、dataloader）

Pytorch学习 day06（torchvision中的datasets、dataloader）

torchvision的datasets 使用torchvision提供的数据集API&#xff0c;比较方便&#xff0c;如果在pycharm中下载很慢&#xff0c;可以URL链接到迅雷中进行下载&#xff08;有些URL链接在源码里&#xff09;代码如下&#xff1a; import torchvision # 导入 torchvision 库 # …
阅读更多...
线程池不香了? 结构化并发才是王道!

线程池不香了? 结构化并发才是王道!

我们先定义获取用户信息任务&#xff1a; 再定义获取订单信息任务&#xff1a; 然后再构造线程池并执行任务&#xff1a; 输出结果为&#xff1a; 看上去一切都刚刚好&#xff0c;但是&#xff0c;如果获取订单信息时出错了&#xff0c;此时会是什么现象呢&#xff1f;修改获取…
阅读更多...
PoC免写攻略

PoC免写攻略

在网络安全领域&#xff0c;PoC&#xff08;Proof of Concept&#xff09;起着重要的作用&#xff0c;并且在安全研究、漏洞发现和漏洞利用等方面具有重要的地位。攻击方视角下&#xff0c;常常需要围绕 PoC 做的大量的工作。常常需要从手动测试开始编写 PoC&#xff0c;再到实…
阅读更多...
SAP - 采购价格确定 ③ 抬头条件和组条件

SAP - 采购价格确定 ③ 抬头条件和组条件

抬头条件和组条件 当我们创建一个具有多个行项目的采购订单时，我们经常需要条件可以应用到所有的行项目中。相应的，条件也可以应用到特定的行项目。在R/3系统中，条件可以涉及采购凭证的单个行项目（项目条件），多个行项目（组条件）或所有的行项目（抬头条件）。 一些标准…
阅读更多...
计算机/大数据毕业设计-基于Python的动漫数据分析可视化系统的设计与实现

计算机/大数据毕业设计-基于Python的动漫数据分析可视化系统的设计与实现

基于Python的动漫数据分析可视化系统的设计与实现 设计爬虫程序爬取哔哩哔哩动漫数据信息 后端使用flask框架&#xff0c;数据库使用Mysql8.0&#xff0c;可视化使用echarts 部分代码如下&#xff1a; # 保存所有动漫信息 all_anime_infos [] # 保存到文件中 file_writer …
阅读更多...
讨论：5万官网是建站界的劳斯莱斯了吧，到了软件开发领域呢？

讨论：5万官网是建站界的劳斯莱斯了吧，到了软件开发领域呢？

如题&#xff0c;所以赛道选择很重要&#xff0c;当然难度系数也不一样。能花5万元做官网的&#xff0c;凤毛麟角&#xff0c;如果是做软件开发&#xff0c;5万元顶多算个起步价&#xff0c;老铁们&#xff0c;是这样吗&#xff1f;
阅读更多...
Openwrt(IstoreOS)安装iventoy

Openwrt(IstoreOS)安装iventoy

背景 目前家里有两台不用的旧主机&#xff0c;平时没事在家里折腾这两台机器。经常换装各种系统。最早是将镜像刷入u盘作为启动盘&#xff0c;这样需要重复装系统就特别麻烦。后来用了ventoy以后一个U盘可以放多个系统镜像&#xff0c;还能做口袋系统&#xff08;SystemToGo&a…
阅读更多...
安卓手机如何使用JuiceSSH实现公网远程连接本地Linux服务器

安卓手机如何使用JuiceSSH实现公网远程连接本地Linux服务器

文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …
阅读更多...
别再找了，关于免费SSL证书都在这里

别再找了，关于免费SSL证书都在这里

免费SSL证书的优点&#xff1a; 成本效益&#xff1a;免费SSL证书可以帮助网站所有者节省资金&#xff0c;特别是对于初创公司或个人网站来说&#xff0c;这是一个很大的优势。提高信任度&#xff1a;通过使用SSL证书&#xff0c;网站可以向访问者展示其对安全性的承诺&#x…
阅读更多...
2024/3/7—2575. 找出字符串的可整除数组

2024/3/7—2575. 找出字符串的可整除数组

代码实现&#xff1a; int* divisibilityArray(char *word, int m, int *returnSize) {int n strlen(word);int *res (int*)malloc(sizeof(int) * n);long cur 0;for (int i 0; i < n; i) {cur (cur * 10 (word[i] - 0)) % m;res[i] (cur 0) ? 1 : 0;}*returnSize …
阅读更多...
1-安装rabbitmq

1-安装rabbitmq

rabbitmq官网&#xff1a; https://www.rabbitmq.com/docs/download 本机环境&#xff1a;mac&#xff0c;使用orbstack提供的docker 使用docker部署rabbitmq docker run -it --rm --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.13-management 然后报错&#xf…
阅读更多...
基于STC系列单片机实现PNP型三极管S8550驱动共阳数码管或NPN型三极管S8050驱动共阴数码管功能

基于STC系列单片机实现PNP型三极管S8550驱动共阳数码管或NPN型三极管S8050驱动共阴数码管功能

Digitron.c #include "Digitron.h" //#include "Key.h" #define uchar unsigned char//自定义无符号字符型为uchar #define uint unsigned int//自定义无符号整数型为uint //uchar code DigitronBitCodeArray[] {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x8…
阅读更多...
机器学习-面经（part8、贝叶斯和其他知识点）

机器学习-面经（part8、贝叶斯和其他知识点）

机器学习面经其他系列 机器学习面经系列的其他部分如下所示&#xff1a; 机器学习-面经(part1)-初步说明 机器学习-面经(part2)-交叉验证、超参数优化、评价指标等内容 机器学习-面经(part3)-正则化、特征工程面试问题与解答合集机器学习-面经(part4)-决策树共5000字的面试问…
阅读更多...
go linux监测文件变化

go linux监测文件变化

go linux监测文件变化 文件改变内容有两种方式&#xff0c;效果一样&#xff0c;但执行方式有区别: 直接打开文件改&#xff0c;现在很多编辑器都是这样操作的先删除原来的&#xff0c;再新创建写入一个替代原来的。比如vi/vim.这种方式会打断linux inotify原有的监测(就好比…
阅读更多...
springboot+vue+mysql项目使用的常用注解

springboot+vue+mysql项目使用的常用注解

实体类常用注解 Data Data 是一个 Lombok 提供的注解&#xff0c;使用 Data 注解可以简化代码&#xff0c;使代码更加简洁易读。 作用&#xff1a;自动为类生成常用的方法&#xff0c;包括 getter、setter、equals、hashCode 和 toString 等需要加Lombok的依赖 <depende…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业