文章目录
- 二叉搜索树的概念
- 二叉搜索树的性质
- 二叉搜索树的模拟实现
- 封装框架
- 添加操作
- 查找操作
- 删除操作
二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
如下图：
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
二叉搜索树的性质
- 二叉搜索树是的中序遍历是有序的！对于上图中序遍历的结果就是
[1,3,4,6,7,8,10,14,13] 有序序列
2.二叉搜索树只支持增删查,不支持修改
由于插入和删除操作都必须先查找，所以查找效率代表了二叉搜索树中各个操作的性能；
但是，对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同
可能得到不同结构的二叉搜索树：
查找时间复杂度：左边O(logN)，右边O(N)；
二叉搜索树的模拟实现
封装框架
封装节点信息
template<class K>
struct BSTreeNode //二叉搜索树封装的节点信息
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{ }
};
封装树的信息；
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
private:
Node* _root = nullptr;
}
添加操作
插入一个节点，需要和当前节点进行比较
如果插入节点小于当前节点的值，则向左走；
如果插入节点大于当前节点的值，则向右走；
如果插入节点等于当前节点的值，返回false；
bool insert(const K& key)//左小右大
{
if (_root == nullptr)//第一次插入时的操作
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* prev = nullptr;
while (cur) // 不为空就一直查找合适位置
{
if (cur->_key < key) // 插入节点大于当前节点的值，则向右走；
{
prev = cur;
cur = cur->_right;
}
else if (cur->_key > key) // 插入节点小于当前节点的值，则向左走；
{
prev = cur;
cur = cur->_left;
}
else if (cur->_key == key) // 插入节点等于当前节点的值，返回false；
return false;
}
// 到根的时候确定是根的左孩子还是右孩子
cur = new Node(key);
if (prev->_key > key)
prev->_left = cur;
else
prev->_right = cur;
return true;
}
查找操作
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;
}
删除操作
1. 删除节点没有孩子节点；
直接删除，不做处理
2. 删除节点只有左孩子节点；
该节点被删除后,将该节点的左孩子连接到该节点的父亲节点
3. 删除节点只有右孩子节点；
该节点被删除后,将该节点的左孩子连接到该节点的父亲节点
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
{
if (cur->_left == nullptr)
{ //左为空
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{ //右为空
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 最后一种情况
}
return true;
}
}
return false;
}
4. 删除节点左、右孩子节点均有；
使用替换法
被替换节点需要满足下列的条件
- 小于所有右子树的值
- 大于所有左子树的值
即左子树中的最右节点，右子树中的最左节点
代码·
// 右树的最小节点(最左节点)
Node* parent = cur;
Node* subLeft = cur->_right;
while (subLeft->_left)
{
parent = subLeft;
subLeft = subLeft->_left;
}
swap(cur->_key, subLeft->_key);
if (subLeft == parent->_left)
parent->_left = subLeft->_right;
else
parent->_right = subLeft->_right;
