当前位置:网站首页>二叉搜索树的实现
二叉搜索树的实现
2022-07-06 21:03:00 【芜湖开冲~】
注意:本篇文章采用c++,在vs2022底下调试
目录
二叉搜索树概念
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
说白了,就是它是一棵排序树,它的左子树都比它小,右子树都比它大,所以它中序遍历以后正好是一个有序的序列
二叉搜索树节点实现
这里采用的是模板的方法实现的节点,节点的每个值都是一个键值对
template<class K, class V>
struct BSTreeNode {
BSTreeNode(const K& key = K(), const V& value = V())
:_val(key, value)
,_left(nullptr)
,_right(nullptr)
{}
BSTreeNode* _left;
BSTreeNode* _right;
pair<K, V> _val;
};
二叉搜索树的属性设置
typedef BSTreeNode<K, V> Node;
Node* _root = nullptr;
二叉搜索树的插入
bool Insert(const K& key, const V& value) {
Node* cur = new Node(key, value);
//空树
if (_root == nullptr) {
_root = cur;
return true;
}
//非空
//找cur插入的位置
Node* prev = cur; //保存一下cur的值
cur = _root;
Node* parent = _root;
while (cur) {
if (key > parent->_val.first) {
parent = cur;
cur = cur->_right;
}
else if (key < parent->_val.first) {
parent = cur;
cur = cur->_left;
}
else {
return false;
}
}
//找到了双亲节点的位置,插入
cur = prev;
if (cur->_val.first > parent->_val.first) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
return true;
}
二叉搜索树的删除
二叉搜索树的删除分为四种情况,待删除节点是叶子节点,只有左孩子,只有右孩子,左右孩子都有,
其中,待删除节点是叶子结点的情况可以和只有左孩子或只有右孩子合并,那就只有三中情况了,
只有左孩子和只有右孩子都好说,直接把它的孩子过继给父母就行了,难的就是左右孩子都有,那就只能找一个替代节点,这个替代节点一般是它的左子树中最大(最右)的那个节点或者是右子树中最小(最左)的那个节点,把那个节点的值放在待删除节点里面,然后删除那个节点
bool Erase(const K& key) {
if (_root == nullptr) {
return false;
}
//找节点
Node* delnode = _root;
Node* parent = nullptr;
while (delnode) {
if (delnode->_val.first == key) {
break;
}
else if (delnode->_val.first > key) {
parent = delnode;
delnode = delnode->_left;
}
else {
parent = delnode;
delnode = delnode->_right;
}
}
//没找着
if (delnode == nullptr) {
return false;
}
//只有右子树或者是叶子节点
if (delnode->_left == nullptr) {
if (parent == nullptr) {
_root = delnode->_right;
delete delnode;
}
else {
if (delnode == parent->_left) {
parent->_left = delnode->_right;
delete delnode;
}
else {
parent->_right = delnode->_right;
delete delnode;
}
}
}
//只有左子树
else if (delnode->_right == nullptr) {
//如果delnode是_root节点
if (parent == nullptr) {
_root = delnode->_left;
delete delnode;
}
else {
if (delnode == parent->_left) {
parent->_left = delnode->_left;
delete delnode;
}
else {
parent->_right = delnode->_left;
delete delnode;
}
}
}
//左右子树都有
else {
Node* firstinorder = delnode->_right;
parent = delnode;
//直接删除不好删除,找替代节点
while (firstinorder->_left) {
parent = firstinorder;
firstinorder = firstinorder->_left;
}
//把替代节点的val赋值给delnode,然后删除替代节点
delnode->_val = firstinorder->_val;
if (firstinorder == parent->_left) {
parent->_left = firstinorder->_right;
}
else {
parent->_right = firstinorder->_right;
}
delete firstinorder;
return true;
}
}
二叉搜索树的Find函数
Node* Find(const K& key) {
return _Find(_root, key);
}
Node* _Find(const Node* root, const K& key) {
if (key == root->_val.first) {
return root;
}
Node* cur = _Find(root->_left, key);
if (cur) {
return cur;
}
cur = _Find(root->_right, key);
if (cur) {
return cur;
}
return nullptr;
}
二叉搜索树的中序遍历
void InOrder() {
_InOrder(_root);
}
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
cout << root->_val.first << ":" << root->_val.second << endl;
_InOrder(root->_left);
_InOrder(root->_right);
}
整体代码
#include <utility>
using namespace std;
template<class K, class V>
struct BSTreeNode {
BSTreeNode(const K& key = K(), const V& value = V())
:_val(key, value)
,_left(nullptr)
,_right(nullptr)
{}
BSTreeNode* _left;
BSTreeNode* _right;
pair<K, V> _val;
};
//约定,value没有一样的
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value) {
Node* cur = new Node(key, value);
//空树
if (_root == nullptr) {
_root = cur;
return true;
}
//非空
//找cur改插入的位置
Node* prev = cur;
cur = _root;
Node* parent = _root;
while (cur) {
if (key > parent->_val.first) {
parent = cur;
cur = cur->_right;
}
else if (key < parent->_val.first) {
parent = cur;
cur = cur->_left;
}
else {
return false;
}
}
cur = prev;
if (cur->_val.first > parent->_val.first) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
return true;
}
Node* Find(const K& key) {
return _Find(_root, key);
}
bool Erase(const K& key) {
if (_root == nullptr) {
return false;
}
//找节点
Node* delnode = _root;
Node* parent = nullptr;
while (delnode) {
if (delnode->_val.first == key) {
break;
}
else if (delnode->_val.first > key) {
parent = delnode;
delnode = delnode->_left;
}
else {
parent = delnode;
delnode = delnode->_right;
}
}
//没找着
if (delnode == nullptr) {
return false;
}
//只有右子树或者是叶子节点
if (delnode->_left == nullptr) {
if (parent == nullptr) {
_root = delnode->_right;
delete delnode;
}
else {
if (delnode == parent->_left) {
parent->_left = delnode->_right;
delete delnode;
}
else {
parent->_right = delnode->_right;
delete delnode;
}
}
}
//只有左子树
else if (delnode->_right == nullptr) {
if (parent == nullptr) {
_root = delnode->_left;
delete delnode;
}
else {
if (delnode == parent->_left) {
parent->_left = delnode->_left;
delete delnode;
}
else {
parent->_right = delnode->_left;
delete delnode;
}
}
}
//左右子树都有
else {
Node* firstinorder = delnode->_right;
parent = delnode;
//直接删除不好删除,找替代节点
while (firstinorder->_left) {
parent = firstinorder;
firstinorder = firstinorder->_left;
}
//把替代节点的val赋值给delnode,然后删除替代节点
delnode->_val = firstinorder->_val;
if (firstinorder == parent->_left) {
parent->_left = firstinorder->_right;
}
else {
parent->_right = firstinorder->_right;
}
delete firstinorder;
return true;
}
}
void InOrder() {
_InOrder(_root);
}
private:
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
cout << root->_val.first << ":" << root->_val.second << endl;
_InOrder(root->_left);
_InOrder(root->_right);
}
Node* _Find(const Node* root, const K& key) {
if (key == root->_val.first) {
return root;
}
Node* cur = _Find(root->_left, key);
if (cur) {
return cur;
}
cur = _Find(root->_right, key);
if (cur) {
return cur;
}
return nullptr;
}
Node* _root = nullptr;
};
边栏推荐
- On file uploading of network security
- Clock in during winter vacation
- Kalman filter-1
- 海思3559万能平台搭建:RTSP实时播放的支持
- Machine learning notes - bird species classification using machine learning
- 19.(arcgis api for js篇)arcgis api for js线采集(SketchViewModel)
- Baidu map JS development, open a blank, bmapgl is not defined, err_ FILE_ NOT_ FOUND
- 1200.Minimum Absolute Difference
- 20. (ArcGIS API for JS) ArcGIS API for JS surface collection (sketchviewmodel)
- . Net interface can be implemented by default
猜你喜欢
A 股指数成分数据 API 数据接口
Free PHP online decryption tool source code v1.2
Restcloud ETL Community Edition June featured Q & A
1200.Minimum Absolute Difference
What is Ba? How about Ba? What is the relationship between Ba and Bi?
19. (ArcGIS API for JS) ArcGIS API for JS line acquisition (sketchviewmodel)
Ubuntu20 installation redisjson record
我的勇敢对线之路--详细阐述,浏览器输入URL发生了什么
R data analysis: how to predict Cox model and reproduce high score articles
Sub pixel corner detection opencv cornersubpix
随机推荐
QT item table new column name setting requirement exercise (find the number and maximum value of the array disappear)
Tencent cloud native database tdsql-c was selected into the cloud native product catalog of the Academy of communications and communications
代码质量管理
How to customize the shortcut key for latex to stop running
Not All Points Are Equal Learning Highly Efficient Point-based Detectors for 3D LiDAR Point
Depth analysis of compilation constants, classloader classes, and system class loaders
如何自定义Latex停止运行的快捷键
PIP download only, not install
Hisilicon 3559 universal platform construction: RTSP real-time playback support
Create applet from 0
2022.6.28
Search of linear table
机器学习笔记 - 使用机器学习进行鸟类物种分类
图形化工具打包YOLOv5,生成可执行文件EXE
Docker部署Mysql8的实现步骤
2022年上半年HIT行业TOP50
22.(arcgis api for js篇)arcgis api for js圆采集(SketchViewModel)
QT 项目 表格新建列名称设置 需求练习(找数组消失的数字、最大值)
MySQL的索引
10 ways of interface data security assurance