前言
本文从零开始实现一棵 C++ 二叉搜索树（BST）：先定义节点结构，再实现核心的插入、查找与中序遍历，最后详细讲解删除操作（涵盖叶子节点、单子节点与双子节点三种情况）。通过完整代码与逻辑梳理，帮助读者深入理解二叉搜索树的底层原理。
1. 什么是二叉搜索树？
二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它或者是一棵空树，或者是具有以下性质的二叉树：
- 左子树上所有节点的值均小于等于根节点的值；
- 右子树上所有节点的值均大于等于根节点的值；
- 它的左右子树也分别为二叉搜索树。
注意：二叉搜索树是否支持插入相等的值取决于具体使用场景。例如，标准库中的
std::set/std::map不允许重复键，而std::multiset/std::multimap则允许。
2. 二叉搜索树性能分析
- 最优情况：树为完全二叉树（或接近完全二叉树），高度为 $O(\log_2 N)$。
- 最差情况：树退化为单支树（类似链表），高度为 $O(N)$。
- 平均时间复杂度：查找、插入、删除的平均时间复杂度为 $O(\log N)$，最差为 $O(N)$。
说明：虽然二分查找也能达到 $O(\log N)$ 的查找效率，但存在两大局限：
- 数据必须存储在支持下标随机访问的连续结构中，且保持有序。
- 插入和删除操作效率低下，通常需要移动大量元素。
3. Key 类型二叉搜索树的实现
本节实现仅存储键值（Key）的二叉搜索树，对应标准库中 set 容器的底层逻辑（默认元素唯一）。
节点结构
template<class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key = K())
: _key(key), _left(nullptr), _right(nullptr) {}
};
类结构
template<class K>
class BSTree {
using Node = BSTNode<K>;
public:
// 接口声明...
private:
Node* _root = nullptr;
};
3.1 插入
：
