C++ 系列 - 二进制搜索树
最编程
2024-10-05 07:04:05
...
????个人主页:羽晨同学
????个人格言:“成为自己未来的主人~”
二叉搜索树
二叉搜索树又称二叉排序树,它或者是一颗空树,或者是具有以下性质的树
- 若它的左子树不为空,则左子树上的所有节点的值都小于根节点的值。
- 若它的右子树不为空,则右子树上的所有节点的值都大于根节点的值。
- 它的左右字数也分别为二叉搜索树。
二叉树在我们之前讲数据结构的时候完成过二叉树的实现,在二叉树中,每个节点都会指向它的左右节点,所以,我们可以先初步实现二叉搜索树当中的每个节点。
template<class K>
class 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);
bool Find(const K& key);
bool Erase(const K& key);
void Inorder();
private:
void _Inorder(Node* root);
private:
Node* _root = nullptr;
};
接下来,让我们逐步分析一下每个功能的具体实现方式。
查找
因为二叉搜索树实现插入功能需要用的查找功能,所以,我们先来实现查找这个函数。
- 从根开始查找,比根大去右边,比根小去左边
- 找到的话,返回true,找不到,返回false
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
插入
- 树为空,则直接新增节点,赋值给root指针
- 树不为空,则查找插入的位置,插入新节点。
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)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
在这个当中,我们要记得定义一个父亲节点,便于找到后进行插入操作。
删除
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->_right == cur)
{
parent->_right = cur->_left;
}
else
parent->_left = 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;
}
中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(_root->_left);
cout << _root->_key << " ";
_Inorder(_root->_right);
}
好了,本次的文章就到这里了,我们下次再见。
下一篇: 如何在 vue 中实现组件通信
推荐阅读
-
C++ 系列 - 二进制搜索树
-
代码随机化算法训练营 | 235. 二进制搜索树的最近共同祖先, 701. 二进制搜索树中的插入操作, 450. 二进制搜索树中删除节点
-
Excel 技巧树系列 05:TEXT 函数、IF 函数和 INDEX + MATCH 组合搜索函数
-
C++ STL 中的二进制搜索
-
Android 算法知识系列:二进制搜索
-
第 5 次阶梯锦标赛模拟 - L2-3 二进制搜索树的第 2 层节点计数(25 分) - 树构建 + DFS
-
C++] 从零开始构建二叉搜索树
-
请谈谈您对数据结构 - 树 - 树的理解 - 二进制搜索树的理解
-
代码随机化刷新 - 二进制树 - 6.二叉搜索树的修改和构建
-
算法 D40 | 动态编程 3 | 343. 整数分割 96. 不同的二进制搜索树