【C++】二叉搜索树的实现-开发者社区

前言

二叉搜索树（Binary Search Tree，BST）是入门数据结构时第一个"带约束的树"。它解决的问题很朴素：在一堆键里快速找到某一个。相比线性表，它把查找从"逐个比对"变成了"每次砍掉一半"，前提是这棵树保持有序结构。

关于 BST，网上流传的说法里有两个不太准确：

其一，"BST 查找是 O(log n)"。严格说，这是平均情况，而且这个平均值依赖于输入分布；如果按有序序列插入，BST 会退化成一条链，查找退化成 O(n)。标准库的std::set/std::map之所以可靠，是因为它们用的是自平衡的树（主流实现都是红黑树），而手写 BST 没有这个保证。

其二，"中序遍历 BST 就得到有序序列"。这句话本身对，但它成立的前提是这是一棵 BST，而不是任意二叉树。对普通二叉树做中序遍历，得到的只是一串按位置访问的节点。

本文用 C++17 实现一棵完整的、能编译能跑的 BST，涵盖插入、查找、删除、遍历，并把指针管理与内存安全一起讲清楚。

一、原理：有序性从哪来

BST 的约束只有一条，但它是递归定义的：

对任意节点，其左子树中所有键都小于该节点的键；
其右子树中所有键都大于该节点的键；
左右子树各自也是 BST。

这条约束带来一个直接推论：沿任意路径向下走，键的大小关系是单调的。查找时比较一次即可决定往哪边走，因此一次比较排除一整棵子树。

操作	平均时间	最坏时间（退化成链）	说明
查找	O(log n)	O(n)	每次比较排除一半子树
插入	O(log n)	O(n)	先查找插入位置，再挂新节点
删除	O(log n)	O(n)	需要处理三种情形
中序遍历	O(n)	O(n)	每个节点恰好访问一次
空间	O(n)	O(n)	每个节点一份额外指针开销

注意"平均 O(log n)"是随机插入下的期望值，不是标准保证。要拿到稳定的对数上界，必须用平衡树。

二、节点与所有权：为什么用 std::unique_ptr

手写树最容易出的问题不是算法，而是内存。节点是new出来的，谁负责delete？如果每个节点用裸指针，就必须在析构函数里手写递归删除，中途任何一个return都可能漏掉一棵子树。

C++11 起可以用std::unique_ptr表达"父节点独占持有子节点"这个语义：unique_ptr的析构函数会自动delete它持有的对象，而该对象的析构又会级联释放它的左右孩子。整棵树的释放是自动的，不需要手写destroy函数。

代价是删除操作的写法要稍微绕一下：不能直接delete一个由unique_ptr持有的节点，必须让持有它的那个unique_ptr放弃所有权（reset）或转移所有权（std::move）。

这里有一个看起来很危险、实际安全的小技巧：写p = std::move(p->right)时，赋值会释放p原来持有的节点，而p->right正是这个节点的一个成员。之所以安全，是因为unique_ptr的移动赋值被规定为等价于先release源指针、再reset目标——释放动作发生时，源unique_ptr已经是空的了，不会二次释放。这个写法是移动语义的经典用法，不是 UB。

三、完整实现

下面的代码是完整、可编译的。请存成bst.cpp，用g++ -std=c++17 -Wall -Wextra或对应 MSVC 开关编译。

// bst.cpp — C++17 #include <cstddef> #include <initializer_list> #include <iostream> #include <memory> template<typename Key> class Bst { public: // 插入：键已存在返回 false bool insert(const Key& k) { if (insertImpl(root_, k)) { ++count_; return true; } return false; } // 查找 bool contains(const Key& k) const { const Node* cur = root_.get(); while (cur) { if (k < cur->key) cur = cur->left.get(); else if (cur->key < k) cur = cur->right.get(); else return true; } return false; } // 删除：键不存在返回 false bool erase(const Key& k) { if (eraseImpl(root_, k)) { --count_; return true; } return false; } // 中序遍历（升序） void inorder() const { inorderImpl(root_.get()); } void inorderImpl(const Node* p) const { if (!p) return; inorderImpl(p->left.get()); std::cout << p->key << ' '; inorderImpl(p->right.get()); } std::size_t size() const { return count_; } bool empty() const { return root_ == nullptr; } private: struct Node { explicit Node(const Key& k) : key(k) {} Key key; std::unique_ptr<Node> left; std::unique_ptr<Node> right; }; static bool insertImpl(std::unique_ptr<Node>& p, const Key& k) { if (!p) { p = std::make_unique<Node>(k); return true; } if (k < p->key) return insertImpl(p->left, k); // 小者左走 if (p->key < k) return insertImpl(p->right, k); // 大者右走 return false; // 相等：视为重复 } // 摘掉以 p 为根子树中键最小的节点（该节点必无左孩子） static void eraseMin(std::unique_ptr<Node>& p) { if (!p->left) { p = std::move(p->right); return; } eraseMin(p->left); } static bool eraseImpl(std::unique_ptr<Node>& p, const Key& k) { if (!p) return false; if (k < p->key) return eraseImpl(p->left, k); if (p->key < k) return eraseImpl(p->right, k); // 找到目标，分三种情形 if (!p->left && !p->right) { // 情形一：叶子 p.reset(); } else if (!p->left) { // 情形二：只有右孩子 p = std::move(p->right); } else if (!p->right) { // 情形二：只有左孩子 p = std::move(p->left); } else { // 情形三：两个孩子 // 用右子树最小键（中序后继）顶替，再摘掉那个节点 const Node* succ = p->right.get(); while (succ->left) succ = succ->left; Key succKey = succ->key; eraseMin(p->right); p->key = succKey; } return true; } std::unique_ptr<Node> root_; std::size_t count_ = 0; // 与真实节点数保持同步 }; int main() { Bst<int> t; for (int k : {50, 30, 70, 20, 40, 60, 80, 30}) { std::cout << "insert " << k << " -> " << (t.insert(k) ? "ok" : "dup") << '\n'; } t.inorder(); // 20 30 40 50 60 70 80 std::cout << '\n'; std::cout << std::boolalpha << t.contains(40) << ' ' // true << t.contains(41) << '\n'; // false t.erase(20); // 叶子 t.erase(30); // 一个孩子 t.erase(50); // 两个孩子 t.inorder(); // 40 60 70 80 std::cout << '\n'; }

运行输出：

insert 50 -> ok insert 30 -> ok insert 70 -> ok insert 20 -> ok insert 40 -> ok insert 60 -> ok insert 80 -> ok insert 30 -> dup 20 30 40 50 60 70 80 true false 40 60 70 80

3.1 删除的三种情形

删除是 BST 里最容易写错的部分，标准做法按孩子数量分三类：

情形	孩子数	处理方式	为什么
一	0（叶子）	直接摘掉	不影响其他节点
二	1	用唯一的孩子顶替自己	子树整体上移，仍然满足 BST 约束
三	2	用中序后继（右子树最小键）或中序前驱（左子树最大键）的键顶替，再删除那个节点	后继比左子树全部大、比右子树其余全部小，顶替后约束不变

情形三里，被摘掉的节点一定没有左孩子（因为它是最小值），所以它的删除必然退化成情形一或情形二，不会无限递归。

3.2 遍历方式对照

遍历	访问顺序	对 BST 的结果
前序 preorder	根 → 左 → 右	可用于序列化/复制
中序 inorder	左 → 根 → 右	键升序
后序 postorder	左 → 右 → 根	适合自底向上释放/求值
层序 level-order	逐层	需要队列辅助

常见坑点

1. 删除两个孩子节点时直接摘掉，丢掉一棵子树

❌ 看到两个孩子就p.reset()，右子树连同其中的节点一起没了。

✅ 用中序后继的键顶替，再删除后继节点；被删的后继节点没有左孩子。

2. 保存了节点指针，删除后继续用

❌ 先记下指向某节点的裸指针，然后调用erase，之后还用这个指针访问其key。erase释放该节点后，这个指针悬垂（dangling），解引用它是 UB，标准不保证任何行为。

✅ 需要跨erase保留信息时，先把键值拷贝出来。

3. 有序输入导致递归深度爆栈

❌ 依次插入 1、2、3、…、1000000，树退化成链，递归insertImpl的深度等于元素个数，栈溢出。

✅ 随机化插入顺序；或改用迭代写法；或直接用自平衡的std::set。

4. 深树析构也会爆栈

❌ 以为"析构是自动的所以没问题"。unique_ptr的删除器是递归的：释放根 → 释放左孩子 → 释放左孩子的左孩子……深度同样等于树高，退化成链时依然可能栈溢出。

✅ 极端场景下要自写迭代式释放（把子节点先摘到显式栈里）。

5. 用浮点数当键

❌ 用double作Key，插入 NaN。NaN 与任何值比较都返回 false，k < p->key和p->key < k同时为假，于是会被当成"重复键"处理，语义完全乱掉。

✅ 键类型必须能构成严格弱序（strict weak ordering）；确实要用浮点时，先定义好 NaN 的处理规则。

6. 计数器与真实节点数不同步

❌ 只在insert里++count_，erase里忘了--count_，size()与实际节点数越差越多。

✅ 让count_在每条修改路径上都更新，或者干脆去掉它、靠遍历统计（代价是 O(n)）。

7. 认为"中序遍历有序"对任意二叉树成立

❌ 对一棵普通二叉树做中序遍历，然后宣称结果已排序。

✅ 该性质只对满足 BST 约束的树成立。调试时先写一个isBst校验函数，比盯着输出猜要快得多。

8. 手写 BST 却没做平衡，还指望它有对数性能

❌ 在生产代码里用自写 BST 存用户可控的键，键恰好大致有序时性能退化。

✅ 直接使用std::set/std::map（libstdc++、libc++、MSVC STL 的实现都是红黑树），或者需要更强查找局部性时考虑 B 树 / 跳表。

总结

要点	结论
核心约束	左子树全部小、右子树全部大，递归成立
复杂度	平均 O(log n)，最坏 O(n)，取决于树高
内存管理	`unique_ptr`表达独占所有权，析构自动级联，但深树会递归爆栈
删除	三种情形，两个孩子时用中序后继顶替
中序遍历	升序输出，但仅在满足 BST 约束时成立
生产建议	优先`std::set`/`std::map`，它们自带平衡