拓冰网站定制 
1. 项目概述1.1 核心需求与适用场景二叉搜索树Binary Search Tree简称 BST是 C 学习路线上绕不开的一个基础数据结构。我在接触它之前链表和数组已经用得比较顺手了但一到需要“快速查找某个元素”的场景总感觉不够痛快——数组的二分查找虽然高效却要求数据必须是有序的链表倒是方便插入删除了可查找只能从头遍历时间复杂度直接拉满到 O(n)。二叉搜索树正好把这两个需求平衡在一个结构里查找、插入、删除的平均时间复杂度都可以做到 O(log n)。这节课按照章节编号应该是一个系列课程中的第二章节第三小节是我自己在学习过程中重新手动实现一遍 BST 的记录。它的适用人群很明确正在上数据结构课的学生、准备 C 面试的求职者、以及那些看过很多遍理论却一直没有独立写完一棵树的“理论派”程序员。看完这篇博文你能独立写出一个支持插入、查找、删除、遍历的完整 BST 类并且能够回答“为什么删除节点要分三种情况”这类面试常问问题。1.2 为什么用 C 实现二叉搜索树不少初学者会问用 C 语言也能实现 BST为什么非要选 C我的感受是C 在这里提供了一个非常好的“中间地带”。你既可以用 struct 定义节点、用指针维护树形关系这部分和 C 语言很像能帮助理解底层内存布局又可以借用类封装、构造函数、析构函数这些 C 特性让代码更安全、更易调试——尤其是析构函数负责递归释放内存这件事手动管理过 C 语言版本的人一定深有体会稍不注意就内存泄漏。另外C 标准库里的std::map和std::set底层就是红黑树一种自平衡的 BST 变体面试里经常被问到它们的实现原理。如果你连最基础的 BST 都没手写过直接看红黑树的旋转逻辑基本等于看天书。所以我一直建议先把普通 BST 写透再去碰平衡树这条路是最顺的。2. 实现前的设计与思考2.1 节点结构的定义方式BST 的节点结构其实非常简洁就是三个成员一个存储数据的键值一个指向左子树的指针一个指向右子树的指针。写成代码是这样template typename T struct BSTreeNode { T key; // 存储的数据 BSTreeNodeT* left; // 左子树指针 BSTreeNodeT* right; // 右子树指针 explicit BSTreeNode(const T val) : key(val), left(nullptr), right(nullptr) {} };我在这里使用了模板template这样数据可以是 int、float甚至自定义类型。如果你刚开始学先不要急着上模板把 key 直接定义成 int 写通逻辑再改成模板会容易得多。构造函数的参数列表里使用const T而不是T是为了避免不必要的拷贝开销这是一种工程上常见的写法。关于“为什么节点要单独用 struct 而不是 class”我的习惯是当这个类型只是承载数据、没有复杂的逻辑操作时用 struct 就够了所有成员默认公开访问起来方便而树本身涉及较多的封装逻辑更适合用 class。这种“struct 负责数据、class 负责逻辑”的划分方式在 C 项目里比较常见也符合直觉。2.2 树的类骨架与接口设计树类需要对外提供哪些能力通常包括插入、查找、删除、遍历、清空析构函数。我把接口设计成这样template typename T class BSTree { public: BSTree() : root_(nullptr) {} ~BSTree() { clear(); } bool insert(const T key); // 插入节点返回是否成功 bool erase(const T key); // 删除节点返回是否成功 bool contains(const T key) const; // 查找节点是否存在 void inorder() const; // 中序遍历用于验证有序性 void clear(); // 清空整棵树 private: BSTreeNodeT* root_; // 各种递归辅助函数的声明这里先留空 };一个很重要的设计决定就是对外公开的接口尽量精美、简洁而真正干活儿的递归逻辑都放到 private 辅助函数里。比如insert对外只是一个返回 bool 的函数内部会调用一个递归函数来完成真正的插入工作。这样做的好处有两个一是用户不需要关心递归的入口参数尤其是根节点二是树的内部结构完全对外隐藏后续如果要改成 AVL 树或者红黑树接口可以保持不变只需要改私有实现。2.3 C 特有的内存管理问题C 实现的 BST 和 Java、Python 一个很大的区别就是内存管理。Java 有垃圾回收Python 有引用计数而 C 要求你手动释放。每次 new 出来的节点最后都必须有一个与之匹配的 delete。否则就会出现内存泄漏——程序运行时间越长占用内存越大最终可能崩溃。二叉树的节点释放不是一个简单的循环能搞定的因为每个节点还连接着它的左右孩子。正确的方式是采用后序遍历的顺序先释放左子树再释放右子树最后释放当前节点。因为如果你先释放了当前节点它的左右指针就成了悬垂指针后面的释放操作就会访问非法内存。这个顺序在代码里表现为template typename T void BSTreeT::clearNode(BSTreeNodeT* node) { if (node nullptr) { return; } clearNode(node-left); // 先释放左子树 clearNode(node-right); // 再释放右子树 delete node; // 最后释放当前节点 }有些教材会把析构函数写成调用clear()再让它递归释放。我实际写的时候发现析构函数里调用 clear 没问题但要注意清空之后一定要把 root_ 置为 nullptr否则以后如果不小心再次调用 clear就会对已经释放的内存执行 delete触发未定义行为通常表现为程序崩溃。3. 核心操作的逐层拆解3.1 插入操作两种写法的对比插入操作有两种主流的实现方式递归版和非递归版。我先给出递归版template typename T bool BSTreeT::insert(const T key) { // 调用私有辅助函数从根节点开始插入返回新的子树根 root_ insertNode(root_, key); return true; } template typename T BSTreeNodeT* BSTreeT::insertNode(BSTreeNodeT* node, const T key) { if (node nullptr) { return new BSTreeNodeT(key); } if (key node-key) { node-left insertNode(node-left, key); } else if (key node-key) { node-right insertNode(node-right, key); } // 如果 key 已经存在这里默认不插入重复值 return node; }递归版最容易理解的地方在于它利用了“函数调用栈”天然保存了路径上的节点。当我们找到一个合适的位置node 为 nullptr时直接 new 一个节点返回给上一层调用者上一层调用者把它挂在自己的 left 或 right 上。这个过程在概念上非常干净。但递归也有代价函数调用是有开销的在树非常高极端情况下退化成链表时递归深度可能达到 n有栈溢出的风险。所以很多跑工程的代码更喜欢非递归版本template typename T bool BSTreeT::insert(const T key) { if (root_ nullptr) { root_ new BSTreeNodeT(key); return true; } BSTreeNodeT* cur root_; BSTreeNodeT* parent nullptr; while (cur ! nullptr) { parent cur; if (key cur-key) { cur cur-left; } else if (key cur-key) { cur cur-right; } else { return false; // 树中已存在相同 key插入失败 } } if (key parent-key) { parent-left new BSTreeNodeT(key); } else { parent-right new BSTreeNodeT(key); } return true; }非递归版的核心思路是使用两个指针cur 负责向下走parent 用来记录 cur 的父节点。当 cur 走到 nullptr 时我们知道找到了“可以插入的位置”但是这个“位置”是通过 parent 的哪个方向挂上去的还需要再比较一次。这里有个小细节为什么不能用 cur 判断挂左边还是右边因为 cur 已经是 nullptr除了 nullptr 本身不携带任何父节点信息只有靠 parent 才能确定插入方向。这两种写法没有绝对的优劣。递归版代码简洁、不易出错适合教学和快速开发非递归版省去了函数调用的开销适合对性能有要求或树深度较大的场景。我个人建议初学者两个版本都写一遍因为他们在训练你两种不同的思维方式——递归思想在后续的 AVL 树和红黑树中还会大量用到。3.2 查找操作迭代实现更高效查找的目标是判断一个值是否存在于树中。由于 BST 的性质左子树所有节点都小于根右子树所有节点都大于根查找过程类似于二分查找当前节点的值等于目标值找到了目标值小于当前节点值往左走目标值大于当前节点值往右走。实现上有递归版和迭代版。迭代版不需要栈空间也更直观template typename T bool BSTreeT::contains(const T key) const { BSTreeNodeT* cur root_; while (cur ! nullptr) { if (key cur-key) { return true; } else if (key cur-key) { cur cur-left; } else { cur cur-right; } } return false; }这段代码的循环不变量是每一次迭代开始时key 只可能位于以 cur 为根的子树中。当 cur 变成 nullptr说明该子树为空目标值不存在。很多初学者在写这个循环时容易犯一个错误在循环体里修改了 cur 指针之后没有立刻重新判断而是继续使用旧值那是逻辑写岔了。一个最简单的验证方法就是用一组数据手动模拟几次循环比如在{5, 3, 8, 1, 4, 7, 9}这棵树里查 7你跟着代码走一遍自然就理解正确性了。3.3 删除操作三种情形的分治处理二叉搜索树的删除是最考验基本功的地方因为它不像插入那样“总能在叶子的位置上接入新节点”删除的节点可能在树中的任意位置。根据待删除节点拥有的子节点数量要分三种情况讨论。情况一待删除节点是叶子节点没有孩子这个最简单。直接把它从父节点上摘下来然后 delete 掉即可。但这里有一个隐蔽的问题如果待删除的节点恰好是根节点且树里只有它一个节点那么它没有父节点。此时只要把 root_ 置为 nullptr然后 delete 掉它就行。情况二待删除节点只有一个孩子比如一个节点只有一个左孩子或只有一个右孩子。此时直接让它的父节点指向它的孩子就像链表删除节点一样“绕过”它然后 delete 掉它。这里也需要注意边界情况如果待删除节点是根节点就没有父节点需要直接更新 root_ 指向它的孩子。情况三待删除节点有两个孩子这是最复杂的一种情况标准做法有两种一种是用左子树中的最大节点前驱节点来替换待删除节点另一种是用右子树中的最小节点后继节点来替换。两种都可以我下面用“右子树最小节点”来演示。为什么可以这样替换因为右子树中最小的节点一定满足它大于当前待删除节点左子树的所有节点且小于或等于右子树中的其他所有节点。把它放到待删除节点的位置依然能保证整棵 BST 的有序性。而且右子树的最小节点一定是“最多只有一个右孩子”的节点因为如果有左孩子左孩子肯定更小所以删除它的时候又回到了情况一或情况二问题就简化了。删除操作的完整代码如下template typename T bool BSTreeT::erase(const T key) { root_ eraseNode(root_, key); return true; // 简化处理实际应检查是否删除成功 } template typename T BSTreeNodeT* BSTreeT::eraseNode(BSTreeNodeT* node, const T key) { if (node nullptr) { return nullptr; // 没有找到 key } if (key node-key) { node-left eraseNode(node-left, key); return node; } if (key node-key) { node-right eraseNode(node-right, key); return node; } // 找到了目标节点开始处理三种情况 if (node-left nullptr node-right nullptr) { delete node; return nullptr; } if (node-left nullptr) { BSTreeNodeT* rightChild node-right; delete node; return rightChild; } if (node-right nullptr) { BSTreeNodeT* leftChild node-left; delete node; return leftChild; } // 两个孩子的场景找右子树最小节点 BSTreeNodeT* minNode findMin(node-right); node-key minNode-key; node-right eraseNode(node-right, minNode-key); return node; }这段代码的返回值设计得很巧妙每个递归返回的要么是原来传入的 node要么是新替换上来的节点。父节点收到返回值后只需要把它挂到对应的左右指针上结构就自动更新了。这种“返回新子树根”的递归模式在二叉树算法里很常见建议多看几遍。一个容易让人困惑的地方是如果我们用“右子树最小节点”的值去覆盖当前节点值那当前节点就成了“多余”的节点需要去右子树里真正地删掉那个最小节点。而那个最小节点位于右子树中并且它最多只有一个右孩子所以递归进去之后会落入情况一或情况二行为是正确且确定的。3.4 寻找最小节点的工具函数上面删除逻辑中用到findMin它的实现非常简短就是沿着左指针一直走到空template typename T BSTreeNodeT* BSTreeT::findMin(BSTreeNodeT* node) const { if (node nullptr) { return nullptr; } while (node-left ! nullptr) { node node-left; } return node; }同理可以写出findMax只要一路往右走即可。这两个函数我在实现“前驱后继查找”、“范围查询”等扩展功能时也频繁用到算是 BST 操作里的“基础设施”。4. 遍历与验证4.1 中序遍历为什么能输出有序序列二叉搜索树有一个非常漂亮的特性对它做中序遍历左子树、根节点、右子树结果就是从小到大排列的有序序列。这个性质很容易理解左子树所有节点都小于根右子树所有节点都大于根中序遍历先访问左边再访问根最后访问右边自然就排好了序。中序遍历的递归实现template typename T void BSTreeT::inorder() const { inorderHelper(root_); std::cout std::endl; } template typename T void BSTreeT::inorderHelper(BSTreeNodeT* node) const { if (node nullptr) { return; } inorderHelper(node-left); std::cout node-key ; inorderHelper(node-right); }这个性质在调试和测试中非常有用不管你怎么插入数据只要中序遍历输出是有序递增的就说明这棵树的 BST 性质没有被破坏。我写插入和删除功能时经常在每次操作后调用中序遍历这是最快的自我验证方法。甚至有一种说法如果面试官让你“验证一棵树是不是 BST”最粗暴但有效的方法就是中序遍历之后检查是否递增。4.2 前序、后序遍历的扩展除了中序遍历前序遍历和后序遍历也经常用到。前序遍历的顺序是“根、左、右”常用于树的序列化和重建比如用 C 把一棵树写到文件里再读出来重建后序遍历的顺序是“左、右、根”常用于释放内存——因为要先释放孩子节点再释放当前节点这正好符合后序遍历的顺序。前序实现template typename T void BSTreeT::preorderHelper(BSTreeNodeT* node) const { if (node nullptr) return; std::cout node-key ; preorderHelper(node-left); preorderHelper(node-right); }后序实现template typename T void BSTreeT::postorderHelper(BSTreeNodeT* node) const { if (node nullptr) return; postorderHelper(node-left); postorderHelper(node-right); std::cout node-key ; }如果你是在 vscode 里跑这些代码建议在 launch.json 里配置好调试环境然后打断点观察递归调用栈的变化。真的学习二叉树最好的工具就是调试器比看十遍书本都有效。5. 完整实现与测试用例5.1 把所有代码拼到一起下面是一个完整可运行的 BST 实现包含模板、插入、查找、删除、遍历、析构#include iostream template typename T struct BSTreeNode { T key; BSTreeNodeT* left; BSTreeNodeT* right; explicit BSTreeNode(const T val) : key(val), left(nullptr), right(nullptr) {} }; template typename T class BSTree { public: BSTree() : root_(nullptr) {} ~BSTree() { clear(); } bool insert(const T key) { if (root_ nullptr) { root_ new BSTreeNodeT(key); return true; } BSTreeNodeT* cur root_; BSTreeNodeT* parent nullptr; while (cur ! nullptr) { 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 BSTreeNodeT(key); } else { parent-right new BSTreeNodeT(key); } return true; } bool erase(const T key) { root_ eraseNode(root_, key); return true; } bool contains(const T key) const { BSTreeNodeT* cur root_; while (cur ! nullptr) { if (key cur-key) return true; else if (key cur-key) cur cur-left; else cur cur-right; } return false; } void inorder() const { inorderHelper(root_); std::cout std::endl; } void clear() { clearNode(root_); root_ nullptr; } private: BSTreeNodeT* root_; BSTreeNodeT* eraseNode(BSTreeNodeT* node, const T key) { if (node nullptr) return nullptr; if (key node-key) { node-left eraseNode(node-left, key); return node; } if (key node-key) { node-right eraseNode(node-right, key); return node; } // 找到节点 if (node-left nullptr node-right nullptr) { delete node; return nullptr; } if (node-left nullptr) { BSTreeNodeT* rightChild node-right; delete node; return rightChild; } if (node-right nullptr) { BSTreeNodeT* leftChild node-left; delete node; return leftChild; } BSTreeNodeT* minNode findMin(node-right); node-key minNode-key; node-right eraseNode(node-right, minNode-key); return node; } BSTreeNodeT* findMin(BSTreeNodeT* node) const { if (node nullptr) return nullptr; while (node-left ! nullptr) node node-left; return node; } void inorderHelper(BSTreeNodeT* node) const { if (node nullptr) return; inorderHelper(node-left); std::cout node-key ; inorderHelper(node-right); } void clearNode(BSTreeNodeT* node) { if (node nullptr) return; clearNode(node-left); clearNode(node-right); delete node; } };5.2 测试用例怎么写写完代码必须测试而且是系统性地测试不能只测 happy path。我一般会先测试插入的多种情况int main() { BSTreeint tree; // 插入测试 tree.insert(5); tree.insert(3); tree.insert(8); tree.insert(1); tree.insert(4); tree.insert(7); tree.insert(9); std::cout 中序遍历(应为1 3 4 5 7 8 9): ; tree.inorder(); // 查找测试 std::cout 查找7: tree.contains(7) std::endl; std::cout 查找6: tree.contains(6) std::endl; // 删除叶子节点 tree.erase(1); std::cout 删除1后中序遍历: ; tree.inorder(); // 删除只有一个孩子的节点 tree.erase(3); std::cout 删除3后中序遍历: ; tree.inorder(); // 删除有两个孩子的节点 tree.erase(8); std::cout 删除8后中序遍历: ; tree.inorder(); // 删除不存在的节点 tree.erase(100); std::cout 删除100后中序遍历: ; tree.inorder(); return 0; }你可以把输出结果手算一遍再跑程序。我最初跑删除测试时经常出现“把根节点删掉后整棵树找不到了”的错误原因就是删除根节点时没有正确更新根指针。上面的实现中erase的第调用root_ eraseNode(root_, key)就是为了保证即使删的是根节点也能拿到新的根节点。这个细节非常重要。5.3 复杂度的直观认识一棵平衡的 BST高度约为 O(log n)所以查找、插入、删除都是 O(log n)。注意我说的是“平衡”二字。如果插入的数据是顺序的比如你依次插入 1、2、3、4、5那这棵树会退化成一条链表高度变成 O(n)所有操作退化成 O(n)。这就是为什么后面有 AVL 树和红黑树这些自平衡数据结构。用一张表总结复杂度操作平均时间复杂度最坏时间复杂度退化时查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)中序遍历O(n)O(n)空间复杂度O(n)O(n)6. 常见问题与避坑指南6.1 删除叶子节点时的悬垂指针初学者最容易犯的错误就是删除叶子节点时在父节点中还保留着指向该节点的指针。比如写了这样的代码// 错误示例 if (parent-left cur) { delete cur; // 忘记把 parent-left 置为 nullptr }之后只要再访问 parent-left就会通过悬垂指针读取已经释放的内存轻则读到脏数据重则程序崩溃。这也是很多小伙伴在 VS 里跑着跑着突然报“访问冲突”的常见原因。解决思路删除叶子节点时必须把父节点相应的指针置空或者像我前面递归版实现一样通过返回值让父节点重新挂载 nullptr。6.2 递归深度过深导致栈溢出当 BST 退化成链表比如一直插入递增序列递归的深度会达到 n。如果 n 是 100 万级别连调用栈都可能撑不住。这不仅仅是理论问题我在用随机数据构造大树时真遇到过一次 stack overflow。有两个缓解办法第一改用非递归版本并显式使用栈std::stack来模拟递归第二使用随机化插入顺序比如先打乱数据让 BST 的形态尽量均衡。当然根本上还是要引入平衡树机制这就是后话了。6.3 delete 和析构的重复调用如果你的clear()函数在每轮测试中可能会被调用多次那么必须保证第二次调用不会出问题。我在 3.3 节的实现里特别强调了clear 结束后根节点要置为 nullptr否则第二次 clear 会对已经释放的内存再次调用 delete属于未定义行为。这类 bug 的特征是有时候能运行有时候崩溃几乎没有规律可循特别让人头疼。6.4 模板声明与实现的分离问题如果你把模板类的声明和实现拆分到.h和.cpp两个文件里会遇到链接错误。这是 C 模板的机制决定的模板的实例化发生在编译期编译器必须在实例化点能看到模板的完整定义。所以要么把模板的声明和实现都写在同一个.h文件里要么在.cpp文件底部显式实例化需要的类型比如template class BSTreeint;。这个问题几乎每个写模板类的人都会遇到特此提醒。6.5 使用调试器单步跟踪学习二叉树我强烈建议你在 vscode 里配置好 C/C 调试环境然后在递归调用处打断点。你观察左边“调用堆栈”窗口里一层一层的函数调用看变量node的值如何在递归过程中变化这种“眼见为实”的体验比任何书本讲解都深刻。我记得自己第一次实际看到递归栈一帧一帧地压入、弹出时那种感觉就像打开了新世界的大门。7. 工程实践中的进一步思考7.1 为什么标准库不用普通 BST有读者可能会好奇既然 BST 这么好用为什么 C 标准库的std::map用的是红黑树而不是普通 BST因为最坏情况太糟糕了。普通 BST 在面对有序输入时退化成链表时间复杂度瞬间降维到 O(n)。红黑树通过节点着色和一系列旋转操作保证了任何情况下树的高度不会超过 2 倍的最优高度也就是把操作稳定在 O(log n)。当然普通 BST 仍然是理解一切平衡树的基础。红黑树的旋转和变色只是为了让 BST 保持平衡核心的查找、插入、删除逻辑和普通 BST 完全一致。你现在把这篇文章的代码吃透之后去看红黑树也就是多学几个旋转函数的事。7.2 BST 在算法题中的典型应用在各种 C 面试和算法竞赛中BST 经常出现在这些场景中验证一棵树是否为二叉搜索树利用中序遍历有序性求 BST 中第 K 小的元素中序遍历 计数BST 的两节点最近公共祖先利用 BST 大小关系判断把 BST 转换为累加树反向中序遍历累加判断两个 BST 是否相同或互为镜像。掌握本期实现的插入、删除、查找三大基础操作之后做这些题基本就有了稳定的根基。我自己的体会是很多“看起来很难”的树题最后拆来拆去核心还是这些基本操作加上遍历的顺序变化。7.3 下一步可以扩展的方向如果你把本文的代码全部跑通并且能不看代码自己敲出来一遍接下来可以挑战这几个方向加入findMin和findMax的公开接口实现顺序遍历、反向遍历重构插入为递归版并支持“如何统计重复节点”支持从数组或 vector批量构建 BST对比一个个插入的效率实现 AVL 树在插入、删除之后进行旋转以保持平衡用 BST 实现一个字符串统计器统计文本里每个单词出现的次数。最后一个方向其实特别适合练手因为std::mapstd::string, int的内部原理就是这样。你用自己写的模板 BST 去统计一篇英文文章的词频既能检验模板对不同数据类型的支持又能直观体会到 BST 在真实文本处理中的意义。8. 写在最后的小建议把二叉搜索树从头到尾实现一遍是我在 C 学习过程中觉得性价比最高的一次练习。它逼着我去思考递归的返回逻辑、指针的生命周期、边界情况的处理这些能力在后面的复杂数据结构和工程代码中全都用得上。如果你现在正卡在“看得懂书但写不出来”的状态我的建议只有一句话关掉别人的代码打开编辑器从定义节点结构开始一步一步自己写。写错了不怕用调试器看用测试用例验证最后再对照本文查漏补缺。这个过程走完你就真正拥有了一棵属于自己的二叉搜索树。 C++手写二叉搜索树：插入、查找、删除与遍历实现解析
1. 项目概述1.1 核心需求与适用场景二叉搜索树Binary Search Tree简称 BST是 C 学习路线上绕不开的一个基础数据结构。我在接触它之前链表和数组已经用得比较顺手了但一到需要“快速查找某个元素”的场景总感觉不够痛快——数组的二分查找虽然高效却要求数据必须是有序的链表倒是方便插入删除了可查找只能从头遍历时间复杂度直接拉满到 O(n)。二叉搜索树正好把这两个需求平衡在一个结构里查找、插入、删除的平均时间复杂度都可以做到 O(log n)。这节课按照章节编号应该是一个系列课程中的第二章节第三小节是我自己在学习过程中重新手动实现一遍 BST 的记录。它的适用人群很明确正在上数据结构课的学生、准备 C 面试的求职者、以及那些看过很多遍理论却一直没有独立写完一棵树的“理论派”程序员。看完这篇博文你能独立写出一个支持插入、查找、删除、遍历的完整 BST 类并且能够回答“为什么删除节点要分三种情况”这类面试常问问题。1.2 为什么用 C 实现二叉搜索树不少初学者会问用 C 语言也能实现 BST为什么非要选 C我的感受是C 在这里提供了一个非常好的“中间地带”。你既可以用 struct 定义节点、用指针维护树形关系这部分和 C 语言很像能帮助理解底层内存布局又可以借用类封装、构造函数、析构函数这些 C 特性让代码更安全、更易调试——尤其是析构函数负责递归释放内存这件事手动管理过 C 语言版本的人一定深有体会稍不注意就内存泄漏。另外C 标准库里的std::map和std::set底层就是红黑树一种自平衡的 BST 变体面试里经常被问到它们的实现原理。如果你连最基础的 BST 都没手写过直接看红黑树的旋转逻辑基本等于看天书。所以我一直建议先把普通 BST 写透再去碰平衡树这条路是最顺的。2. 实现前的设计与思考2.1 节点结构的定义方式BST 的节点结构其实非常简洁就是三个成员一个存储数据的键值一个指向左子树的指针一个指向右子树的指针。写成代码是这样template typename T struct BSTreeNode { T key; // 存储的数据 BSTreeNodeT* left; // 左子树指针 BSTreeNodeT* right; // 右子树指针 explicit BSTreeNode(const T val) : key(val), left(nullptr), right(nullptr) {} };我在这里使用了模板template这样数据可以是 int、float甚至自定义类型。如果你刚开始学先不要急着上模板把 key 直接定义成 int 写通逻辑再改成模板会容易得多。构造函数的参数列表里使用const T而不是T是为了避免不必要的拷贝开销这是一种工程上常见的写法。关于“为什么节点要单独用 struct 而不是 class”我的习惯是当这个类型只是承载数据、没有复杂的逻辑操作时用 struct 就够了所有成员默认公开访问起来方便而树本身涉及较多的封装逻辑更适合用 class。这种“struct 负责数据、class 负责逻辑”的划分方式在 C 项目里比较常见也符合直觉。2.2 树的类骨架与接口设计树类需要对外提供哪些能力通常包括插入、查找、删除、遍历、清空析构函数。我把接口设计成这样template typename T class BSTree { public: BSTree() : root_(nullptr) {} ~BSTree() { clear(); } bool insert(const T key); // 插入节点返回是否成功 bool erase(const T key); // 删除节点返回是否成功 bool contains(const T key) const; // 查找节点是否存在 void inorder() const; // 中序遍历用于验证有序性 void clear(); // 清空整棵树 private: BSTreeNodeT* root_; // 各种递归辅助函数的声明这里先留空 };一个很重要的设计决定就是对外公开的接口尽量精美、简洁而真正干活儿的递归逻辑都放到 private 辅助函数里。比如insert对外只是一个返回 bool 的函数内部会调用一个递归函数来完成真正的插入工作。这样做的好处有两个一是用户不需要关心递归的入口参数尤其是根节点二是树的内部结构完全对外隐藏后续如果要改成 AVL 树或者红黑树接口可以保持不变只需要改私有实现。2.3 C 特有的内存管理问题C 实现的 BST 和 Java、Python 一个很大的区别就是内存管理。Java 有垃圾回收Python 有引用计数而 C 要求你手动释放。每次 new 出来的节点最后都必须有一个与之匹配的 delete。否则就会出现内存泄漏——程序运行时间越长占用内存越大最终可能崩溃。二叉树的节点释放不是一个简单的循环能搞定的因为每个节点还连接着它的左右孩子。正确的方式是采用后序遍历的顺序先释放左子树再释放右子树最后释放当前节点。因为如果你先释放了当前节点它的左右指针就成了悬垂指针后面的释放操作就会访问非法内存。这个顺序在代码里表现为template typename T void BSTreeT::clearNode(BSTreeNodeT* node) { if (node nullptr) { return; } clearNode(node-left); // 先释放左子树 clearNode(node-right); // 再释放右子树 delete node; // 最后释放当前节点 }有些教材会把析构函数写成调用clear()再让它递归释放。我实际写的时候发现析构函数里调用 clear 没问题但要注意清空之后一定要把 root_ 置为 nullptr否则以后如果不小心再次调用 clear就会对已经释放的内存执行 delete触发未定义行为通常表现为程序崩溃。3. 核心操作的逐层拆解3.1 插入操作两种写法的对比插入操作有两种主流的实现方式递归版和非递归版。我先给出递归版template typename T bool BSTreeT::insert(const T key) { // 调用私有辅助函数从根节点开始插入返回新的子树根 root_ insertNode(root_, key); return true; } template typename T BSTreeNodeT* BSTreeT::insertNode(BSTreeNodeT* node, const T key) { if (node nullptr) { return new BSTreeNodeT(key); } if (key node-key) { node-left insertNode(node-left, key); } else if (key node-key) { node-right insertNode(node-right, key); } // 如果 key 已经存在这里默认不插入重复值 return node; }递归版最容易理解的地方在于它利用了“函数调用栈”天然保存了路径上的节点。当我们找到一个合适的位置node 为 nullptr时直接 new 一个节点返回给上一层调用者上一层调用者把它挂在自己的 left 或 right 上。这个过程在概念上非常干净。但递归也有代价函数调用是有开销的在树非常高极端情况下退化成链表时递归深度可能达到 n有栈溢出的风险。所以很多跑工程的代码更喜欢非递归版本template typename T bool BSTreeT::insert(const T key) { if (root_ nullptr) { root_ new BSTreeNodeT(key); return true; } BSTreeNodeT* cur root_; BSTreeNodeT* parent nullptr; while (cur ! nullptr) { parent cur; if (key cur-key) { cur cur-left; } else if (key cur-key) { cur cur-right; } else { return false; // 树中已存在相同 key插入失败 } } if (key parent-key) { parent-left new BSTreeNodeT(key); } else { parent-right new BSTreeNodeT(key); } return true; }非递归版的核心思路是使用两个指针cur 负责向下走parent 用来记录 cur 的父节点。当 cur 走到 nullptr 时我们知道找到了“可以插入的位置”但是这个“位置”是通过 parent 的哪个方向挂上去的还需要再比较一次。这里有个小细节为什么不能用 cur 判断挂左边还是右边因为 cur 已经是 nullptr除了 nullptr 本身不携带任何父节点信息只有靠 parent 才能确定插入方向。这两种写法没有绝对的优劣。递归版代码简洁、不易出错适合教学和快速开发非递归版省去了函数调用的开销适合对性能有要求或树深度较大的场景。我个人建议初学者两个版本都写一遍因为他们在训练你两种不同的思维方式——递归思想在后续的 AVL 树和红黑树中还会大量用到。3.2 查找操作迭代实现更高效查找的目标是判断一个值是否存在于树中。由于 BST 的性质左子树所有节点都小于根右子树所有节点都大于根查找过程类似于二分查找当前节点的值等于目标值找到了目标值小于当前节点值往左走目标值大于当前节点值往右走。实现上有递归版和迭代版。迭代版不需要栈空间也更直观template typename T bool BSTreeT::contains(const T key) const { BSTreeNodeT* cur root_; while (cur ! nullptr) { if (key cur-key) { return true; } else if (key cur-key) { cur cur-left; } else { cur cur-right; } } return false; }这段代码的循环不变量是每一次迭代开始时key 只可能位于以 cur 为根的子树中。当 cur 变成 nullptr说明该子树为空目标值不存在。很多初学者在写这个循环时容易犯一个错误在循环体里修改了 cur 指针之后没有立刻重新判断而是继续使用旧值那是逻辑写岔了。一个最简单的验证方法就是用一组数据手动模拟几次循环比如在{5, 3, 8, 1, 4, 7, 9}这棵树里查 7你跟着代码走一遍自然就理解正确性了。3.3 删除操作三种情形的分治处理二叉搜索树的删除是最考验基本功的地方因为它不像插入那样“总能在叶子的位置上接入新节点”删除的节点可能在树中的任意位置。根据待删除节点拥有的子节点数量要分三种情况讨论。情况一待删除节点是叶子节点没有孩子这个最简单。直接把它从父节点上摘下来然后 delete 掉即可。但这里有一个隐蔽的问题如果待删除的节点恰好是根节点且树里只有它一个节点那么它没有父节点。此时只要把 root_ 置为 nullptr然后 delete 掉它就行。情况二待删除节点只有一个孩子比如一个节点只有一个左孩子或只有一个右孩子。此时直接让它的父节点指向它的孩子就像链表删除节点一样“绕过”它然后 delete 掉它。这里也需要注意边界情况如果待删除节点是根节点就没有父节点需要直接更新 root_ 指向它的孩子。情况三待删除节点有两个孩子这是最复杂的一种情况标准做法有两种一种是用左子树中的最大节点前驱节点来替换待删除节点另一种是用右子树中的最小节点后继节点来替换。两种都可以我下面用“右子树最小节点”来演示。为什么可以这样替换因为右子树中最小的节点一定满足它大于当前待删除节点左子树的所有节点且小于或等于右子树中的其他所有节点。把它放到待删除节点的位置依然能保证整棵 BST 的有序性。而且右子树的最小节点一定是“最多只有一个右孩子”的节点因为如果有左孩子左孩子肯定更小所以删除它的时候又回到了情况一或情况二问题就简化了。删除操作的完整代码如下template typename T bool BSTreeT::erase(const T key) { root_ eraseNode(root_, key); return true; // 简化处理实际应检查是否删除成功 } template typename T BSTreeNodeT* BSTreeT::eraseNode(BSTreeNodeT* node, const T key) { if (node nullptr) { return nullptr; // 没有找到 key } if (key node-key) { node-left eraseNode(node-left, key); return node; } if (key node-key) { node-right eraseNode(node-right, key); return node; } // 找到了目标节点开始处理三种情况 if (node-left nullptr node-right nullptr) { delete node; return nullptr; } if (node-left nullptr) { BSTreeNodeT* rightChild node-right; delete node; return rightChild; } if (node-right nullptr) { BSTreeNodeT* leftChild node-left; delete node; return leftChild; } // 两个孩子的场景找右子树最小节点 BSTreeNodeT* minNode findMin(node-right); node-key minNode-key; node-right eraseNode(node-right, minNode-key); return node; }这段代码的返回值设计得很巧妙每个递归返回的要么是原来传入的 node要么是新替换上来的节点。父节点收到返回值后只需要把它挂到对应的左右指针上结构就自动更新了。这种“返回新子树根”的递归模式在二叉树算法里很常见建议多看几遍。一个容易让人困惑的地方是如果我们用“右子树最小节点”的值去覆盖当前节点值那当前节点就成了“多余”的节点需要去右子树里真正地删掉那个最小节点。而那个最小节点位于右子树中并且它最多只有一个右孩子所以递归进去之后会落入情况一或情况二行为是正确且确定的。3.4 寻找最小节点的工具函数上面删除逻辑中用到findMin它的实现非常简短就是沿着左指针一直走到空template typename T BSTreeNodeT* BSTreeT::findMin(BSTreeNodeT* node) const { if (node nullptr) { return nullptr; } while (node-left ! nullptr) { node node-left; } return node; }同理可以写出findMax只要一路往右走即可。这两个函数我在实现“前驱后继查找”、“范围查询”等扩展功能时也频繁用到算是 BST 操作里的“基础设施”。4. 遍历与验证4.1 中序遍历为什么能输出有序序列二叉搜索树有一个非常漂亮的特性对它做中序遍历左子树、根节点、右子树结果就是从小到大排列的有序序列。这个性质很容易理解左子树所有节点都小于根右子树所有节点都大于根中序遍历先访问左边再访问根最后访问右边自然就排好了序。中序遍历的递归实现template typename T void BSTreeT::inorder() const { inorderHelper(root_); std::cout std::endl; } template typename T void BSTreeT::inorderHelper(BSTreeNodeT* node) const { if (node nullptr) { return; } inorderHelper(node-left); std::cout node-key ; inorderHelper(node-right); }这个性质在调试和测试中非常有用不管你怎么插入数据只要中序遍历输出是有序递增的就说明这棵树的 BST 性质没有被破坏。我写插入和删除功能时经常在每次操作后调用中序遍历这是最快的自我验证方法。甚至有一种说法如果面试官让你“验证一棵树是不是 BST”最粗暴但有效的方法就是中序遍历之后检查是否递增。4.2 前序、后序遍历的扩展除了中序遍历前序遍历和后序遍历也经常用到。前序遍历的顺序是“根、左、右”常用于树的序列化和重建比如用 C 把一棵树写到文件里再读出来重建后序遍历的顺序是“左、右、根”常用于释放内存——因为要先释放孩子节点再释放当前节点这正好符合后序遍历的顺序。前序实现template typename T void BSTreeT::preorderHelper(BSTreeNodeT* node) const { if (node nullptr) return; std::cout node-key ; preorderHelper(node-left); preorderHelper(node-right); }后序实现template typename T void BSTreeT::postorderHelper(BSTreeNodeT* node) const { if (node nullptr) return; postorderHelper(node-left); postorderHelper(node-right); std::cout node-key ; }如果你是在 vscode 里跑这些代码建议在 launch.json 里配置好调试环境然后打断点观察递归调用栈的变化。真的学习二叉树最好的工具就是调试器比看十遍书本都有效。5. 完整实现与测试用例5.1 把所有代码拼到一起下面是一个完整可运行的 BST 实现包含模板、插入、查找、删除、遍历、析构#include iostream template typename T struct BSTreeNode { T key; BSTreeNodeT* left; BSTreeNodeT* right; explicit BSTreeNode(const T val) : key(val), left(nullptr), right(nullptr) {} }; template typename T class BSTree { public: BSTree() : root_(nullptr) {} ~BSTree() { clear(); } bool insert(const T key) { if (root_ nullptr) { root_ new BSTreeNodeT(key); return true; } BSTreeNodeT* cur root_; BSTreeNodeT* parent nullptr; while (cur ! nullptr) { 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 BSTreeNodeT(key); } else { parent-right new BSTreeNodeT(key); } return true; } bool erase(const T key) { root_ eraseNode(root_, key); return true; } bool contains(const T key) const { BSTreeNodeT* cur root_; while (cur ! nullptr) { if (key cur-key) return true; else if (key cur-key) cur cur-left; else cur cur-right; } return false; } void inorder() const { inorderHelper(root_); std::cout std::endl; } void clear() { clearNode(root_); root_ nullptr; } private: BSTreeNodeT* root_; BSTreeNodeT* eraseNode(BSTreeNodeT* node, const T key) { if (node nullptr) return nullptr; if (key node-key) { node-left eraseNode(node-left, key); return node; } if (key node-key) { node-right eraseNode(node-right, key); return node; } // 找到节点 if (node-left nullptr node-right nullptr) { delete node; return nullptr; } if (node-left nullptr) { BSTreeNodeT* rightChild node-right; delete node; return rightChild; } if (node-right nullptr) { BSTreeNodeT* leftChild node-left; delete node; return leftChild; } BSTreeNodeT* minNode findMin(node-right); node-key minNode-key; node-right eraseNode(node-right, minNode-key); return node; } BSTreeNodeT* findMin(BSTreeNodeT* node) const { if (node nullptr) return nullptr; while (node-left ! nullptr) node node-left; return node; } void inorderHelper(BSTreeNodeT* node) const { if (node nullptr) return; inorderHelper(node-left); std::cout node-key ; inorderHelper(node-right); } void clearNode(BSTreeNodeT* node) { if (node nullptr) return; clearNode(node-left); clearNode(node-right); delete node; } };5.2 测试用例怎么写写完代码必须测试而且是系统性地测试不能只测 happy path。我一般会先测试插入的多种情况int main() { BSTreeint tree; // 插入测试 tree.insert(5); tree.insert(3); tree.insert(8); tree.insert(1); tree.insert(4); tree.insert(7); tree.insert(9); std::cout 中序遍历(应为1 3 4 5 7 8 9): ; tree.inorder(); // 查找测试 std::cout 查找7: tree.contains(7) std::endl; std::cout 查找6: tree.contains(6) std::endl; // 删除叶子节点 tree.erase(1); std::cout 删除1后中序遍历: ; tree.inorder(); // 删除只有一个孩子的节点 tree.erase(3); std::cout 删除3后中序遍历: ; tree.inorder(); // 删除有两个孩子的节点 tree.erase(8); std::cout 删除8后中序遍历: ; tree.inorder(); // 删除不存在的节点 tree.erase(100); std::cout 删除100后中序遍历: ; tree.inorder(); return 0; }你可以把输出结果手算一遍再跑程序。我最初跑删除测试时经常出现“把根节点删掉后整棵树找不到了”的错误原因就是删除根节点时没有正确更新根指针。上面的实现中erase的第调用root_ eraseNode(root_, key)就是为了保证即使删的是根节点也能拿到新的根节点。这个细节非常重要。5.3 复杂度的直观认识一棵平衡的 BST高度约为 O(log n)所以查找、插入、删除都是 O(log n)。注意我说的是“平衡”二字。如果插入的数据是顺序的比如你依次插入 1、2、3、4、5那这棵树会退化成一条链表高度变成 O(n)所有操作退化成 O(n)。这就是为什么后面有 AVL 树和红黑树这些自平衡数据结构。用一张表总结复杂度操作平均时间复杂度最坏时间复杂度退化时查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)中序遍历O(n)O(n)空间复杂度O(n)O(n)6. 常见问题与避坑指南6.1 删除叶子节点时的悬垂指针初学者最容易犯的错误就是删除叶子节点时在父节点中还保留着指向该节点的指针。比如写了这样的代码// 错误示例 if (parent-left cur) { delete cur; // 忘记把 parent-left 置为 nullptr }之后只要再访问 parent-left就会通过悬垂指针读取已经释放的内存轻则读到脏数据重则程序崩溃。这也是很多小伙伴在 VS 里跑着跑着突然报“访问冲突”的常见原因。解决思路删除叶子节点时必须把父节点相应的指针置空或者像我前面递归版实现一样通过返回值让父节点重新挂载 nullptr。6.2 递归深度过深导致栈溢出当 BST 退化成链表比如一直插入递增序列递归的深度会达到 n。如果 n 是 100 万级别连调用栈都可能撑不住。这不仅仅是理论问题我在用随机数据构造大树时真遇到过一次 stack overflow。有两个缓解办法第一改用非递归版本并显式使用栈std::stack来模拟递归第二使用随机化插入顺序比如先打乱数据让 BST 的形态尽量均衡。当然根本上还是要引入平衡树机制这就是后话了。6.3 delete 和析构的重复调用如果你的clear()函数在每轮测试中可能会被调用多次那么必须保证第二次调用不会出问题。我在 3.3 节的实现里特别强调了clear 结束后根节点要置为 nullptr否则第二次 clear 会对已经释放的内存再次调用 delete属于未定义行为。这类 bug 的特征是有时候能运行有时候崩溃几乎没有规律可循特别让人头疼。6.4 模板声明与实现的分离问题如果你把模板类的声明和实现拆分到.h和.cpp两个文件里会遇到链接错误。这是 C 模板的机制决定的模板的实例化发生在编译期编译器必须在实例化点能看到模板的完整定义。所以要么把模板的声明和实现都写在同一个.h文件里要么在.cpp文件底部显式实例化需要的类型比如template class BSTreeint;。这个问题几乎每个写模板类的人都会遇到特此提醒。6.5 使用调试器单步跟踪学习二叉树我强烈建议你在 vscode 里配置好 C/C 调试环境然后在递归调用处打断点。你观察左边“调用堆栈”窗口里一层一层的函数调用看变量node的值如何在递归过程中变化这种“眼见为实”的体验比任何书本讲解都深刻。我记得自己第一次实际看到递归栈一帧一帧地压入、弹出时那种感觉就像打开了新世界的大门。7. 工程实践中的进一步思考7.1 为什么标准库不用普通 BST有读者可能会好奇既然 BST 这么好用为什么 C 标准库的std::map用的是红黑树而不是普通 BST因为最坏情况太糟糕了。普通 BST 在面对有序输入时退化成链表时间复杂度瞬间降维到 O(n)。红黑树通过节点着色和一系列旋转操作保证了任何情况下树的高度不会超过 2 倍的最优高度也就是把操作稳定在 O(log n)。当然普通 BST 仍然是理解一切平衡树的基础。红黑树的旋转和变色只是为了让 BST 保持平衡核心的查找、插入、删除逻辑和普通 BST 完全一致。你现在把这篇文章的代码吃透之后去看红黑树也就是多学几个旋转函数的事。7.2 BST 在算法题中的典型应用在各种 C 面试和算法竞赛中BST 经常出现在这些场景中验证一棵树是否为二叉搜索树利用中序遍历有序性求 BST 中第 K 小的元素中序遍历 计数BST 的两节点最近公共祖先利用 BST 大小关系判断把 BST 转换为累加树反向中序遍历累加判断两个 BST 是否相同或互为镜像。掌握本期实现的插入、删除、查找三大基础操作之后做这些题基本就有了稳定的根基。我自己的体会是很多“看起来很难”的树题最后拆来拆去核心还是这些基本操作加上遍历的顺序变化。7.3 下一步可以扩展的方向如果你把本文的代码全部跑通并且能不看代码自己敲出来一遍接下来可以挑战这几个方向加入findMin和findMax的公开接口实现顺序遍历、反向遍历重构插入为递归版并支持“如何统计重复节点”支持从数组或 vector批量构建 BST对比一个个插入的效率实现 AVL 树在插入、删除之后进行旋转以保持平衡用 BST 实现一个字符串统计器统计文本里每个单词出现的次数。最后一个方向其实特别适合练手因为std::mapstd::string, int的内部原理就是这样。你用自己写的模板 BST 去统计一篇英文文章的词频既能检验模板对不同数据类型的支持又能直观体会到 BST 在真实文本处理中的意义。8. 写在最后的小建议把二叉搜索树从头到尾实现一遍是我在 C 学习过程中觉得性价比最高的一次练习。它逼着我去思考递归的返回逻辑、指针的生命周期、边界情况的处理这些能力在后面的复杂数据结构和工程代码中全都用得上。如果你现在正卡在“看得懂书但写不出来”的状态我的建议只有一句话关掉别人的代码打开编辑器从定义节点结构开始一步一步自己写。写错了不怕用调试器看用测试用例验证最后再对照本文查漏补缺。这个过程走完你就真正拥有了一棵属于自己的二叉搜索树。