从零开学C++：二叉搜索树

引言：在本篇博客当中，我们会将关于二叉树的进阶结构——二叉搜索树，强大的搜索效率让它在数据结构当中变得十分重要，让我们一起来进行学习吧！

更多有关C++的知识详解可前往个人主页：计信猫

一，二叉搜索树的概念

        二叉搜索树的概念其实很简单，首先它一定满足成为一颗二叉树的基本条件，其次值比根节点小的储存在左子树，值比根节点大的储存在右子树，同时它的左右子树也为二叉搜索树。如图就是一颗简单的二叉搜索树：

二，二叉搜索树的创建

        既然我们想创建一颗二叉搜索树，那么首先我们就应该创建一个二叉搜索树的节点结构体（我们称为Node），如下代码所示：

template<class k>
class Node
{
public:
Node(const k& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
Node* _left;
Node* _right;
k _key;//key为所储存的值
};

        此后我们还应该创建一个结构体专门用于二叉搜索树的遍历，数据操作，代码如下：

template<class k>
class BSTree
{
public:
using Node = Node<k>;
    Node* _root = nullptr;
};

三，二叉搜索树的数据操作函数

1，插入数据

        在二叉搜索树中，我们想插入一个值其实就非常简单了，我们分为两种情况：

        情况一：当二叉搜索树为一个空树时，那么我们就直接创建一个节点并且将这个节点赋值给_root即可。

        情况二：即不为空树时，那么我们只需要根据二叉搜索树的规则遍历到二叉树的根节点，再把数据插入即可。

        所以我们的代码如下：

//插入数据
bool insert(const k& key)
{
//情况一：根节点为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//情况二：根节点不为空
else
{
//比根节点大的放左边，比根节点小的放右边
Node* cur = _root;
Node* parent = nullptr;
//cur遍历到根节点
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
//比父节点小就插入左边，反之则插入右边
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}

 2，查找数据

        该函数的作用是查找二叉搜索树中是否存在值key，如果在遍历的过程中找到了值key，那么就返回true，若未找到值key，就返回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//相等就返回true
{
return true;
}
}
return false;
}

 3，删除数据

        删除数据函数在本篇博客中就相对复杂，但没事，我将分情况来进行一一地讲解。

（1）删除的节点左右子树都为空

        这种情况就非常简单，删除这种叶子节点（cur）我们只需要将其父节点的左右指针指向空，然后delete掉这个叶子节点即可，如下图所示：

        而该种情况可以被我们直接归类为情况（2）或情况（3） 。

（2）删除的节点左子树不为空，右子树为空

        当我们遇到这种情况的时候，我们就可以将其父节点（parent）与这个节点（cur）的左孩子相连，但连接的时候我们同时需要判断这个节点与父节点的左右关系，如果被删除节点在父节点的左边，那么我们就应该将该节点的左子树插入到父节点的左边，反之我们则插入父节点的右边。如下图所示：

        可一旦当我们遇到如下图的情况就要进行特殊处理：

        其实处理办法也很简单，我们只需要将根节点的左孩子赋值给_root，然后再删除cur节点即可。所以该情况下处理的代码如下：

else if (cur->_right == nullptr)//cur的右边为空
{
if (cur == _root)//特殊情况
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)//左孩子被删除
{
parent->_left = cur->_left;
}
else//右孩子被删除
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}

（3）删除的节点左子树为空，右子树不为空

        那么这种情况其实就可以直接类比到情况（2）了，此时我们就可以直接展示代码：

if (cur->_left == nullptr)//cur的左边为空
{
if (cur == _root)//特殊情况
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)//左孩子被删除
{
parent->_left = cur->_right;
}
else//右孩子被删除
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}

（4）删除的节点左子树和右子树都不为空

        这种情况是最麻烦的一种，但是不用担心，静下心来慢慢理解，你会发现易如反掌。那让我们以下图为例子：

        那么解决这种问题，我们就会用到一种方法，叫做替换法。替换法的含义是找到左子树的最右节点或者右子树的最左节点，来替换掉要删除的节点，再删除需要被删除的节点。语言听着很晦涩，那么我们以图来说明!

        这样，一个节点就成功被我们删除了！但是要注意，连接节点的时候还是要进行判断，若被删除的节点是在其父节点的左边，那么替换的节点也必须被连接在父节点的左边，同理，右边也是一样的。所以我们的代码如下：

//删除数据
bool erase(const k& key)
{
Node* cur = _root;
Node* parent = nullptr;
//使用cur先遍历到要删除的节点的位置
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
//相等，进行删除操作
if (cur->_left == nullptr)//cur的左边为空
{
if (cur == _root)
{
_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)//cur的右边为空
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)//左孩子被删除
{
parent->_left = cur->_left;
}
else//右孩子被删除
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
else//左右均不为空，使用替换法删除：左子树的最大值或者右子树的最小值
{
Node* replace = cur->left;
Node* replaceparent = cur;
while (replace->_right)
{
replaceparent = replace;
replace = replace->_right;
}
cur->_key = replace->_key;
if (replaceparent->_left == replace)
{
replaceparent->_left = replace->_left;
}
else
{
replaceparent->_right = replace->_left;
}
delete replace;
return true;
}
}
}
return false;
}

原文地址：https://blog.csdn.net/hu_ju_hong/article/details/142543397

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