二叉搜索树的实现[C++]

🕗 发布于 2024-07-16 18:30 c++ 开发语言 搜索二叉树

文章目录

搜索二叉树
实现搜索二叉树
总结

今天本堂主来一起讨论下什么是搜索二叉树，和如何实现二叉搜索树

搜索二叉树

那么二叉搜索树似乎如何实现搜索呢？二叉搜索树和普通二叉树有什么不同呢？

概念

搜索二叉树又可以称作二叉搜索树或二叉排序树。
搜索二叉树需要满足几个条件或者说要具备几个性质：

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树

二叉搜索树的功能

查找

二叉搜索树的查找：

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。

这样在理想情况下时间复杂度是O（logn）,而极端情况如下图时间复杂度还是O（n²）

在这里插入图片描述

实现搜索二叉树

那么如何实现搜索二叉树呢？
在这里插入图片描述
咱们可以按照这个思路去实现

节点的定义

定义节点的时候二叉树包括：本身值，左节点，右节点
那么我们就可以这样来定义节点

template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;

BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};

这样我们就定义了一个二叉搜索树的节点结构体，构造函数则是用于创建节点并初始化建值，左右指针默认为空

建立搜索二叉树

那么接下来我们就进行声明根节点和初始化根节点为我们后面实现搜索二叉树的功能做铺垫

template<class K>
class BSTree
{
typedef BSTNode<K> Node;
\*
...
*\
private:
Node* _root = nullptr;
};

声明根节点：我们声明了一个名为 _root 的指针，该指针指向 Node 类型的对象。这里的 Node 是 BSTNode 的类型别名。

初始化根节点：通过将 _root 初始化为 nullptr，我们是在创建一个空的搜索二叉树，为后面做铺垫。

接口

万事俱备那么我们就来实现搜索二叉树的功能吧

插入

首先一定是向空的搜索二叉树中插入数。

很简单我们先在BSTree的类里面定义一个Insert的函数

//插入
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;
}
}


cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else if (parent->_key > key)
{
parent->_left = cur;
}
return true;
}

我们先判断_root如果为空那么我们定义一个新新节点连接到根节点，并给新节点赋值
其次如果树不为空，遍历树来找到正确的插入位置（我这里用的双指针防止迷路）
如果找到和键值相同的节点则不插入
符合搜索二叉树的性质加入新节点

搜索

有了插入的铺垫我们搜索的函数在遍历查找树这里就可以CV下

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

不同的是在插入的时候找到和键值相同的值是返回false 而在搜索函数找到键值返回true证明找到了，而没找到值的时候才返回false

打印

那么打印这里就正常写就可以,但是会有一点点小问题
在我正常写打印函数之后，因为_root是私有的只有内部能用所以我用不了

void InOrder()
{
if (root == nullptr)
{
return;
}
InOrder(root->_left);
cout << root->_key << " ";
InOrder(root->_right);
}

在这里我就进行了些调整

//打印
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
//打印的子函数
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

这样我用个子函数之后再在打印函数中调用子函数就可以了

删除

相较前两个删除是比较麻烦的

看长度可知⬇

//删除
bool Erase(const K& key)
{
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
{
//0-1个孩子
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left == cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
//两个孩子
else
{
Node* rightMinP = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;

if (rightMinP->_left == rightMin)
{
rightMinP->_left = rightMin->_right;
}
else
{
rightMinP->_right = rightMin->_right;
}
delete rightMin;
return true;
}
}
}

return false;
}

那么删除这里我在 BSTree 类中定义成员函数 Erase，用于删除搜索二叉树中具有特定键值 key 的节点。

定义函数：bool Erase(const K& key)，这是一个返回 bool 类型的函数，它接受一个键值 key 作为参数。
查找要删除的节点：
- 初始化两个指针 parent 和 cur，分别用于跟踪父节点和当前节点。
- 进入一个循环，直到找到要删除的节点或者当前节点为 nullptr。
- 在循环中，通过比较 cur->_key 和 key 来确定是否继续向左或向右遍历。
删除节点的逻辑：
- 如果找到要删除的节点，则根据节点是否有子节点或子节点的数量来决定如何删除节点。
- 如果节点只有一个子节点（要么是左子节点，要么是右子节点），则直接将父节点的相应指针指向该子节点。
- 如果节点有两个子节点，则需要找到右子树中的最小节点（即右子树的最左下角的节点），将其值复制到当前节点，然后删除右子树中的最小节点。
释放内存：
- 在删除节点后，如果节点不再被引用，则释放其内存。
返回结果：
- 如果成功删除节点，返回 true。
- 如果循环结束而没有找到要删除的节点，返回 false。
  这段代码实现了搜索二叉树中键值的删除操作，它通过递归或迭代的方式找到要删除的节点，并确保在删除节点后树仍然保持搜索二叉树的性质。

总结

那么以上就是搜索二叉树的说明和实现，能给我点点赞吗？

完整代码：

#pragma once
#include <iostream>
using namespace std;

template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;

BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};

template<class K>
class BSTree
{
typedef BSTNode<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;
}
}


cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else if (parent->_key > key)
{
parent->_left = cur;
}
return true;
}

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

//删除
bool Erase(const K& key)
{
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
{
//0-1个孩子
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left == cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
//两个孩子
else
{
//右子树的最大节点作为替代节点
/*Node* rightMinP = nullptr;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;

rightMinP->_left = rightMinP->_right;
delete rightMin;
return true;*/
Node* rightMinP = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;

if (rightMinP->_left == rightMin)
{
rightMinP->_left = rightMin->_right;
}
else
{
rightMinP->_right = rightMin->_right;
}
delete rightMin;
return true;
}
}
}

return false;
}

//打印
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
//打印的子函数
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

private:
Node* _root = nullptr;
};

封面图
在这里插入图片描述

原文地址：https://blog.csdn.net/Q741_147/article/details/140445811

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：mpi4py跨节点并行案例
下一篇：pear-admin-fast项目修改为集成PostgreSQL启动

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20