【C++】 二叉搜索树的实现

前言二叉搜索树Binary Search TreeBST是入门数据结构时第一个带约束的树。它解决的问题很朴素在一堆键里快速找到某一个。相比线性表它把查找从逐个比对变成了每次砍掉一半前提是这棵树保持有序结构。关于 BST网上流传的说法里有两个不太准确其一BST 查找是 O(log n)。严格说这是平均情况而且这个平均值依赖于输入分布如果按有序序列插入BST 会退化成一条链查找退化成 O(n)。标准库的std::set/std::map之所以可靠是因为它们用的是自平衡的树主流实现都是红黑树而手写 BST 没有这个保证。其二中序遍历 BST 就得到有序序列。这句话本身对但它成立的前提是这是一棵 BST而不是任意二叉树。对普通二叉树做中序遍历得到的只是一串按位置访问的节点。本文用 C17 实现一棵完整的、能编译能跑的 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都可能漏掉一棵子树。C11 起可以用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 -stdc17 -Wall -Wextra或对应 MSVC 开关编译。// bst.cpp — C17 #include cstddef #include initializer_list #include iostream #include memory templatetypename 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_ptrNode left; std::unique_ptrNode right; }; static bool insertImpl(std::unique_ptrNode p, const Key k) { if (!p) { p std::make_uniqueNode(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_ptrNode p) { if (!p-left) { p std::move(p-right); return; } eraseMin(p-left); } static bool eraseImpl(std::unique_ptrNode 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_ptrNode root_; std::size_t count_ 0; // 与真实节点数保持同步 }; int main() { Bstint 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 803.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 与任何值比较都返回 falsek 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::maplibstdc、libc、MSVC STL 的实现都是红黑树或者需要更强查找局部性时考虑 B 树 / 跳表。总结要点结论核心约束左子树全部小、右子树全部大递归成立复杂度平均 O(log n)最坏 O(n)取决于树高内存管理unique_ptr表达独占所有权析构自动级联但深树会递归爆栈删除三种情形两个孩子时用中序后继顶替中序遍历升序输出但仅在满足 BST 约束时成立生产建议优先std::set/std::map它们自带平衡BST 的价值不在于能存数据而在于它用一条极简约束换来了可预测的查找路径。真正的工程结论是有序结构必须配平衡否则它的性能上界和链表没有区别。