去年做一个内部工具时我需要维护一份动态变化的“热点数据排名”数据量不大但要求能随时按序输出、快速查询某个键值是否在库中。最初我直接用了std::map一切顺利但后来有个同事问std::map的底层到底是啥为什么迭代顺序总是有序的我意识到自己对二叉搜索树的实现细节其实是一知半解的——真正面试、阅读源码、甚至将来理解 AVL 和红黑树时都需要先跨过“手写一棵 BST”这道坎。于是我用 C 从头实现了一个二叉搜索树覆盖插入、查找、删除、遍历和辅助查询过程中踩了不少坑也补全了不少关于递归、指针和边界条件的认知。这篇文章就把这套实现完整记录下来适合刚学完 C 基础、想动手做数据结构练习的读者也适合需要自己实现有序容器、希望理解 BST 原理的开发者。我会把每一步的“为什么这么设计”一并讲清楚而不是只丢代码。1. 为什么还要自己写一棵二叉搜索树1.1 标准库已经在用 BST但封住了你的视线先问个问题如果你只想排序、查重直接用std::set不就行了确实可以。C 标准库里的std::map和std::set底层大多是红黑树——红黑树就是一棵自平衡的二叉搜索树。但问题在于库把平衡、旋转、节点分裂这些细节完全封装了你只看到insert、find、erase这几个接口。我自己写 BST首先是为了看清那个“黑盒”内部到底长什么样。举个最简单的问题std::map的迭代器为什么能按 key 有序输出答案就在二叉搜索树的中序遍历里——先访问左子树、再访问根、最后访问右子树就能得到从小到大排列的序列。但如果你没亲手实现过中序递归这个解释始终只是一个结论。1.2 从项目需求倒推什么场景需要“裸树”除了学习目的我这里有个更实际的理由并不是所有有序动态数据都能直接用标准库容器解决。比如说你的数据带有“优先级”和“时间戳”两个维度想在同一个容器里同时维护两份索引或者想在 key 有序之外还能快速知道排名第 k 大的元素是哪个。标准库里没有现成的“按排名查找”接口你只能每次遍历。但如果自己实现一棵带size计数的 BST就可以用子树节点数量快速回答“这个区间的元素有多少”“倒数第 10 名是谁”之类的问题。这是手写 BST 比直接用std::map更灵活的地方。另外二叉搜索树是 AVL 树、红黑树、B 树这些更复杂结构的基石。你不可能一上来就写出旋转逻辑但理解了普通 BST 的递归结构之后再去看那些平衡方案思路会顺畅很多。所以这篇文章里的实现虽然不包含自平衡但它是一切后续结构的地基。// 最低限度的思维预备BST 的定义 // 对于每个节点 node // node 左子树中所有节点的值 node 的值 // node 右子树中所有节点的值 node 的值 // 左右子树本身也是一棵 BST这个定义听起来简单但是写代码时你很快会发现最难的往往不是定义而是“删除节点之后如何还满足这个定义”。2. 节点结构与接口设计先画好骨架再动手2.1 节点定义一版够用的代码我习惯用类模板实现这样树能存int、float、自定义对象适配面试或项目里的常见需求。节点结构很简单三个指针成员加一个值成员template typename T struct BSTNode { T val; BSTNodeT* left; BSTNodeT* right; explicit BSTNode(const T v) : val(v), left(nullptr), right(nullptr) {} };有几个细节值得专门说left和right一定要初始化为nullptr。我早期写代码经常漏掉初始化结果插入时就炸了因为随机的野指针会让树的结构完全错乱。构造函数里用explicit避免临时构造隐式转换比如误把整数隐式转换成节点。如果你存的是字符串、结构体等类型T需要支持operator和operator或至少是能比较大小的类型。2.2 接口清单与返回值约定我最终确定的对外接口如下接口功能返回值说明bool insert(const T v)插入一个值插入成功返回 true已存在返回 falsebool erase(const T v)删除一个值删除成功返回 true未找到返回 falsebool contains(const T v)查找是否存在存在 true否则 falsevoid inorder()中序遍历输出无返回值int height()返回树高度空树返回 -1T minValue()/T maxValue()返回最小/最大值调用者需保证树非空返回值约定上我统一采用“操作是否成功”作为布尔值而不是把“查不到”用-1这样的魔法数表示。对泛型类型来说-1可能是一个合法的数据值所以用bool更稳妥。关于查找的另一种设计是返回指向节点的指针BSTNodeT* find(const T v);这用处很大以后做 AVL 树的旋转时你需要拿到某个节点的指针去操作。这里我保留一个私有方法findNode对外暴露contains更安全一些。3. 插入与查找递归写起来爽迭代用起来稳3.1 插入递归版本为什么好写插入逻辑非常符合 BST 的定义从根出发如果待插入值比当前节点小就向左走比当前节点大就向右走直到碰到空位置把它挂上去。template typename T bool BSTreeT::insert(const T v) { if (!root_) { root_ new BSTNodeT(v); size_; return true; } return insertRec(root_, v); } template typename T bool BSTreeT::insertRec(BSTNodeT* node, const T v) { if (!node) { node new BSTNodeT(v); size_; return true; } if (v node-val) { return insertRec(node-left, v); } else if (v node-val) { return insertRec(node-right, v); } return false; // 已存在 }递归版本的关键在于参数类型是BSTNodeT*——指针的引用。这样在node new ...时修改的是父节点中那个指针变量本身而不是局部副本。这一点特别重要如果参数写成BSTNodeT* node新节点虽然创建了但父节点的左或右指针仍然停留在空状态树就“丢”了节点后面查不到。为什么不统一用迭代递归写法直观逻辑和定义一一对应代码不容易错。缺点也很明显树高度如果达到几千层递归可能栈溢出。所以更稳的工程实现常把插入写成迭代版本template typename T bool BSTreeT::insertIter(const T v) { BSTNodeT** cur root_; while (*cur) { if (v (*cur)-val) { cur ((*cur)-left); } else if (v (*cur)-val) { cur ((*cur)-right); } else { return false; } } *cur new BSTNodeT(v); size_; return true; }这里用二级指针的引用用法BSTNodeT**非常顺手循环里直接修改cur为某个子指针的地址找到空位后通过*cur ...完成挂接。既不用记录父节点也不用特判根节点是否为空。如果你是第一次手写 BST建议把这两个版本都写一遍能加深对“指针是变量的地址”这件事的理解。3.2 查找标准实现与短路条件查找和插入遵循同一套导航逻辑template typename T bool BSTreeT::contains(const T v) const { BSTNodeT* cur root_; while (cur) { if (v cur-val) { cur cur-left; } else if (v cur-val) { cur cur-right; } else { return true; } } return false; }为什么查找不用递归因为查找不需要修改树结构迭代就足够清晰高效而且没有递归栈溢出的风险。这里每一步都走向正确的子树时间复杂度是 O(h)h是树高。最好情况下h是 O(log n)最坏情况比如按升序插入树退化成链表h就到 O(n) 了。这一点我在后面第 7 节会专门展开。3.3 递归深度被数据顺序坑过一次我第一版插入用的纯递归调试时插入 1 到 100000 的有序序列程序直接崩溃了。查了下栈深度树高 100000每层递归都要分配栈帧当然爆了。后来我把插入改成迭代版本再把inorder的递归遍历也改成栈模拟才算稳定。这个教训让我意识到别高估递归的优雅工程上要随时评估最坏情况下的栈开销。4. 删除操作三种情况的完整拆除流程这是整个 BST 实现里最核心、也最容易写崩的部分。删除节点时的难点在于删完之后剩下的节点仍然要构成一棵合法的 BST。4.1 情况划分叶子、单分支、双分支叶子节点没有左右孩子直接删掉父节点对应的指针置为空。只有一个子节点用唯一的子节点顶替被删除节点的位置。有两个子节点这种情况最麻烦。不能直接删除因为左右两个孩子都需要保留而且要保持有序性。4.2 双分支的替换删除法用前驱还是后继处理双分支的标准方案是找到被删除节点的中序前驱或中序后继把它放进被删除节点里然后删除前驱/后继所在节点。中序前驱左子树中值最大的节点即左子树一直往右走到头。中序后继右子树中值最小的节点即右子树一直往左走到头。比如要删除一个值为 50 的根节点它的左子树最大值是 45右子树最小值是 60。用 45 或 60 替换掉 50都还能保证整棵树有序。选哪个通常看左/右子树谁更浅但在这里我统一选后继右子树最小因为实现简单而且可以把问题转化成“删除右子树里一定只有一个或没有子节点的节点”——后继节点不可能有左孩子这就把一个双分支问题降级成了单分支或叶子问题。4.3 完整删除代码与边界验证我用递归实现删除的核心函数参数仍然用指针引用这样父节点指针可以即时更新template typename T bool BSTreeT::erase(const T v) { return eraseRec(root_, v); } template typename T bool BSTreeT::eraseRec(BSTNodeT* node, const T v) { if (!node) { return false; } if (v node-val) { return eraseRec(node-left, v); } else if (v node-val) { return eraseRec(node-right, v); } // 找到目标节点 if (!node-left) { // 只有右子树或没有子树 BSTNodeT* tmp node-right; delete node; node tmp; } else if (!node-right) { // 只有左子树 BSTNodeT* tmp node-left; delete node; node tmp; } else { // 有两个子节点找右子树的最小值作为后继 BSTNodeT* succ findMinNode(node-right); node-val succ-val; // 值覆盖 eraseRec(node-right, succ-val); // 删掉后继 } return true; } template typename T BSTNodeT* BSTreeT::findMinNode(BSTNodeT* root) { if (!root-left) return root; return findMinNode(root-left); }代码里的findMinNode返回的是指针引用这样不仅能拿到最小节点还能得到指向它的指针本身方便删除时更新。我最初写成BSTNodeT*返回删除后继时会发现父节点的左孩子没有被置空导致树里残留一个悬空指针。后来改成引用返回问题迎刃而解。这里有两个边界情况需要反复测试删除根节点比如树只有一个节点删除后root_要变为nullptr。eraseRec(root_, v)中的node正是root_的引用所以能正确更新。连续删除后有新插入删除后size_要对应递减。我在代码里没有显示处理size_实际使用时要记得在成功删除后减一否则容器大小不对。另外关于“值覆盖”和“指针替换”我采用值覆盖。这种做法简单但有个隐患如果有外部指针指向被删除节点的地址那么值覆盖后外部指针依然存活但内容变了。如果你期望删除后外部指针失效那就应该继续用指针替换方式删除后继。这是面试时经常会讨论的细节值得自己动手对比一下。5. 遍历、高度和其他辅助方法让树真正可用5.1 中序遍历输出有序序列的基础BST 最大的价值之一就是中序遍历能直接得到有序序列。template typename T void BSTreeT::inorderRec(BSTNodeT* node) const { if (!node) return; inorderRec(node-left); std::cout node-val ; inorderRec(node-right); }递归版本代码短但如果树高很大依然有栈溢出风险。我在实际测试中会用一个显式栈版本用栈模拟系统递归template typename T void BSTreeT::inorderIter() const { std::stackBSTNodeT* st; BSTNodeT* cur root_; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); std::cout cur-val ; cur cur-right; } }这个迭代版本是经典的“一路向左压栈弹栈后转向右孩子”的逻辑。第一次写时很容易忘记在弹栈后把cur设置为右孩子导致死循环。我的经验是在纸上画一棵三层的树手动模拟一遍栈的变化比盯代码调试管用得多。5.2 高度与深度递归里传递了什么信息高度定义为从根到最远叶子节点的边数。空树高度我设为 -1单节点高度为 0。递归逻辑就是“左子树高度和右子树高度的较大者再加 1”template typename T int BSTreeT::heightRec(BSTNodeT* node) const { if (!node) return -1; int leftH heightRec(node-left); int rightH heightRec(node-right); return std::max(leftH, rightH) 1; }如果你把空树高度设为 0那么单节点高度就是 1两种情况各有约定。需要保证所有接口里的约定一致。我曾经在height和删除逻辑中混用两套约定测试时发现平衡判断全乱了。5.3 查找最小值/最大值与第 k 小元素最小值就是一直向左走最大值一直向右走这个没什么好说的。更有趣的是第 k 小问题。标准 BST 节点里没有记录子树大小所以找第 k 小只能遍历效率不高。我在节点里加了一个int n;表示该子树节点总数插入时在路径上各节点n删除时反向递减然后查找第 k 小就能做到template typename T T BSTreeT::kthSmallest(int k) const { BSTNodeT* cur root_; while (cur) { int leftSize cur-left ? cur-left-n : 0; if (k leftSize) { cur cur-left; } else if (k leftSize 1) { return cur-val; } else { k - (leftSize 1); cur cur-right; } } throw std::out_of_range(kthSmallest out of range); }这个功能在比赛和业务里很实用比如“找到成绩排名第 5 的学生”。标准库容器没有直接等价接口自己实现却非常简单。前提是你要在插入和删除的每个递归或迭代路径上正确维护n。插入时从根到叶子路径上所有节点n删除时对应路径上所有节点n--。这算是对“子树大小维护”的一个入门练习。6. 测试驱动用一组用例把树“拷问”到位写完成套代码之后我用一个相对系统的测试方案来验证实现。你不需要什么测试框架单纯用 main 函数加断言就够了。6.1 直接测根、叶子和链状结构我测试的第一批用例针对最基础功能用例操作期望结果1插入 5contains(5) 为 true2插入 3、8、2、4中序输出 2 3 4 5 83重复插入 5insert 返回 falsesize 不变4查找不存在的 10contains 返回 false5删除叶子 2中序输出 3 4 5 8这个过程中发现一个非常隐蔽的 bug我在删除叶子时把节点删除后忘了处理父节点指针导致父节点的左孩子仍然指向被释放的内存。后续查找时访问野指针程序时对时错。后来检查代码才发现我没有用指针引用而是传的指针副本。这个问题在第 4 节已经修复但这提醒我每次测试插入和删除之后都要用中序遍历验证整棵树结构是否仍然有序——单测能判断插入是否成功但无法直接暴露指针悬挂。6.2 删除测试专项把每种情况都覆盖一遍删除的专项测试我分成四组删除根节点它没有左孩子只有右子树——验证指针更新。删除根节点它有两个孩子——验证后继替换。删除一个有两个孩子的中间节点——验证子树重接。连续删除多个节点直到树为空——验证 size 递减到 0root_变为 nullptr。关键的删除用例我贴一段实测代码// 构造一棵树10, 5, 15, 3, 7, 12, 20 BSTreeint t; for (int v : {10, 5, 15, 3, 7, 12, 20}) t.insert(v); t.erase(10); // 双分支后继是12用12覆盖10 t.inorder(); // 期望3 5 7 12 15 20 assert(!t.contains(10)); assert(t.contains(12));实际运行中我发现删除双分支的根节点之后树的中序输出满足有序但树的形状不一定正确——比如后继的右子树上去了且后继原来所在的父节点指针没有正确断开。我通过打印每个节点的左右孩子地址来检查。后来把findMinNode返回类型改成指针引用后问题才彻底解决。6.3 测试过程中发现的真实 bug这里列两类值得分享的问题析构函数没有释放所有内存。我只写了erase单个节点忘了在析构函数里递归删除。结果程序退出时报_BLOCK_TYPE_IS_VALID断言一看就是内存泄漏/重复释放。解决方式是写一个clear()递归删除所有节点template typename T void BSTreeT::clearRec(BSTNodeT* node) { if (!node) return; clearRec(node-left); clearRec(node-right); delete node; }拷贝构造和赋值运算符浅拷贝。当我用BSTreeint t2 t1;时两个对象的root_指向同一块内存。析构时一个对象释放内存另一个对象再析构就要二次释放。我给类补上了拷贝构造、拷贝赋值和移动语义或者用std::unique_ptr管理节点所有权。如果你只想快速测试可以暂时禁用拷贝BSTree(const BSTree) delete; BSTree operator(const BSTree) delete;但完整项目里最好还是实现深拷贝或者移动语义否则容易出事。7. 不可忽视的缺陷与后续演进方向7.1 不平衡问题有序插入就是灾难普通 BST 最致命的缺陷就是结构完全取决于插入顺序。插入随机数据时树相对平衡但如果数据恰好按升序或降序插入树就变成一条链表插入、查找、删除全部退化到 O(n)。我自己实测过一组数据插入 1 到 10000 的随机整数树高大约是三十几但插入 1 到 10000 的严格升序序列树高直接到 9999。这个差距对实时性要求高的业务是灾难。解决思路要么是打乱插入顺序要么做平衡对应到工程上就是 AVL 树、红黑树、替罪羊树、伸展树等方案。如果你想从普通 BST 平滑演进到 AVL第一步可以给节点增加高度字段第二步在每个插入和删除递归回溯时检查左右子树高度差第三步实现单旋转和双旋转。这个迭代很有价值因为 AVL 的旋转逻辑在普通 BST 代码里也能做局部验证——我在自己实现 AVL 时就是在删除了这棵基础 BST 代码的几个函数基础上改出来的。7.2 递归深度与释放内存递归是 BST 实现里最自然的写法但也是隐患。普通递归版本在树高极大时会栈溢出这个前面已经说了。工程上可以有两种改进一是把“高递归风险”的函数比如查找、插入、遍历改成迭代二是调整递归终止条件把尾递归改写成循环。对于删除这种递归结构比较强的情况也可以用迭代版删除但代码会复杂许多。我的建议是明确你的数据规模如果高度很可能超过几百甚至上千就用迭代为主如果只是练习递归完全够用而且更容易读。内存释放上一定要配套析构函数。我用std::vector辅助验证树内所有节点都已释放插入 10000 个随机数统计进程内存占用退出前后做对比。条件允许的话用valgrind或 ASAN 检测能精准看到哪块内存没释放。这也是 C 手写数据结构绕不开的一环。7.3 向平衡树演进AVL 和红黑树该怎么迈出第一步动笔写平衡树之前先把这篇里的基础 BST 吃透尤其要理解“前驱/后继”“指针引用”“递归回溯”这三个点。AVL 树是在插入、删除后从被修改的位置沿着递归栈往上回溯检查平衡因子红黑树则是通过颜色标记和旋转维护平衡。普通 BST 的代码里递归版本的插入和删除已经天然具备了“回溯”过程只需要在每一层递归返回前补上旋转逻辑就能升级成 AVL。具体的做法是把搜索树节点里的val、left、right保持不动增加int height;每次插入后更新当前节点高度然后做旋转。如果你现在没时间写 AVL也可以在业务里先记录一下实际数据分布如果插入顺序基本随机那普通 BST 的复杂度通常是够用的如果数据有序性很强就别心存侥幸老老实实上平衡方案或者直接用std::map。以我个人经验来看手写 BST 最大的收获不是“我会写树了”而是理解了“递归和指针如何协同描述一种递归的数据结构”。之后你去看任何平衡树源码都会轻松很多至少不会在看到RRotation、LLRotation这些函数名时发怵。这一版实现我自己保留了好几个迭代版本每次换不同场景重写都能发现新的理解盲区。建议你也把它当成一块实验田不断往里面加功能、改设计踩过真实的坑才算真正拥有这棵树。