二叉搜索树的实现[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 的节点。

1. 定义函数：bool Erase(const K& key)，这是一个返回 bool 类型的函数，它接受一个键值 key 作为参数。
2. 查找要删除的节点：
   • 初始化两个指针 parent 和 cur，分别用于跟踪父节点和当前节点。
   • 进入一个循环，直到找到要删除的节点或者当前节点为 nullptr。
   • 在循环中，通过比较 cur->_key 和 key 来确定是否继续向左或向右遍历。
3. 删除节点的逻辑：
   • 如果找到要删除的节点，则根据节点是否有子节点或子节点的数量来决定如何删除节点。
   • 如果节点只有一个子节点（要么是左子节点，要么是右子节点），则直接将父节点的相应指针指向该子节点。
   • 如果节点有两个子节点，则需要找到右子树中的最小节点（即右子树的最左下角的节点），将其值复制到当前节点，然后删除右子树中的最小节点。
4. 释放内存：
   • 在删除节点后，如果节点不再被引用，则释放其内存。
5. 返回结果：
   • 如果成功删除节点，返回 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;
};

封面图