简介一份数据结构课程综合性实验资料面向正在学习二叉排序树、需要完成综合实验报告的高校学生。内容围绕BST的构建、插入、查找、删除与中序遍历等核心算法提供可直接运行的C源码和配套实验文档源码通过节点定义与递归函数实现查找平均复杂度为O(logn)删除操作覆盖无子节点、单子节点和双子节点三种情形并说明如何维持树的性质文档还讨论了当树倾斜退化时需借助AVL、红黑树等自平衡方案为深入实验做了铺垫。压缩包共2个文件含1份doc格式实验报告和1个cpp源码文件整体仅305KB下载便捷目前已有1736人学习适合期末实验参考、算法复习或课前预习。读者对照源码与文档既能掌握二叉排序树的完整实现流程也能将其迁移到平衡树相关实验中提升综合设计与调试能力。 二叉排序树Binary Search Tree简称BST是数据结构里绕不开的一道坎。不管是期末考试、考研笔试还是面试编程题它都是高频考点很多进阶树结构——AVL树、红黑树、B树——本质上都是在BST这张底图上加了不同的约束策略。这篇文章我打算把BST里最常见的操作算法完完整整过一遍插入、查找、删除、遍历、统计高度、合法性判定、有序输出逐个上代码再谈谈容易踩的坑。看完之后不管你是在准备笔试还是纯粹想把树这块基础补牢应该都能直接上手跑通。我写这篇文章的底气来自这些年反复教别人、反复在面试题里见到它的经历。BST的代码量不算大但每一行都很讲究递归和指针的用法尤其是删除节点那段写错一个分支就是内存泄漏或者树结构被改坏。所以这篇文章不仅要给你能跑的代码还要把代码背后的取舍讲明白——知道为什么这么写比背下来重要得多。1. 二叉排序树的整体设计思路拆解1.1 二叉排序树到底是什么BST的定义三句话就能说完左子树上所有节点的值都小于根节点右子树上所有节点的值都大于根节点左右子树本身又各是一棵BST。这三点看起来简单但它把“在一堆数据中查找”这件事变成了每次比较后去掉一半子树的游戏。如果一棵树是平衡的查找一个元素就如同在一个有序数组里做二分查找时间和数据规模是对数关系。你可以把它理解成查字典你不会从第一页逐页翻而是根据拼音或者偏旁直接跳到中部再根据目标词的相对位置判断往左翻还是往右翻。这个顺序性还带来一个隐藏福利对BST做中序遍历得到的序列一定是有序递增的。这一条在面试里经常作为突破口出现后面我会专门讲到。1.2 为什么不用数组或链表实现这是初学者最常问的问题。直接给结论数组查找快但插入删除慢链表插入删除快但查找慢BST在理想情况下能同时拿到两者优势。数据结构查找插入删除有序数组O(log n) 二分O(n) 移动元素O(n) 移动元素普通链表O(n) 逐个遍历O(1) 头插或尾插O(1) 知道位置时BST平衡时O(log n)O(log n)O(log n)当然这个对比有个大前提BST要保持“平衡”。如果插入顺序很极端比如按升序依次插入BST会退化成一条链表所有操作的复杂度也跟着退化为O(n)。这是BST最大的软肋也是AVL树、红黑树这些平衡树出现的原因。这篇先聚焦基础算法平衡问题放到最后再聊。2. 起步算法结构定义、插入与查找2.1 节点结构一棵树的最小单元BST的节点在C语言里通常是这么定义的typedef struct BSTNode { int key; // 节点值 struct BSTNode *left; // 左孩子 struct BSTNode *right; // 右孩子 } BSTNode;真正工程里节点的值可能是一个结构体甚至一个对象比较逻辑也不止“大于小于”这么简单。但不管值多复杂核心结构就是这个三件套一个数据域两个指针域。只要你理解“节点指针指向孩子”这件事后面所有递归操作都好理解。我习惯把key声明为int考试和面试场景里最容易验证插入几个整数然后中序遍历看是否有序一眼就能判断算法对不对。2.2 插入算法把新节点挂到正确的位置插入逻辑一句话就能说清从根出发如果待插入值比当前节点小就向左走大就向右走直到走到空指针位置在这里创建新节点。递归版本的代码极为简洁BSTNode* insertBST(BSTNode *root, int key) { if (root NULL) { BSTNode *node (BSTNode*)malloc(sizeof(BSTNode)); node-key key; node-left node-right NULL; return node; } if (key root-key) { root-left insertBST(root-left, key); } else if (key root-key) { root-right insertBST(root-right, key); } return root; }这里有个特别值得玩味的设计函数返回值是BSTNode*每次递归都返回“挂好孩子之后的新子树根”。这样做的原因是——当递归到底发现空位置时新建的节点必须有个方式交还给父节点。如果单纯传一个二级指针也能写但返回值写法在语义上更清晰每个递归层都拿到一个更新后的子树再统一挂回去。你可能会问如果插入的值已经存在怎么办上面的代码选择忽略不插入重复值。这是BST最常见的约定因为重复值既不参与比较也没有太大意义。但有些场景确实允许重复那时通常的策略是“小于往左走大于等于往右走”或者反之。写之前先定好规则面试时主动提一句印象分会好很多。2.3 查找算法递归版和迭代版都练熟查找和插入走的路一模一样只是找到就停找不到就到空为止。// 递归版 BSTNode* searchBST(BSTNode *root, int key) { if (root NULL || root-key key) { return root; } if (key root-key) { return searchBST(root-left, key); } return searchBST(root-right, key); } // 迭代版 BSTNode* searchBSTIter(BSTNode *root, int key) { BSTNode *cur root; while (cur ! NULL cur-key ! key) { if (key cur-key) { cur cur-left; } else { cur cur-right; } } return cur; }查找算法可以说是整个BST的“试金石”。它每走一步比较一次大小往下走一层就排除掉一整棵子树。这个思路和二分查找如出一辙所以有些人会把它和“二分算法”联系起来——确实BST本质上就是一棵以二分策略组织的树。实际写代码时我建议递归版和迭代版都写一遍。递归版考查对分治思想的理解迭代版则锻炼对指针操作的掌控。面试时如果让我当场写查找我一般选迭代版因为它逻辑直白还能避免系统栈溢出的风险。3. 删除算法三种场景逐个拆解删除是BST所有操作里最考验基本功的一个也是面试里最容易写错的题。核心难点不在“删除”本身而在删完后如何继续保持BST的有序性。3.1 叶子节点与单子树节点的删除删除一个节点按孩子数量分成三种情况。第一种情况删除叶子节点。它没有孩子直接释放内存让父节点对应指针置空即可。第二种情况待删除节点只有左子树或只有右子树。做法也很朴素用它的唯一子树顶替它原来的位置。BSTNode* findMin(BSTNode *root) { if (root NULL) return NULL; while (root-left ! NULL) { root root-left; } return root; } BSTNode* deleteBST(BSTNode *root, int key) { if (root NULL) { return NULL; } if (key root-key) { root-left deleteBST(root-left, key); } else if (key root-key) { root-right deleteBST(root-right, key); } else { // 待删除节点左孩子为空 if (root-left NULL) { BSTNode *temp root-right; free(root); return temp; } // 待删除节点右孩子为空 if (root-right NULL) { BSTNode *temp root-left; free(root); return temp; } // 第三种情况左右孩子都不为空见下一节 BSTNode *temp findMin(root-right); root-key temp-key; root-right deleteBST(root-right, temp-key); } return root; }注意deleteBST和insertBST一样都返回“删除后子树的根”。当左孩子为空时哪怕右孩子也为空代码逻辑也一致——返回NULL给父节点完成叶子节点的删除。这两行判断其实把前两种情况合并处理了很巧妙。3.2 左右子树都存在用后继替换第三种情况最麻烦。待删除节点左右都有孩子直接删掉会失去两个子树没法简单顶替。业界通用的解法是“替换法”找一个既在树结构中承担位置、又能保持有序性的节点把它搬到待删节点来。找谁合适两个自然的候选左子树中的最大值中序前驱或者右子树中的最小值中序后继。以中序后继为例它一定大于待删节点左子树的所有值又小于或等于右子树的其余值把它搬到待删位置BST性质不会被破坏。// 接上一段 else 的完整情况 BSTNode *temp findMin(root-right); // 找到右子树最小节点 root-key temp-key; // 用它的值覆盖当前节点 root-right deleteBST(root-right, temp-key); // 删除右子树中那个最小节点为什么这里要坚持“删除右子树中的最小节点”而不是直接把temp释放因为temp还有可能是它所在位置的根而且它没有左孩子可能只有右孩子。所以第二次删除必然后落到前两种简单情况不会无限递归下去。整段逻辑层层递进复杂度保持在O(log n)。举一个具体的例子。假设BST中有节点序列50、30、70、20、40、60、80。现在删除根节点50。右子树是[70, 60, 80]最小值是60于是先用60覆盖50变成60、30、70、20、40、60、80root-key60再删除右子树中的那个60。由于60是原右子树的最小值它一定没有左孩子直接走“左孩子为空”分支把它的右孩子NULL或子树顶上即可。最终树里所有节点依然有序。3.3 删除的边界条件与内存管理写删除时最容易出问题的是“释放之后还在使用”或者“父节点还指着旧地址”。递归返回值的写法能天然规避这个问题所有对子树的修改都是通过“先删除再赋值回父指针”完成的。如果你的实现用小逻辑是// 错误示范只释放节点不更新父指针 free(root); return NULL; // 忘记把新子树返回给上层结果就是main函数里打印树时访问了野指针程序随机崩溃。所以每次写完删除算法我建议用一个固定序列手动推演一遍特别关注“被替换位置”的父节点到底指向了谁。4. 遍历、统计与合法性判定4.1 中序遍历BST的有序输出BST最迷人的地方不仅在于查找还在于遍历。三种遍历方式中中序遍历有个独一无二的特性输出序列严格递增。这一点在很多算法题里都是破题关键。void inorder(BSTNode *root) { if (root NULL) { return; } inorder(root-left); printf(%d , root-key); inorder(root-right); }这段代码只有三行但它把“递归”概念展示得淋漓尽致先处理完左边所有节点再访问自己最后处理右边。如果你往BST里依次插入5、2、7、1、3、6、8不管插入顺序怎么打乱中序遍历永远打印“1 2 3 5 6 7 8”。前序遍历和后序遍历也有用途。前序常用于序列化一棵树后序常用于先处理子节点再处理父节点的场景比如释放整棵树。三个遍历代码结构几乎一样区别只是访问时机的三行换顺序。4.2 求高度、节点数和最大值最小值求树高是理解“递归返回值”的最好练习。高度定义为根到最远叶子节点的边数有些教材按节点数算定义先说清。int treeHeight(BSTNode *root) { if (root NULL) { return 0; } int leftH treeHeight(root-left); int rightH treeHeight(root-right); return (leftH rightH ? leftH : rightH) 1; }叶子节点高度为1空树高度为0。递归时不断向下收集子树的“局部结果”回到当前层时取较大值加1。这个模式在树形DP里随处可见值得刻进脑子里。求最大值和最小值就简单了一路向左到尽头就是最小值一路向右到尽头就是最大值。这个操作在删除算法里已经被findMin用到过。int maxValue(BSTNode *root) { if (root NULL) return -1; // 根据题意决定空值 while (root-right ! NULL) { root root-right; } return root-key; }4.3 判断一棵树是不是BST这是高频面试题。很多人第一反应对每个节点比较左孩子小于自己、右孩子大于自己不就行了这个思路有个隐蔽漏洞。反例就是一棵根为10、左孩子为5、右孩子为15但右子树的左孩子为12的树——12确实大于15的左孩子吗不12小于根10但按单层判断它会被误判为合法。所以正确的做法是给每个节点传递一个区间所有节点值必须落在区间内。bool isBST(BSTNode *root, int minVal, int maxVal) { if (root NULL) { return true; } if (root-key minVal || root-key maxVal) { return false; } return isBST(root-left, minVal, root-key) isBST(root-right, root-key, maxVal); }调用时传isBST(root, INT_MIN, INT_MAX)。左子树所有节点必须小于根所以上限是根值右子树必须大于根所以下限是根值。每个节点的取值范围在递归过程中被逐步压缩这样右子树的左孩子如果小于根会在这里直接被卡掉。5. 复杂度、退化场景与常见问题排查5.1 为什么说“理想情况”是O(log n)BST所有操作的耗时都等于“从根到目标节点”路径的长度也就是树的高度。平衡时每层能容纳两倍于上一层的节点所以n个节点的高度大约是log2(n)。查找、插入、删除都要走一条路径复杂度就是O(log n)。但“高度为log n”不是BST的固有属性。如果你按升序依次插入1、2、3、4……节点会全部挂在右孩子上树的高度变成nBST直接退化成链表。此时查找一个元素要遍历全部节点复杂度掉了几个数量级。这就是为什么工程里用绝不仅仅是裸BSTAVL树靠旋转维持左右子树高度差不超过1红黑树用颜色约束路径长度比。理解了BST退化再去看平衡树就能明白它们究竟在“救”什么。5.2 常见错误速查表我总结了平时在教学和面试辅导中遇到最多的几个问题整理成一张速查表。错误现象根本原因解决办法插入后中序遍历少了值忘了用返回值更新root调用处写root insertBST(root, key)删除后程序崩溃访问了已释放的指针递归删除后必须返回并让父指针接收结果删除根节点后树错乱直接用free而不找替换节点左右双子树时用前驱或后继替换判断BST结果错误只比较当前节点与左右孩子改成传区间的递归判断出现重复值时插入失败没有规定等于时走哪分支明确约定重复值丢弃或统一走左/右这几类问题在我初学阶段几乎全踩过。前两个属于对“返回值传递”理解不够后三个属于对B树结构的有序性理解不深。5.3 调试技巧用中序遍历验证一切这里分享一个我最推荐的小技巧不管你写的是插入、删除还是旋转操作只要BST逻辑正确中序遍历结果一定严格递增。所以调试流程可以固定成三步第一步按一个固定序列插入所有元素。第二步打印中序遍历结果确认“1 2 3 5 7 8”这类递增序列。第三步执行要验证的操作比如删除某个值再打印一次中序遍历看结果是否还是递增且元素是否少了预期那一个。如果删除后序列出现乱序问题大概率出在“替换值”或“指针挂接”上不是遍历函数的问题。这个思路比在纸上画一堆箭头要省力得多也适合笔试前快速自查。5.4 迭代插入一个值得掌握的变体递归在树高几百层时就危险了系统栈可能溢出。所以很多工程场景需要迭代版本的插入。迭代插入的关键是保存一个parent指针用来记录当前节点的父节点。BSTNode* insertBSTIter(BSTNode *root, int key) { BSTNode *node (BSTNode*)malloc(sizeof(BSTNode)); node-key key; node-left node-right NULL; if (root NULL) { return node; } BSTNode *cur root, *parent NULL; while (cur ! NULL) { parent cur; if (key cur-key) { cur cur-left; } else if (key cur-key) { cur cur-right; } else { free(node); return root; // 重复值不插入 } } if (key parent-key) { parent-left node; } else { parent-right node; } return root; }这段代码的思路是用cur一路跌跌撞撞找到空位用parent记住最后一个非空节点。找到之后根据key和parent的比较结果把新节点挂到正确位置。它在真实工程里比递归版本更可控建议有时间也顺手练一遍。最后再分享一点我对BST的体会。别看它代码短却是理解“递归返回值”和“二叉树指针操作”最好的教材。我面试别人时出这道题重点看的不是候选人能不能默写出来而是遇到删除双子树节点时有没有真正理解为什么要用前驱或后继替换。把这段逻辑想透了后面学红黑树、B树的插入删除都会顺畅很多。如果你想往下深入建议沿着“BST → 平衡树 → 红黑树”这条路径走下去你会发现今天写的这几个基础算法全部都在用。本文还有配套的精品资源点击获取