1. 先搞清楚一件事为什么要给二叉树分这么多类很多人学二叉树的时候第一反应是不就是一个节点最多挂两个孩子吗怎么又冒出满二叉树、完全二叉树、平衡二叉树、二叉搜索树、红黑树这一串名词我刚入门那会儿也是这个感觉觉得是教材在硬凑概念。后来写代码写得多了被各种性能问题按在地上摩擦过几回才明白这些分类其实不是在玩文字游戏而是在用不同的约束条件换取不同的好处。你可以把二叉树想象成一栋没有电梯的老楼节点就是房间边就是楼梯。如果这栋楼每层都住满那是满二叉树如果只有最底下一层没住满而且人都挤在左边那叫完全二叉树。规不规整直接决定了你能不能拿一个数组把整栋楼装下、能不能用下标算出某个房间的邻居是谁。而二叉搜索树干的是另一件事它给房间编号规定左边的都比我小、右边的都比我大于是查东西就不用一层层扫了。问题在于光有“左小右大”这个规矩还不够。你要是手气差按顺序往一棵二叉搜索树里塞数据它会长成一条链子查找退化成从头翻到尾跟链表没区别。这时候就轮到平衡二叉树出面它通过旋转操作强行把树压扁让高度维持在 log 级别。红黑树则可以看成平衡二叉树的一个更务实的表亲它放弃了一点点平衡的严格性换来插入删除时更少的调整动作因此在工业界里反而更常见。我写这篇东西是想把这几类二叉树从“考试要背的定义”拉回到“实际要用的工具”这个层面上来。不管你是正在啃王道数据结构、准备考研复试的学生还是面试前临时抱佛脚想搞清楚红黑树的候选人或者只是想在项目里选一个合适的树结构来存点数据把这几类树的区别、联系和适用场景捋清楚都能省掉不少返工的麻烦。下面我按照从简单到复杂的顺序一类一类拆开讲顺便把那些真正容易踩的坑都摆出来。2. 满二叉树和完全二叉树最朴素也最实用的两种形态2.1 满二叉树的定义与节点数推算满二叉树指的是每一层的节点数都达到该层能容纳的最大值整棵树看上去像一把完整的扇形一个空缺都没有。用更正式的说法如果一棵树的深度为 k根节点记为第 1 层并且总节点数为 2^k − 1那它就是满二叉树。这个公式不是背出来的是推出来的。第 1 层最多 1 个节点也就是 2^0第 2 层最多 2 个即 2^1第 3 层最多 4 个即 2^2……第 k 层最多 2^(k−1) 个。把等比数列加起来2^0 2^1 … 2^(k−1) 2^k − 1。所以只要你说一棵树是满的节点总数就被深度唯一确定了反过来节点数 n 也能直接推出深度 k log2(n1)。满二叉树在理论上非常干净很多引理都靠它做归纳的基础。但它在现实中极少出现因为要求太苛刻了——你存 10 个数据它偏要你凑够 15 个才叫满。所以教材讲满二叉树主要是为了后面定义完全二叉树做铺垫。2.2 完全二叉树放宽一点点换来回很多完全二叉树是这么规定的除了最后一层其他每一层都是满的而且最后一层的节点必须集中在左边中间不能空着、右边更不能有节点而左边没有。换句话说把一棵完全二叉树从上到下、从左到右编号1 号到 n 号是一口气排下来、中间不断档的。理解了这句话你就会发现满二叉树一定是完全二叉树但完全二叉树不一定是满的。这是一个高频考点也特别容易在选择题里挖坑。举个常见的例子一棵有 6 个节点的完全二叉树按层序编号 1 到 6它的最后一层只有 3 个节点显然不满但它确实是完全二叉树因为最后一层的 4、5、6 号节点是靠左连续排列的。2.3 为什么完全二叉树能用数组存下来这是完全二叉树最重要的实用价值。由于节点编号连续不断档你根本不需要指针直接开一个数组下标就从 1 开始存关系下标公式下标从 1 开始下标公式下标从 0 开始左孩子2i2i 1右孩子2i 12i 2父节点i / 2向下取整(i − 1) / 2是否为叶子2i n2i 1 n拿生活里的礼品盒打个比方指针存储像每个盒子里塞一张纸条告诉你下一个盒子在哪数组存储则是把这些盒子编好号整整齐齐码在柜子里你站在柜子前直接数第几格就行。前者要额外维护纸条指针占内存后者只要会算下标就够了。所以堆大顶堆、小顶堆这种结构一定用完全二叉树因为它既要频繁访问父子节点又需要随机访问任意位置数组存储的常数开销小得不是一点半点。注意用下标从 1 开始的公式写代码时数组要开 n1 大小0 号位置空着不用。我见过太多人因为混用 0 基和 1 基公式导致左孩子算成了右孩子调了半天还在怀疑人生。2.4 怎么判断一棵树是不是完全二叉树判断思路一点都不复杂层序遍历BFS走一遍就行。规则是这样的一旦遇到第一个“孩子不全”的节点——也就是只有左孩子没有右孩子或者干脆两个孩子都没有——那么从它之后遍历到的所有节点都必须是叶子节点否则就不是完全二叉树。bool isComplete(TreeNode* root) { if (!root) return true; queueTreeNode* q; q.push(root); bool seenIncomplete false; // 是否遇到过缺孩子的节点 while (!q.empty()) { TreeNode* cur q.front(); q.pop(); if (cur-left) { if (seenIncomplete) return false; // 之前已缺还冒出孩子 q.push(cur-left); } else { seenIncomplete true; } if (cur-right) { if (seenIncomplete) return false; q.push(cur-right); } else { seenIncomplete true; } } return true; }这里的逻辑关键在于“seenIncomplete”这个标记一旦置为 true后面任何节点只要有孩子就判失败。因为完全二叉树的性质决定了空缺只能出现在最末尾。2.5 关于这两个概念的几个高频误区第一个误区是“完全二叉树就是满二叉树”。这个前面说过了一定不要搞混。第二个误区是“节点数 n 的完全二叉树高度是 log2(n)”。正确的公式是 floor(log2 n) 1比如 n 6log2 6 约为 2.58向下取整是 2加 1 等于 3实际上 6 个节点的完全二叉树高度确实是 3。第三个误区跟考试里常见的“n0 n2 1”有关。这个式子的意思是任意非空二叉树中叶子节点数等于度为 2 的节点数加 1。很多人只记结论不会推结果题目稍微变一下就不会用了。推导其实很简单设总节点数为 n度为 0、1、2 的节点数分别为 n0、n1、n2那么 n n0 n1 n2另一方面从边的角度看除了根节点每个节点都被一条边指着所以总边数 n − 1而边又等于所有节点孩子数之和即 n1 2n2。两个式子一联立就能得到 n0 n2 1。这个推导过程建议自己动手写一遍比死记有用得多。3. 二叉搜索树第一次把“有序”引入树里3.1 定义与中序遍历性质二叉搜索树BST的规矩很好记对于任意一个节点它左子树里所有节点的值都小于它右子树里所有节点的值都大于它。注意这里说的是“所有节点”不是只有直接孩子满足就行。这个定义带来一个非常漂亮的推论对一棵 BST 做中序遍历得到的序列是严格递增的。为什么因为中序的顺序是“左、根、右”而左子树全部小于根、根又小于右子树全部递归下去自然就排好序了。这个性质是 BST 的命根子很多应用场景都靠它比如你要查第 k 小的元素或者判断一棵树是不是 BST都可以用中序遍历来做。判断一棵树是不是 BST最容易犯的错误是只比较父子节点的值。反例很典型根是 10右孩子是 1515 的左孩子是 6。节点 6 比父节点 15 小、比根 10 小看起来好像没问题但它出现在根节点右子树里就违反了“右子树所有节点都大于根”的规矩。正确做法是给递归传上下界一路收窄bool isValidBST(TreeNode* root, long low, long high) { if (!root) return true; if (root-val low || root-val high) return false; return isValidBST(root-left, low, root-val) isValidBST(root-right, root-val, high); }用 long 做边界是为了躲开 int 最小值/最大值这种边界测试用例这个坑在面试里踩一次就记住了。3.2 查找与插入顺着一条路往下走查找的逻辑就是每次和当前节点比大小小了往左、大了往右走到空说明没找到。平均情况下每次能排除一半的候选复杂度是 O(log n)。插入也一样找到该插入的空位置挂上去就行不需要动其他节点。但这里有个隐藏的坑如果插入的数据本身是有序的比如 1、2、3、4、5 依次插入这棵树会一直往右长最后变成一条向右的链高度是 n查找退化成 O(n)。这就是所谓的最坏情况。很多人写测试用例时喜欢用有序数据结果发现自己的 BST 慢得离谱就是这个原因。3.3 删除操作才是最麻烦的一环查找和插入都简单删除才是 BST 里真正需要动脑子的地方。删除分三种情况要删的节点没有孩子直接把父节点的对应指针置空。要删的节点只有一个孩子让父节点直接指向那个孩子。要删的节点有两个孩子这时候不能直接删得找一个替代者。第三种情况的常规做法是找右子树里的最小值也就是右子树一路向左走到底的那个节点把它复制到要删的位置然后再把那个最小值节点本身删掉。因为右子树最小值一定大于左子树全部、小于右子树剩下的全部用它来顶替当前节点BST 的性质依然成立。为什么用右子树最小值而不是左子树最大值其实两个都行效果一样只是习惯上统一选一个方向写起来不容易乱。TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; 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) return root-right; if (!root-right) return root-left; TreeNode* succ root-right; while (succ-left) succ succ-left; // 找右子树最小 root-val succ-val; root-right deleteNode(root-right, succ-val); } return root; }这段递归写法很干净但要注意最后一行必须是对 root-right 做删除而不是对整个 root 再做一遍否则就死循环了。我第一版代码就写错过这里。3.4 BST 的价值与它无法回避的短板BST 的意义在于它把“有序”这件事从线性结构搬到了树结构上查一个数、找一个区间、求第 k 小、找前驱后继全都能在 O(log n) 的时间里完成。相比之下维护一个有序数组虽然查找能用二分但插入删除要挪元素代价是 O(n)。但 BST 的 O(log n) 只是平均不是保证。它的形态完全取决于插入顺序最坏情况下退化到 O(n)。在需要稳定性能的场合这种“看运气”的结构显然不能接受。于是人们就琢磨能不能在插入删除的时候顺手调整一下形状让它始终保持比较扁这就是接下来两节要讲的平衡二叉树和红黑树。4. 平衡二叉树AVL把高度死死锁住4.1 平衡因子与平衡条件AVL 树是最早被提出来的自平衡二叉搜索树它的核心思路是在 BST 的基础上再加一条约束任意节点的左右子树高度差不超过 1。这个高度差叫平衡因子Balance Factor定义为左子树高度减去右子树高度取值只能是 −1、0、1。为什么要限制在 1 以内因为一旦平衡因子恒在 −1 到 1 之间可以证明树高一定是 O(log n) 级别查找的复杂度就有了硬保障不再看插入顺序的脸色。代价是每次插入或删除之后都得检查有没有失衡一旦失衡就要通过旋转把树掰回来。4.2 四种失衡形态与对应的旋转操作失衡一共有四种情况名字按“新节点插入的位置”来取LL 型往左孩子的左子树插入导致失衡需要一次右旋。RR 型往右孩子的右子树插入导致失衡需要一次左旋。LR 型往左孩子的右子树插入导致失衡需要先对左孩子左旋、再对当前节点右旋。RL 型往右孩子的左子树插入导致失衡需要先对右孩子右旋、再对当前节点左旋。拿 LL 型举例右旋的操作是把当前节点记为 A它的左孩子记为 BB 的右子树记为 T2。旋转之后 B 成为新的子树根A 变成 B 的右孩子而 T2 挂到 A 的左孩子位置。为什么这样调整是对的因为 T2 里所有值都比 B 大、比 A 小正好适合放在 A 的左子树。TreeNode* rightRotate(TreeNode* A) { TreeNode* B A-left; TreeNode* T2 B-right; B-right A; A-left T2; // 更新高度 A-height max(h(A-left), h(A-right)) 1; B-height max(h(B-left), h(B-right)) 1; return B; // 新根 }左旋就是镜像操作把右孩子提上来当根。LR 和 RL 都是两步旋转先把它转成 LL 或 RR再处理一次。提醒一点旋转完之后一定要重新计算高度而且顺序必须是先算被降下去的那个节点A再算升上来的那个B。因为 B 的新高度依赖 A 的新高度顺序反了高度就会算错然后整棵树后面判断平衡因子全是错的调起来特别隐蔽。4.3 删除操作比插入更折磨人插入只需要在递归回溯的路上检查一次失衡、转一次就完事了。删除不一样删完之后可能要沿着回溯路径一路调整上去每一层都可能需要旋转最坏要到根节点才停。这就是为什么 AVL 的删除实现比插入长得多。我个人的经验是写 AVL 删除先把普通 BST 删除写好再在每一层返回之前加上“更新高度 判断平衡因子 旋转”这三步逻辑会清楚很多。不要在删除的每个分支里都塞旋转代码那样代码根本没法看。4.4 AVL 的适用场景与它的代价AVL 的平衡是严格平衡树高接近理论最小值所以查找效率是这类结构里最好的。但严格就意味着调整频繁插入删除时旋转的次数平均比红黑树多。如果你的场景是“查多改少”比如构建好之后基本只读AVL 就很合适如果是频繁插入删除比如实时任务的调度队列AVL 的旋转开销会变成负担。一个比较实际的判断标准读操作占比超过八成AVL 可以考虑否则优先考虑红黑树。数据库的内存索引、某些需要极致查询性能的场景会偏爱 AVL 这一派。5. 红黑树工程界更看重的那个折中方案5.1 五条性质记住它们才能理解后面的修复逻辑红黑树在 BST 的基础上给每个节点染了一个颜色红或黑然后加上五条约束每个节点不是红就是黑。根节点必须是黑色。每个叶子节点这里指的是空节点 NIL都算黑色。红色节点的两个子节点必须是黑色也就是说不能有两个红节点连着。从任意节点出发到它所有后代叶子节点的路径上黑色节点数量相同这个数量叫黑高。性质 4 和 5 是精髓。性质 5 保证了从根到任意叶子的路径长度不会差太多因为黑节点数量一样红的又不能连续出现最长路径最多是最短路径的两倍。由此可以推出红黑树的高度上限是 2·log2(n1)查找依然是 O(log n) 级别。注意是“上限”不是精确值说明它比 AVL 松但松得可控。5.2 红黑树和 AVL 到底差在哪对比维度AVL 树红黑树平衡程度严格左右高度差 ≤ 1放宽最长路径 ≤ 2 倍最短树高更矮查询更快略高查询稍慢插入调整旋转次数少但需要回溯更新旋转少多数是变色删除调整复杂且旋转多相对友好变色配合最多 3 次旋转适用场景查多改少增删查均衡一句话总结AVL 用更多的旋转换取更矮的树红黑树用略高的树换取更少的调整。在实际工程里插入删除往往是常态红黑树的整体吞吐更好所以它赢了。5.3 插入修复的三种情形新插入的节点一律先染成红色——因为染红只会违反性质 4不能连续红而染黑会破坏性质 5黑高一致修起来更麻烦。染红之后如果父节点是黑的那就什么事都没有如果父节点是红的那就要分情况处理而分情况的关键在于“叔叔节点”父节点的兄弟是什么颜色。情况一叔叔是红色。把父节点和叔叔都染黑祖父染红然后把当前节点跳到祖父继续向上检查。这相当于把问题往上推了一层。情况二叔叔是黑色且当前节点和父节点方向一致比如父是祖父的左孩子当前又是父的左孩子。以祖父为支点旋转一次然后把父和祖父的颜色对调。情况三叔叔是黑色且当前节点和父节点方向不一致父是祖父的左孩子当前是父的右孩子。先以父节点为支点转一次把情况三变成情况二再按情况二处理。坦白说红黑树的插入修复逻辑光看文字要反复好几遍才能理清楚。我的建议是拿纸笔画几个具体的小例子把每一步的节点颜色和指针变化都标出来比盯着定义强太多。5.4 为什么标准库和操作系统都爱用红黑树看看它在哪些地方出现过就知道它多受欢迎了Java 的 TreeMap 和 TreeSet 底层是红黑树C 标准库里的 map、set、multimap、multiset 大多数实现也是红黑树Linux 内核里大量需要有序管理的数据结构比如虚拟内存区域的管理、高精度定时器队列用的也是红黑树。选它的理由很实在一是性能有保证最坏也是 O(log n)不像裸 BST 会退化二是插入删除的整体开销比 AVL 小在写操作多的情况下更划算三是实现相对稳定几十年打磨下来各个语言的实现都很成熟你基本不用自己写。需要说明的是教材上讲红黑树经常会配一大堆旋转图但真正写代码时你会发现插入的旋转最多两次、删除的旋转最多三次剩下的都是变色代码量比想象中小。6. 动手实现一棵能跑的二叉搜索树6.1 结构定义与基础工具函数光看概念容易飘我建议至少手写一棵 BST 出来把插入、查找、删除、中序遍历全跑通。结构定义很朴素struct TreeNode { int val; int height; // AVL 才需要BST 可以先不写 TreeNode* left; TreeNode* right; TreeNode(int v) : val(v), height(1), left(nullptr), right(nullptr) {} };插入用递归最省事因为递归天然能沿着路径回溯不需要额外维护父指针TreeNode* insert(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val root-val) root-left insert(root-left, val); else if (val root-val) root-right insert(root-right, val); else return root; // 重复值直接忽略看业务需求 return root; }这里要留意“重复值怎么处理”这个问题。有人选择忽略有人选择插到右子树有人干脆在节点里加个计数器。这个决策要提前定好因为一旦写进代码后面所有查找和删除逻辑都得跟它保持一致。6.2 验证树的正确性三件套测试写完基本操作之后一定要做三个验证第一中序遍历输出必须是升序。这是检验 BST 性质有没有被破坏的最快方法。跑一遍打印出来如果有序说明结构基本没问题。第二手动 print 出树的高度。随机插 1000 个数据如果高度在 10 到 20 之间说明树长得比较平衡如果高度接近 1000说明退化成链了BST 的实现可能有问题或者数据恰好有序。第三模拟删除后的结构。捏几个小规模的手工用例比如插入 {5,3,8,2,4,7,9}分别删除叶子、单孩子节点、双孩子节点再把中序打出来看是否还有序。这三步做完你对 BST 的理解会比看十页书都深。6.3 从 BST 扩展到 AVL 需要补哪些东西如果你想把刚才的 BST 改成 AVL要补的只有三块一是节点里加高度字段二是每次操作返回前更新高度三是加一个检查平衡因子并旋转的函数。插入和删除的骨架完全不用动只是把“返回 root”这一句换成“先更新高度再检查平衡必要时旋转最后返回新的子树根”。这个改造过程我建议你一定要亲手做一遍。因为它会让你体会到自平衡不是另一套结构而是在普通树的基础上加了一层“事后检查 局部修正”的机制。理解了这层机制红黑树也就没那么神秘了——只是它检查的是颜色而不是高度。7. 写二叉树时最容易崩的几个地方7.1 空指针解引用稳居报错第一名“写二叉树程序时为什么总是报运行时错误”这个问题在搜索里出现频率极高我敢说九成的答案是空指针。递归函数里访问root-left-val这种链式解引用之前只要中间任何一环可能是空就会崩。最稳妥的习惯是递归函数第一行先写if (!root) return ...;不要等到用了才想起来判空。另一个高发点是删除操作里找后继的那段循环。如果代码写成while (succ)而不是while (succ-left)运气不好就会把空指针解引用。写完循环条件一定回头看一眼。7.2 递归基线写错直接栈溢出二叉树递归的基线条件有两个常见错法一是写成if (root-left nullptr root-right nullptr)这样遇到只有一个孩子的节点就不停地往下递归二是漏掉了对空节点的判断只判了叶子。正确做法永远是if (!root)打头然后再处理叶子或者一般情况。7.3 删除之后没有正确回接指针普通 BST 的删除用递归返回新子树根的写法是最稳的因为每一层都用返回值重新挂好了指针。如果图省事用迭代写法就很容易出现“删掉节点之后父节点的孩子指针还指向被删对象”的情况表现为程序不崩但结果莫名其妙。凡是涉及指针改动的操作我都建议用递归版本先跑通再考虑改迭代。7.4 常见问题速查表现象可能原因处理办法程序运行时报段错误访问了空指针递归首行判空链式解引用前逐层检查中序遍历结果不是升序BST 性质被破坏检查插入比较方向、删除后是否重新挂接树退化成一条链数据有序或 BST 未做平衡打乱插入顺序做测试或改用 AVL/红黑树高度算出来比预期大很多旋转后没有更新高度更新顺序先更新下层节点再更新上层插入重复值行为不一致没定义重复值策略明确忽略、右插或计数全流程统一删除节点后找不到其他节点指针断裂用递归返回新根的写法重建连接递归层次太深导致爆栈树过高或基线错误检查平衡性必要时改迭代或手动模拟栈7.5 几条我踩坑踩出来的经验写代码之前先把“重复值怎么处理”“空树怎么表示”这两个问题定下来别边写边改否则后面全是补丁。调试树结构时不要只printf值把树形结构画出来看网上有不少打印树的现成函数花十分钟找一个能省几个小时。测试数据一定要包含三种极端情况全升序、全降序、完全随机这三组过不去的话代码大概率有问题。另外别一上来就挑战红黑树。我见过不少人初学就想手撸红黑树结果卡在删除修复那里半个月最后连 BST 都没搞明白。正确顺序是先 BST再 AVL最后红黑树。AVL 是理解“旋转”最好的跳板把 AVL 的四种旋转写顺了红黑树的旋转就是换汤不换药。8. 考试、面试、工程里各自该抓什么重点8.1 考研和期末考点分布很集中如果是应付考试先看完全二叉树和满二叉树的定义和计算。n0 n2 1 这个公式完全二叉树的节点数和高度的关系按层序编号之后父子节点的下标关系这几个几乎是必考题。线索二叉树、树的存储方式这些属于配套考点一般和遍历结合着出。平衡二叉树的考点主要在“插入后如何调整”特别是给你一串数字让你画出最终的 AVL 和红黑树。这种题没有捷径只能动手画画五六道之后基本就有手感了。红黑树的考试难度一般不会太大主要考性质和插入后的颜色调整删除调整在本科阶段考得相对少。8.2 面试问的是理解和取舍面试很少让你默写红黑树的旋转代码但很爱问“为什么用红黑树不用 AVL”“BST 为什么要平衡”“完全二叉树为什么可以用数组存”。这些问题考的不是记忆而是你对“约束和代价”这层关系的理解。另一个高频问题是“BST 删除有两个孩子的节点怎么做”因为这里最能看出你是不是真写过代码。回答时把“找右子树最小节点替换”的思路说清楚再补一句“也可以找左子树最大节点效果等价”基本上就稳了。8.3 工程落地别自己造轮子实际项目里需要有序集合时优先用标准库C 用 map/setJava 用 TreeMap/TreeSetPython 用 sortedcontainers 这类库。这些实现都是红黑树或者其他成熟平衡树性能和稳定性都经过大量验证。自己手写树结构的场景其实很少通常是标准库满足不了某些特殊需求比如需要自定义节点的合并策略、需要持久化结构、或者面试要求现场实现。如果确实要自己写我的排序建议是能用哈希表就用哈希表不需要有序时它更快需要有序且增删频繁用红黑树需要有序但几乎只读考虑 AVL 或者有序数组加二分只是需要堆序直接上二叉堆完全二叉树加数组就够了。最后分享一个我个人一直在用的做法每学一种树就随手写一个小脚本随机生成一千条数据插进去把树高、查找耗时、插入耗时都打出来对比一下。数据不会骗人眼睁睁看着裸 BST 退化成链、AVL 和红黑树高度稳定在十几层那种对“约束换性能”的直观感受比背十遍定义都管用。等你哪天在项目里真的因为选对了树结构而少写了一大堆兜底逻辑回头看这些分类名词就不会觉得它们是教材的装饰品了。