搜索二叉树Binary Search TreeBST是数据结构里最经典的树形结构之一也是理解 std::map/std::set 底层机制的基础。很多人平时直接调用现成容器根本不会想自己手写一棵 BST可一旦开始“模拟实现”就会发现在插入、删除、遍历这些看着很简单的操作里藏着大量指针和递归的坑。这篇文章用 C 把一个可用的搜索二叉树类完整搭建出来从节点设计到拷贝控制从插入查找到最难写的删除全部过一遍最后附上我调试时踩过的坑和排查思路。适合正在学数据结构、准备校招笔试或者想把 C 内存管理基本功打扎实的开发者。1. 为什么还要自己动手写一棵搜索二叉树1.1 从“会用”到“会写”差在哪写业务代码时我们习惯了“会用”即可调标准库容器完成增删查就行。可一旦问题变成“模拟实现一棵搜索二叉树”不少看似熟练的人会卡住。原因在于接口只是最外层的一层壳真正决定性能的是树的形状、节点指针的连接、删除时的结构调整。自己动手写一遍才会直观感受到为什么需要比较器、为什么需要拷贝控制、为什么递归删除不容易出错但递归查找可能会栈溢出。这些经验不是靠背接口能获得的。1.2 搜索二叉树到底在做什么BST 的定义一句话就能说完对于任意节点左子树所有节点小于它右子树所有节点大于它。这个性质让中序遍历天然有序让查找可以每次排除一半子树所以平均时间复杂度是 O(log n)。但注意这只是平均。如果插入顺序恰好是 1、2、3、4、5BST 会退化成一条单链表查找就变成 O(n)。这一点的理解是后面学习 AVL 树、红黑树和 B 树的前提也是面试时最容易展开追问的知识点。1.3 模拟实现的功能边界我这次模拟实现不做平衡旋转目标就是普通 BST。类支持模板键类型 K提供 insert、erase、contains、inorder 四个公接口并处理好构造、拷贝、赋值、析构。插入和查找用迭代版本删除用递归版本因为递归删除逻辑最清晰也最接近教科书。后面你会看到这种取舍在普通 BST 的实现里最不容易写出 bug调试时也最好对着图说话。2. 节点设计与基础架构2.1 节点结构怎么设计先定义节点。为了模拟实现我用一个最简单的结构体里面只有键、左孩子指针、右孩子指针。不需要 parent 指针因为普通 BST 的查找和插入不需要回退删除用递归版本也不需要额外维护父节点。给每个节点构造一个完整的构造函数方便直接 new。template typename K struct BSTreeNode { K _key; BSTreeNodeK* _left; BSTreeNodeK* _right; explicit BSTreeNode(const K key) : _key(key), _left(nullptr), _right(nullptr) {} };有人喜欢把 _key 改成 _val这没关系我们后续如果要扩展成键值对容器再往节点里加一个 _value 成员就行。构造函数用 explicit 防止隐式转换这也是工程上的好习惯。命名上用下划线前缀是常见风格如果你在团队里用另外一种风格保持一致就行。2.2 类框架与接口规划树的类模板把 Node 类型用 using 包一层后续改节点类型时只改一处。公有接口控制暴露范围私有辅助函数负责递归细节。我习惯把所有递归辅助函数放在 private 区这样用户不会误调带内部状态参数的版本。template typename K class BSTree { using Node BSTreeNodeK; public: BSTree() : _root(nullptr) {} ~BSTree() { destroy(_root); } BSTree(const BSTree other); BSTree operator(BSTree other); bool insert(const K key); bool erase(const K key); bool contains(const K key) const; void inorder() const; private: Node* _root; void destroy(Node* root); Node* copy(Node* root); void inorderImpl(Node* root) const; bool eraseImpl(Node* root, const K key); };如果你愿意也可以把 BSTreeNode 定义成 BSTree 的嵌套结构但那样代码会更长。独立结构体便于单独测试也方便以后复用。2.3 构造、析构、拷贝控制默认构造只需要把根指针置空。析构必须递归释放整棵树注意释放顺序是后序遍历先删左右子树再删当前节点否则会访问已经被释放的节点。void destroy(Node* root) { if (root nullptr) return; destroy(root-_left); destroy(root-_right); delete root; }拷贝构造不能直接用默认浅拷贝否则两个对象的 _root 会指向同一片内存析构时二次释放。正确的做法是深拷贝递归复制每个节点。Node* copy(Node* root) { if (root nullptr) return nullptr; Node* newNode new Node(root-_key); newNode-_left copy(root-_left); newNode-_right copy(root-_right); return newNode; } BSTree(const BSTree other) : _root(copy(other._root)) {}赋值运算符推荐用 copy-and-swap。参数按值传递自动触发拷贝构造然后把当前对象的 _root 和临时对象的 _root 交换临时对象析构时自然释放原来的树。BSTree operator(BSTree other) { std::swap(_root, other._root); return *this; }这样就同时覆盖了自赋值和异常安全的问题。需要包含 或 才能用 std::swap。2.4 “三/五法则”在这里的教训C 里只要手动管理了堆内存就必须思考构造、析构、拷贝、赋值这一系列函数。很多初学 BST 的人只写了 insert 和 inorder测试一跑没问题等把对象放回容器或者按值传参立即崩溃。崩溃位置往往不在错误逻辑那里而在析构函数。所以我把拷贝控制放在核心操作之前讲确保后面的代码不会埋雷。3. 核心操作插入、查找与删除3.1 插入非递归实现为什么更适合插入操作不需要回溯用迭代写反而比递归更省栈空间。先处理空树再带着 parent 指针一路往下走最后根据比较结果挂到父节点的左边或右边。遇到相同 key 时直接返回 false保持键的唯一性。bool insert(const K key) { if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; Node* parent nullptr; while (cur) { parent cur; if (key cur-_key) { cur cur-_left; } else if (key cur-_key) { cur cur-_right; } else { return false; } } if (key parent-_key) { parent-_left new Node(key); } else { parent-_right new Node(key); } return true; }这里最容易忽略的是最后一步。循环结束时 cur 是 nullptr只有 parent 还指着最后一个有效节点所以必须再通过 key 和 parent-_key 的大小判断新节点应该挂在哪边。如果你在最后写成 cur new Node(key)那么新节点只是临时被 cur 指向没有真正连进树里打印结果永远少节点。3.2 查找迭代实现与 const 正确性查找与插入类似但更简单。当前节点为空说明不存在比较 key 决定往左还是往右。bool contains(const K key) const { Node* cur _root; while (cur) { if (key cur-_key) { cur cur-_left; } else if (key cur-_key) { cur cur-_right; } else { return true; } } return false; }注意 contains 是 const 成员函数它不能修改任意节点。由于我们的私有成员是 Node*在 const 函数里这个指针本身只能读但编译器并不会阻止通过该指针修改节点内容。查找逻辑里不修改任何内容所以没问题。如果你想做得更严谨可以把查找辅助函数声明成接收 const Node*但那样会增加模板类型处理的复杂度普通模拟实现没必要。3.3 删除最值得反复练习的部分删除是 BST 里最复杂的操作不能只写一次就完事。删除一个节点后必须继续保持“左小右大”的性质所以得按孩子数量分情况没有孩子直接删除让父节点对应指针置空。只有一个孩子让父节点直接指向它的唯一孩子。有两个孩子不能直接删除当前节点要用右子树最小节点或者左子树最大节点的键来替换当前节点再删除那个被用来替换的节点。用递归来写可以直接用指针引用 Node* 去修改父节点的指针省去单独维护 parent 的麻烦。下面这段是我调试了很久后沉淀下来的版本。bool eraseImpl(Node* root, const K key) { if (root nullptr) return false; if (key root-_key) { return eraseImpl(root-_left, key); } if (key root-_key) { return eraseImpl(root-_right, key); } // 找到了要删除的节点 if (root-_left nullptr) { Node* old root; root root-_right; delete old; return true; } if (root-_right nullptr) { Node* old root; root root-_left; delete old; return true; } // 左右孩子都存在用右子树最小节点替换 Node* minNode root-_right; while (minNode-_left) { minNode minNode-_left; } root-_key minNode-_key; return eraseImpl(root-_right, root-_key); }外部接口只需要一行bool erase(const K key) { return eraseImpl(_root, key); }为什么左右孩子都存在时要找右子树最小节点因为右子树里所有节点都比当前节点大而右子树的最小节点又是其中最接近当前节点的一个用它的键覆盖当前节点后仍然满足左子树都小于它、右子树都大于它的性质。左子树最大节点同理二者选其一即可。这段代码里还有一个细节当把右子树最小节点的 key 复制到当前节点后原来的 minNode 还在右子树中所以再调用 eraseImpl(root-_right, root-_key) 去删除它。因为 root-_key 已经被更新成 minNode 的 key递归路径会正确找到那个节点。minNode 本身必然没有左孩子所以要么直接删除要么只有右孩子正好落到上面两种分支里。3.4 用中序遍历验证结构的正确性插入、删除都写完后最直接的验证方式就是中序遍历。BST 的中序遍历结果一定是严格升序因为遍历顺序是左子树、当前节点、右子树。void inorder() const { inorderImpl(_root); std::cout std::endl; } private: void inorderImpl(Node* root) const { if (root nullptr) return; inorderImpl(root-_left); std::cout root-_key ; inorderImpl(root-_right); }我用一组数据简单测过依次插入 5、3、7、2、4、6、8中序输出是 2 3 4 5 6 7 8。接着删除 3再删除根节点 5输出依然是有序的。每次操作后都跑一遍中序是排查结构是否被破坏最重要的手段。4. 实操细节与调试心得4.1 支持自定义类型扩展比较器目前代码里直接用 key cur-_key 做比较对 int、double、string 都没问题。但如果键是自定义结构体你又想按某个字段排序就需要给类增加比较器模板参数。标准库容器都支持这种设计我们模拟实现时也可以抄过来。template typename K, typename Compare std::lessK class BSTree { ... private: Compare _comp; bool isLess(const K a, const K b) const { return _comp(a, b); } };插入、查找、删除里的比较逻辑全部改成 isLess(key, cur-_key) 这种写法。默认构造时 _comp 会调用默认构造函数不需要额外初始化。这样 BSTree 就可以传一个自定义仿函数按业务规则比较对象并不复杂。4.2 重复键、异常安全与 const 接口当前插入遇到相同 key 返回 false这对应 std::map/std::set 的唯一键语义。如果你想要 std::multiset 的效果把插入里相等的分支改为继续往右走或者给节点加计数就能支持重复键。异常安全方面插入用 new 分配节点可能抛 bad_alloc异常发生时树结构没有被破坏因为还没有把新节点连接进去这部分是安全的。拷贝复制时如果中途抛异常我们的 copy 函数会泄漏已分配的节点严谨一点可以用 try-catch 包裹释放普通练习可以暂时不处理。const 接口重点在 contains 和 inorder。查找不应该修改树中序遍历也不能修改节点所以都把函数声明为 const。插入和删除会修改结构保持非 const。这样的接口设计是容器类的基本素养。4.3 我反复踩过的坑排查速查表整理一张表格遇到类似问题可以直接对照。现象可能原因排查方法插入后中序少了节点新节点没有挂到树上比如最后用 cur 而不通过 parent 连接单步跟踪插入函数检查 parent 的左右指针删除后部分子树丢失删除只有一个孩子的节点时没有先保存旧节点再处理孩子指针画节点关系图确认指针赋值的先后顺序中序不是升序比较逻辑写反或者插入时左右挂错逐个节点检查 _key 与左右孩子的大小关系程序析构崩溃浅拷贝导致两个对象共享同一棵树的节点检查拷贝构造是否深拷贝赋值是否用 copy-and-swap递归栈溢出插入顺序接近有序BST 退化成链表打印树的高度改用平衡树或打乱插入顺序我自己最深的体会是删除操作不能只在脑子里面想必须拿纸笔把“当前节点、父节点、孩子节点”画出来。尤其是两个孩子的替换法画一遍比写十个测试用例都管用。4.4 一个可视化的调试辅助函数中序遍历只能验证有序性看不到树长什么样。调试时可以加一个纵向打印的函数用前序遍历输出节点和缩进层次强一些。或者更简单用层序遍历的思想一行一行打印。我常用的一个简易函数是递归先打印右子树再打印当前节点最后左子树用控制台方向模拟树结构。虽然丑但至少能直观看到退化和缺失。5. 从模拟到应用的下一步5.1 搜索二叉树帮你理解标准容器有了这棵手写 BST再回头看 std::map 的用法你会发现底层无非是给树节点增加了 value 和颜色字段再在插入删除后做旋转调平衡。std::set 则只保存 key内部结构和 BSTree 非常像。理解普通 BST 是理解红黑树、AVL 树的第一步也是理解有序容器和哈希容器区别的起点。面试时如果能把“有序性从哪来、复杂度为何退化”讲清楚就已经超过很多人。5.2 扩展成简易版 key-value 容器把节点改成两个成员一个保存 key一个保存 value插入时传入 pair查找时把 value 带出来就是一个简化版的标准 map。具体改动很小节点里加一个 V _valueinsert 接受 key 和 valuecontains 改为 find返回 Node* 或一个可选值。再复杂一点可以增加 operator[]用 key 找到对应 value不存在时自动插入默认值。这也是很多 C 面试题的进阶版非常推荐自己动手改一版。5.3 从普通 BST 走向平衡树普通 BST 的致命弱点是插入顺序可能让它退化成链表。解决思路只有一条在插入和删除后调整树的形状保证任何路径的长度不会相差太多。AVL 树要求左右子树高度差不超过 1红黑树用颜色规则实现弱平衡操作更少但逻辑更绕。基础打牢之后可以先写 AVL 的旋转再尝试红黑树。你会发现之前手写的删除经验在平衡树里仍然适用只是多了一步恢复平衡。最后分享一个小技巧学 BST 时一定要做“每个关键步骤都打印一次中序”的调试习惯。我当年写删除函数前两次都栽在“两个孩子的替换”上不是没有找到最小节点就是递归返回值没有接到父指针上。后来老老实实把 eraseImpl 的参数改成 Node*一个问题都不剩了。如果你也在模拟实现 C 搜索二叉树建议先跑通插入和查找再写删除每写一个函数就输出一次中序验证等这些全稳定后再尝试 AVL 树和红黑树会发现那个难啃的骨头已经没那么可怕了。