C++ 手写二叉搜索树：核心操作详解
二叉搜索树的性质
二叉搜索树（BST）也叫二叉排序树，要么为空，要么满足：
- 左子树所有节点值 ≤ 根节点值。
- 右子树所有节点值 ≥ 根节点值。
- 左右子树递归满足该性质。
处理相等值时没有统一标准。std::set/std::map 不允许重复键，而 std::multiset/std::multimap 允许，这依赖具体实现。本文的实现暂不允许重复，插入时遇到相等键直接返回 false。
中序遍历 BST 能得到升序序列，因此它很适合排序和查找。但树的结构对性能影响很大：
- 完全二叉树形态下高度为 $\log_2 N$，增删查都是 $O(\log N)$。
- 有序插入会使树退化成链表，高度 N，操作降到 $O(N)$。
这正是引入 AVL、红黑树等平衡二叉搜索树的动机。尽管有序数组的二分查找也是 $O(\log N)$，但数组的插入/删除需要移动大量元素；而平衡 BST 在动态修改上优势明显。
节点与树的结构
节点用 struct 定义，方便外部访问：
template<class K>
struct BSTreeNode {
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key)
: _left(nullptr), _right(nullptr), _key(key) {}
};
树的框架需要管理资源，所以正确实现拷贝、赋值和析构必不可少。我们通过私有辅助函数完成递归逻辑。
template<class K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
// 默认构造
BSTree() = default;
// 拷贝构造
BSTree(const BSTree<K>& t) {
_root = Copy(t._root);
}
// 赋值重载
BSTree<K>& operator=(const BSTree<K> t) {
swap(_root, t._root);
return *this;
}
~() {
(_root);
}
:
{
(root == ) ;
Node* copy = (root->_key);
copy->_left = (root->_left);
copy->_right = (root->_right);
copy;
}
{
(root == ) ;
(root->_left);
(root->_right);
root;
}
:
Node* _root = ;
};
