简介：这是一份面向数据结构课程的综合实验资料，围绕二叉排序树的构建、插入、查找、删除及中序遍历等核心算法，提供完整可运行的C++实现与实验报告，适合高校学生完成综合性实验或复习BST知识时参考。压缩包共2个文件，包含1份doc格式的实验报告和1个cpp格式的源代码文件，整体约305KB，报告涵盖算法原理、关键函数说明与性能分析，代码可直接编译运行验证。资料已有1736人学习浏览，内容聚焦BST平衡问题与不同数据场景下的效率对比，能帮助读者深入理解二叉排序树机制并提升编码调试能力。无需额外环境配置，下载解压即可对照学习。
1. 二叉排序树的核心概念与设计思路
二叉排序树（Binary Search Tree，简称 BST），也叫二叉查找树，是数据结构课程里绕不开的一道坎。我在带新人或者辅导学生的时候经常说一句话：如果你能把二叉排序树彻底搞明白，树相关的算法题基本就通了三分之一。这句话不夸张，因为二叉排序树的插入、查找、删除、遍历这几种操作，几乎涵盖了二叉树所有的基础算法套路。
那二叉排序树到底是个什么东西？一句话概括：它是一种特殊的二叉树，每个节点的左子树所有节点值都小于当前节点，右子树所有节点值都大于当前节点。这个“左小右大”的规则，就是整棵树所有算法的灵魂。
1.1 BST到底解决了什么问题
在很多实际场景里，我们需要一种既能快速查找，又能灵活插入删除的数据结构。数组查找快但插入删除慢，链表插入删除快但查找慢。二叉排序树就是来平衡这两者的：它通过“二分”的思想，让查找、插入、删除的平均时间复杂度都能达到 O(logn)，同时实现起来又不像平衡树（比如红黑树、AVL树）那么复杂。
打个比方，BST就像一本按拼音排序的电话簿。你想找“张三”，不会从第一页翻到最后一页，而是根据首字母直接翻到 Z 开头的区域，再逐步缩小范围。BST 的查找过程本质上就是这个逻辑：从根节点出发，目标值比当前节点小就往左走，大就往右走，每次都排除掉一半的搜索空间。
1.2 为什么按照“左小右大”来组织数据
这个设计背后有一个很深刻的数学逻辑：有序性。BST 之所以查找快，是因为它每走一步就能排除掉“半个树”。而且这种有序性还带来一个额外的好处——中序遍历BST得到的序列一定是升序排列的。这个性质我们在后面的遍历章节会用到，很多算法题（比如把BST转成有序双向链表）就是靠这个性质来解的。
另外，BST 这种结构天然支持最值查询：最左边的节点一定是最小值，最右边的节点一定是最大值。这在某些需要频繁取极值的应用场景（比如动态维护一个有序集合）里非常好用。
1.3 节点结构怎么设计
在开始写算法之前，先把节点的数据结构定下来。一般来说，一个 BST 节点需要三个字段：数据域 value、左孩子指针 left、右孩子指针 right。如果你用的是 C/C++，最常见的是这样的结构体：
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };用 Java 的话就是 class TreeNode，成员变量加上构造方法。Python 则更简洁，直接用 class 定义，成员默认公开。无论哪种语言，核心都是这三个字段。也有一些高级用法会加一个 parent 指针指向父节点，方便某些操作，但基础算法不需要，我们这里先用最精简的结构。
这里有个小建议：做算法题或者写项目的时候，TreeNode 的定义最好统一，不要一个文件里出现几种不同版本的节点定义。很多人写着写着就搞混了，明明这个节点有 parent 指针，下一个文件里又没了，编译直接报错。
2. 查找与插入算法：BST 最基础的两板斧
查找和插入是 BST 最基础的两个操作，也是最容易写对又最容易写错的。我见过太多人在查找时忘记处理空指针，或者在插入时没有把新节点真正“挂”到树上。下面逐个拆解。
2.1 查找算法的递归与迭代两种写法
查找的核心逻辑：从根节点开始，如果目标值等于当前节点值，查找成功；如果目标值小于当前节点值，递归去左子树找；如果大于，递归去右子树找；如果走到空节点还没找到，说明不存在。
递归写法非常直观：
TreeNode* searchBST(TreeNode* root, int target) { if (root == NULL || root->val == target) { return root; } if (target < root->val) { return searchBST(root->left, target); } return searchBST(root->right, target); }这个写法有个好处是逻辑和 BST 的定义完全对应，几乎不可能写错。但是递归有一个问题：当树的高度很大（比如退化成链表时），递归深度可能很深，有栈溢出的风险。这时候迭代写法更稳妥：
TreeNode* searchBST(TreeNode* root, int target) { while (root != NULL && root->val != target) { if (target < root->val) { root = root->left; } else { root = root->right; } } return root; }迭代写法不需要额外的函数调用栈，空间复杂度是 O(1)，在实际工程里更推荐。我个人的习惯是：如果是笔试面试做题，用递归，代码短、易读、不容易错；如果是工程代码，用迭代。
2.2 插入算法的细节与重复值处理
插入的逻辑比查找稍微复杂一点，因为你要找到“该挂在哪个节点的下面”。思路还是利用 BST 的有序性，一路向下找，直到遇到空位，然后创建新节点挂上去。
TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) { return new TreeNode(val); } if (val < root->val) { root->left = insertIntoBST(root->left, val); } else if (val > root->val) { root->right = insertIntoBST(root->right, val); } // val == root->val 时，根据需求处理重复值 return root; }这段代码里有几个容易踩坑的地方。
第一，递归函数的返回值一定要接收。很多人写成insertIntoBST(root->left, val);，没有把返回值赋给root->left，结果新节点创建了但没挂上去，树一点变化都没有。这个错误非常隐蔽，因为编译器不会报错，运行也不崩溃，就是结果不对。
第二，重复值怎么处理？BST 的定义里没有统一标准，有的做法是直接忽略，有的做法是计数，还有的会让重复值统一往右子树走。具体取决于你的业务需求。如果是做算法题，题目一般会明确说明有没有重复值；如果没说，默认按不重复处理即可。
2.3 为什么插入和查找的平均复杂度是 O(logn)
简单推导一下：BST 的查找和插入每一层只需要做一次比较，所以时间开销取决于树的高度 h。在完全二叉树或接近完全二叉树的情况下，树的高度 h ≈ log₂n，所以每次操作需要比较 log₂n 次，复杂度 O(logn)。
但这里有个大坑：BST 的复杂度是有条件的。如果你按顺序插入 1、2、3、4、5，得到的树会是一条“斜线”，高度等于 n，此时查找复杂度退化成 O(n)，和链表没区别。这也是平衡二叉树存在的意义。在写 BST 算法时，心里要时刻记住这一点。
3. 删除算法：BST 中最容易翻车的操作
删除是 BST 所有操作中最复杂的，没有之一。我第一次手写删除的时候也是改了好几遍才跑通。它的难点在于：删除一个节点之后，整棵树还必须保持 BST 的性质。根据被删节点的孩子数量，分三种情况讨论。
3.1 情况一：删除叶子节点
这是最简单的情况。叶子节点没有孩子，直接把它从父节点上摘掉，释放内存（C/C++ 需要手动处理，Java/Python 等语言让 GC 代劳）。
怎么“摘掉”？有两种做法：一种是在父节点里把这个指针置空，另一种是递归写法里直接返回 NULL 给父节点接收。递归写法更通用：
if (root->left == NULL && root->right == NULL) { delete root; return NULL; }注意delete root之后必须返回 NULL，让上一层递归去更新父节点的指针。很多人漏了这一步，导致父节点还指向一块已经被释放的内存，形成“野指针”。
3.2 情况二：删除只有一个孩子的节点
这种节点“拖着一个孩子”，删除时让它的孩子顶替它的位置就行了。逻辑上就是把当前节点绕过，像链表删除一样。
if (root->left == NULL) { TreeNode* temp = root->right; delete root; return temp; } if (root->right == NULL) { TreeNode* temp = root->left; delete root; return temp; }这段代码的含义很直白：如果左孩子为空，那就让右孩子上位；如果右孩子为空，就让左孩子上位。因为左右子树的值本身就满足 BST 的约束（右子树所有值都大于当前节点，左子树所有值都小于当前节点），所以孩子顶替上来不会破坏有序性。
3.3 情况三：删除有两个孩子的节点（核心难点）
这是最麻烦的情况。被删节点有两个孩子，不能简单地让某个孩子顶替，因为你不知道该让左孩子还是右孩子上位，即使选了一个，它的另一侧子树也不好安置。
业界标准的解法是：找前驱或后继节点来替换。所谓前驱，就是左子树中值最大的那个节点；后继就是右子树中值最小的那个节点。这两个节点有一个共同特点：它们至多只有一个孩子（前驱不可能有右孩子，后继不可能有左孩子，因为如果有孩子，那孩子的值会更接近被删节点），所以删起来很简单。
我用后继替换来示范。思路是：先找到右子树中的最小节点，把它的值赋给当前节点，然后递归地删除右子树中的那个最小节点即可。这样一来，值被替换了，节点从“有两个孩子的难删节点”变成了“只有一个或没有孩子的易删节点”，问题迎刃而解。
TreeNode* deleteNode(TreeNode* root, int key) { if (root == NULL) return NULL; if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { // 找到要删除的节点 if (root->left == NULL && root->right == NULL) { delete root; return NULL; } if (root->left == NULL) { TreeNode* temp = root->right; delete root; return temp; } if (root->right == NULL) { TreeNode* temp = root->left; delete root; return temp; } // 有两个孩子的情况 TreeNode* successor = root->right; while (successor->left != NULL) { successor = successor->left; } root->val = successor->val; root->right = deleteNode(root->right, successor->val); } return root; }这段代码是完整的删除实现，包含了三种情况的处理。用前驱替换也是一样的思路，找左子树的最大节点，复制值，然后递归删左子树里的那个节点。两种方案都可以，看个人习惯。
我实际写代码的体会是，有两个孩子的删除分支特别容易出 bug，常见的有两个：一是找后继时循环条件写错，导致找到的不是最小值；二是在递归删除后继节点时，应该传入successor->val而不是key。一旦传错了，删完根本对不上号。
3.4 删除操作复杂度分析
删除操作本质上先要查找目标节点（O(h)），找到之后如果遇到双孩子情况，还需要在子树里查找前驱或后继（又是 O(h)）。但这两步是串行先后发生的，不是嵌套循环，所以总复杂度仍然是 O(h)。在平衡树里就是 O(logn)，退化链表里是 O(n)。
4. 遍历与构建：从树到序列再回到树
遍历是理解二叉树结构的最好方式。BST 的遍历和普通二叉树一样，有前序、中序、后序、层序四种方式，但 BST 的中序遍历有特殊意义，我们单独拿出来说。
4.1 三种深度优先遍历的递归与迭代实现
先看递归版。遍历的递归写法几乎是模板化的，改下访问顺序就是一个新遍历。
// 前序遍历：根 -> 左 -> 右 void preorder(TreeNode* root) { if (root == NULL) return; cout << root->val << " "; // 访问根 preorder(root->left); // 遍历左子树 preorder(root->right); // 遍历右子树 } // 中序遍历：左 -> 根 -> 右 void inorder(TreeNode* root) { if (root == NULL) return; inorder(root->left); cout << root->val << " "; // 访问根 inorder(root->right); } // 后序遍历：左 -> 右 -> 根 void postorder(TreeNode* root) { if (root == NULL) return; postorder(root->left); postorder(root->right); cout << root->val << " "; // 访问根 }递归遍历虽然好写，但在工程大树上会爆栈。我给出迭代版前序遍历，核心是要手动维护一个栈：
void preorderIter(TreeNode* root) { if (root == NULL) return; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); cout << cur->val << " "; // 先压右孩子，再压左孩子，出栈才能先左后右 if (cur->right) st.push(cur->right); if (cur->left) st.push(cur->left); } }中序遍历的迭代写法要更绕一些，核心思路是“沿左子树一路入栈，弹出访问，再转向右子树”：
void inorderIter(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; while (cur != NULL || !st.empty()) { while (cur != NULL) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); cout << cur->val << " "; cur = cur->right; } }这几个写法我建议至少手写一遍，尤其是中序迭代。面试里直接考你“不用递归实现中序遍历”的频率非常高。
4.2 层序遍历与按层打印
层序遍历就是按层从上到下、从左到右访问节点，依靠队列来实现，非常直观：
void levelOrder(TreeNode* root) { if (root == NULL) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* cur = q.front(); q.pop(); cout << cur->val << " "; if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } }按层打印（每层打印一行）也很常见。做法是在 while 循环里先记录当前队列的大小，然后只处理这个数量内的节点，这样每一批就是一个层：
void levelOrderLine(TreeNode* root) { if (root == NULL) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; i++) { TreeNode* cur = q.front(); q.pop(); cout << cur->val << " "; if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } cout << endl; } }这个levelSize的套路非常实用，很多与“层”相关的问题（比如计算二叉树最大宽度、找每层最大值）都要用到这个技巧。
4.3 从数组构建 BST：两种实际场景
写算法题时经常需要从数组构建一棵 BST。有两种常见场景。
场景一：数组本身就是 BST 的中序遍历序列。我们知道 BST 中序遍历是升序的，但仅凭中序序列无法唯一确定一棵树。如果数组是升序且题目要求构建一棵“高度平衡的 BST”，那就每次取中间元素作为根，左右部分递归构建。这是经典的“将有序数组转换为二叉搜索树”问题。
TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) { if (left > right) return NULL; int mid = left + (right - left) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = sortedArrayToBST(nums, left, mid - 1); root->right = sortedArrayToBST(nums, mid + 1, right); return root; }场景二：给定一个无顺序的数组，按顺序一个个插入构建 BST。这个场景更贴近 BST 的“动态构建”特性。从根节点开始，直接调用前面写的插入函数即可。此时建出来的树高度取决于数组的顺序，也因此可能出现各种形态。
4.4 为什么中序遍历BST一定有序
这是 BST 最漂亮的数学性质。中序遍历的顺序是“左子树 → 根 → 右子树”。根据 BST 的定义，左子树所有节点值都小于根节点，右子树所有节点值都大于根节点。所以中序遍历先访问了比根小的所有节点，再访问根，再访问比根大的所有节点。对每个子树递归地应用这个逻辑，整体上就是严格递增的。
这个性质有多好用？我们经常利用 BST 中序有序来做“验证是否为合法 BST”、“找第 K 小的元素”、“BST 转双向链表”等题目。本质上都是在利用“中序有序”这个天然约束。
5. 常见问题与排查技巧实录
最后一个部分，全部是经验。写 BST 相关代码时间久了，踩过的坑、看别人踩过的坑，攒下来就是这一节的内容。
5.1 树退化成链表：为什么明明写了BST却还是慢
这是非常经典的坑。BST 的效率建立在“树”这个形态上，如果退化成一条链，查找、插入全部退化成 O(n)。什么情况会退化？最常见的是“有序插入”。比如按 1、2、3、4、5 的顺序依次插入，每次新节点都是当前树里最大的，最后得到的树就是一条右斜链。
怎么避免？如果是数据量不大且不重复的动态集合，可以试试随机化插入顺序，能显著降低退化概率。如果对性能有硬性要求，就不要用裸 BST 了，直接上 AVL 树或红黑树。这也是工业届很少直接使用裸 BST 的原因。
如何快速判断当前树是否退化？一个简单的办法是递归计算树的高度，和理论上平衡状态的高度对比。如果树高接近 n 而不是 log₂n，那基本已经退化。
5.2 递归深度过大导致栈溢出
递归实现简洁，但深度过大时函数调用栈会爆掉。在刷题网站（如力扣）上，遇到超大数据量或树高很深的测试用例时，递归代码容易报栈溢出错误（Stack Overflow）。
排查思路：
- 先确认数据规模是不是很大（比如 10⁵ 级别的线性插入）。
- 再确认树高是不是接近 n。
- 如果是，就把递归版本改成迭代版本。
我平时写的时候有一个原则：如果题目没有特殊要求，能用迭代就用迭代，不能用迭代再考虑递归。查找和插入都有迭代版本，只有删除不太好写迭代，其他大部分操作迭代都能搞定。
5.3 内存泄漏与野指针：C/C++ 的痛
写 C/C++ 的 BST 代码，new出来的节点用完必须delete。删除节点时，最怕的是“只 delete 了节点，但父节点的指针还指向那块内存”。这时候再访问父节点的指针，就是一个标准的野指针。
如何避免？我给自己定了几条规矩：
- 删除操作里，
delete之后必须把局部指针置空。 - 递归返回时，父节点必须接收并更新孩子指针。
- 如果整个树不用了，写一个后序遍历式的销毁函数，先删子树，再删根节点。
void destroyTree(TreeNode* root) { if (root == NULL) return; destroyTree(root->left); destroyTree(root->right); delete root; }这段代码没什么技术含量，但能有效减少内存泄漏。笔试面试里可能不会查内存泄漏，但实际工程中这就是致命的 bug。
5.4 调试技巧：如何可视化一棵树
二叉树这东西在脑海里想是一回事，实际跑起来看又是一回事。调试 BST 代码时，我强烈推荐写一个“打印树”的辅助函数，把树的结构按层打印出来。写起来不难，几十行代码，但调 bug 的时候效率翻倍。
void printTree(TreeNode* root) { if (root == NULL) { cout << "Empty tree" << endl; return; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; i++) { TreeNode* cur = q.front(); q.pop(); if (cur) cout << cur->val << " "; else { cout << "# "; continue; } q.push(cur->left); q.push(cur->right); } cout << endl; } }比如你在删除算法里改了一行，不确定对不对，直接打印整棵树，一眼就能看出中序是否还有序、树是否完整、哪个节点掉了。这比在代码里到处加断点管用得多。
再补充一个技巧：写 BST 算法题时，优先跑一些“边界用例”。比如空树NULL、只有根节点、两个节点、删除不存在的值、删除根节点等。这些用例往往能暴露代码里最容易隐藏的 bug。我见过很多人在普通用例上跑得飞起，一提交就挂，就是因为边界没处理干净。
6. 写在最后的一点心得
BST 的算法实现看起来不难，但真正理解它需要写、需要调、需要踩坑。我这几年看了不少初学者代码，发现最容易出问题的不是算法本身，而是对指针或引用传递的理解不到位。以 C++ 为例，很多人写root->left = deleteNode(root->left, key)和deleteNode(root->left, key)之间的区别都还没想清楚，就开始写删除算法，不出错才怪。
我的建议是先用一组小数据（比如 {5, 3, 6, 2, 4, 7}）在纸上模拟一遍插入和删除的完整过程，把指针变化的每一步画出来，再去写代码。这个习惯能帮你省下大量调试时间。BST 是很多高级数据结构（AVL、红黑树、B 树）的基石，花时间把它吃透，后面学什么都会快很多。
本文还有配套的精品资源，点击获取
