目录
在数据结构与算法的世界里，二叉搜索树（Binary Search Tree，简称BST）是一种非常重要的数据结构，它以其高效的查找、插入和删除操作，在众多应用场景中发挥着关键作用。本文将通过一段C++ 代码，详细解析二叉搜索树的实现过程。
二叉搜索树简介
二叉搜索树是一种特殊的二叉树，它满足以下性质：
- 对于树中的每个节点，其左子树中所有节点的值都小于该节点的值。
- 对于树中的每个节点，其右子树中所有节点的值都大于该节点的值。
基于这些性质，二叉搜索树能够在平均情况下以O(\log n) 的时间复杂度完成查找、插入和删除操作，其中n 是树中节点的数量。
代码结构
我们来看的这段C++ 代码定义了一个 BSTree 类，用于实现二叉搜索树。代码主要包含以下几个部分：
1. 节点定义： Node 结构体定义了二叉搜索树的节点，每个节点包含一个键值 _key 以及指向左子节点和右子节点的指针 _left 和 _right 。
cpp
template<class K>
struct BSTreeNode
{
BSTreeNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
K _key;
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
};
1. 树类定义： BSTree 类包含了二叉搜索树的主要操作，如插入、删除、搜索等，并且包含一个指向根节点的指针 _root 。
cpp
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
// 插入操作
bool insert(const K& key)
{
// 代码实现...
}
// 删除操作
bool erase(const K& key)
{
// 代码实现...
}
// 搜索操作
bool Find(const K& key)
{
// 代码实现...
}
private:
Node* _root;
};1. 测试函数： TestBtNode 函数用于测试二叉搜索树的功能，通过创建一个 BSTree 对象，并向其中插入一些数据，然后进行相关操作的测试。
cpp
void TestBtNode()
{
int arr[] = { 8,3,1,10,6,4,7,14,13 };
BSTree<int> t;
for (auto e : arr)
{
t.insert(e);
}
t._InOrder();
}核心操作实现详解
插入操作（insert）
插入操作是向二叉搜索树中添加新节点的过程。其基本思路是从根节点开始，根据要插入的值与当前节点值的大小关系，决定向左子树或右子树移动，直到找到合适的插入位置。
cpp
bool insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = 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;
}在这段代码中，首先判断根节点是否为空，如果为空则直接创建新节点作为根节点。否则，通过一个循环，在树中找到合适的插入位置，最后将新节点插入到相应的位置。
删除操作（erase）
删除操作相对复杂一些，需要考虑多种情况：
1. 删除节点为叶子节点：直接删除该节点。
2. 删除节点只有左子树或右子树：用子树替换该节点。
3. 删除节点左右子树都存在：通常有两种方法，一种是用左子树的最大值节点或右子树的最小值节点替换该节点，然后删除替换节点。这里采用的是用左子树的最大值节点替换。
cpp
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 (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
// 双不为空
else
{
Node* parent = cur;
Node* lm = cur->_left;
while (lm->_right)
{
parent = lm;
lm = lm->_right;
}
// 交换
swap(cur->_key, lm->_key);
if (parent->_left == lm)
{
parent->_left == lm->_left;
}
else
{
parent->_right == lm->_left;
}
cur = lm;
}
delete cur;
return true;
}
}
return false;
}
代码中首先找到要删除的节点，然后根据不同情况进行处理。如果是叶子节点或单支节点，直接进行删除和子树连接操作；如果是左右子树都存在的节点，找到左子树的最大值节点，交换值后删除该节点。
搜索操作（Find）
搜索操作是在二叉搜索树中查找指定值的过程。通过比较当前节点的值与目标值的大小关系，决定向左子树或右子树继续查找，直到找到目标值或遍历完整个树。
cpp
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;
}这段代码通过一个循环，从根节点开始，不断比较当前节点值与目标值，直到找到目标值返回 true ，或者遍历完树未找到返回 false 。
测试与验证
在 TestBtNode 函数中，通过创建一个 BSTree 对象，并向其中插入一组数据 { 8,3,1,10,6,4,7,14,13 } ，然后可以调用相关操作进行测试，例如搜索某个值是否存在，删除某个节点等。虽然代码中 t._InOrder() 这里的 _InOrder 方法未给出实现（推测是中序遍历用于打印树的节点），但我们可以补充一个简单的中序遍历实现来查看树的结构：
cpp
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
std::cout << root->_key << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
std::cout << std::endl;
}
通过调用 InOrder 方法，我们可以看到插入数据后的二叉搜索树按照中序遍历的结果，即节点值从小到大排列，验证二叉搜索树的性质。
总结
本文通过详细解析一段C++ 代码，介绍了二叉搜索树的基本概念、核心操作的实现原理以及测试方法。二叉搜索树作为一种重要的数据结构，其高效的查找、插入和删除操作使其在许多算法和实际应用中都有着广泛的应用。理解和掌握二叉搜索树的实现，对于进一步学习更复杂的数据结构和算法具有重要意义。 同时，代码中也存在一些可以优化和改进的地方，例如增加内存管理的安全性检查，添加更多的辅助函数来提高代码的可读性和可维护性等。希望本文能帮助读者更好地理解二叉搜索树及其实现过程。