1. 为什么二叉树是数据结构的分水岭如果你正在啃《数据结构》这门课学完链表、栈、队列之后大概率会觉得“也就那样”。直到你碰到二叉树事情开始变得不一样了。二叉树不是一种“复杂的数据结构”它是第一种让你从线性思维转向非线性思维的结构这个转折点非常关键。从应用层面看二叉树几乎是无处不在的。文件系统的目录结构、数据库的索引B树可以理解为二叉树的变种、编译器里表达式树、网络的路由表甚至你每天用的搜索引擎的排序逻辑背后都有树的影子。学会二叉树你才能真正看懂这些系统背后的组织方式。这个系列写到第8篇前面的线性结构都是“一根绳上的蚂蚱”最多就是单链表、双链表、循环链表来回折腾。二叉树引入了“左右孩子”的概念意味着一个节点可以有两个去向处理问题的复杂度从O(n)级别的线性思考变成了O(log n)级别的分支思考。这是思维方式的一次升级也是后续学习图、搜索算法、动态规划的基础。为什么说二叉树的深度、遍历、搜索是高频考点因为这几个点直接对应着递归思维、栈与队列的应用、指针操作的熟练度。面试题里考二叉树本质上是在考察你递归和迭代两种编程范式有没有真正掌握。所以这篇内容我不打算只念定义而是要带着你把二叉树从概念到代码、从遍历到删除节点完整拆一遍你可以直接把它当成一份实验报告加面试笔记用。2. 二叉树的定义与关键形态2.1 基本术语节点、深度、高度很多初学者会被深度和高度搞晕我先把这个基础说清楚。二叉树由节点组成最上面的节点叫根节点往下分出去的是左右孩子。没有孩子的节点叫叶子节点。深度是从根节点往下数根节点深度为1也有定义为0的但考试和实际代码里国内教材一般习惯从1开始。高度是从叶子节点往上数叶子节点高度为1。举个例子一个三层满二叉树根节点深度1中间层深度2最底层深度3反过来最底层高度1中间层高度2根节点高度3。理解这个之后后面求深度、写递归函数的时候才不会把终止条件和返回值搞错。另外还有几个概念要区分清楚度为0的节点、度为1的节点、度为2的节点。二叉树中每个节点最多有两个孩子所以节点度只能是0、1、2。有一个很经典的公式叶子节点数等于度为2的节点数加1。这个在很多题目里直接可以用比如“已知度为2的节点有10个问叶子节点有几个”答案就是11个不用去画图。2.2 几种常见的二叉树形态考试和面试里经常提到的形态有这么几种满二叉树每一层都是满的节点总数是2的n次方减1。这种树形态最规整很多性质可以直接推导。完全二叉树除了最后一层其他层都是满的最后一层的节点都集中在左侧。这是堆的数据结构的基础。搜索二叉树左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点。这个在查找、插入、删除时效率很高平均O(log n)。平衡二叉树左右子树高度差不超过1。它是对搜索二叉树的优化避免退化成链表。我见过很多学生背了定义却不会做题原因在于把概念和代码割裂了。其实这些形态跟后面的操作是一体的搜索二叉树决定了插入和查找的比较规则完全二叉树决定了顺序存储的下标计算方式平衡二叉树决定了旋转操作的触发条件。概念是为了代码逻辑服务的不是拿来背的。判断一棵树是不是完全二叉树有个实用方法不需要背公式用层序遍历一旦遇到空节点后面所有节点都必须为空否则就不是完全二叉树。这个方法在写代码时比数节点数快得多。3. 存储方式怎么选顺序存储与链式存储3.1 顺序存储数组里的二叉树顺序存储就是用数组来存二叉树节点。核心规律是对于下标为i从1开始计数的节点其左孩子下标为2i右孩子下标为2i1父节点下标为i/2取整。这种存储方式适合完全二叉树因为节点紧凑排列不需要浪费空间。但如果是普通二叉树问题就大了。比如一棵深度为10但每层只有1个节点的斜树如果要用顺序存储需要申请2的10次方减1个空间实际只用了10个空间浪费率将近99%。顺序存储的优点是访问速度快连续内存对缓存友好缺点是插入删除节点维护成本高。所以它一般用于堆排序和优先级队列的场景不太用于搜索二叉树的动态操作。3.2 链式存储指针连接的世界链式存储更符合二叉树的逻辑结构每个节点定义一个数据域和两个指针域typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;三个字符的数据域加上两个指针每个节点16字节左右空间利用效率比数组直观得多。插入删除节点只需要修改几个指针的指向不需要移动数组元素非常适合动态变化的数据结构。还有变体是三叉链表多加了一个parent指针方便从下往上访问节点在做某些算法题比如找最近公共祖先的时候很省事。代价是每个节点多了4字节平时用二叉链表就够。我在这里给出一个建议初学阶段不管是练习还是做实验报告优先用链式存储。因为指针操作能让你把树的结构看得更清楚而且后续的递归遍历、删除操作都是建立在指针操作基础上的。如果你一上来就用数组实现反而对“节点之间的逻辑关系”缺少直观感受。等你完全把树的思维建立起来再看顺序存储的优势就容易理解了。4. 二叉树的遍历递归与迭代两手都要硬4.1 四种遍历方式的结果规律遍历是最核心的内容不管是面试还是期末考试二叉树相关的题目80%都跟遍历有关。前序、中序、后序、层序每种方式的访问顺序不同但理解它们有一个共同的方法看访问根节点的时机。前序遍历先根再左后右中序遍历先左再根后右后序遍历先左再右后根层序遍历从上到下从左到右一层一层来前序、中序、后序这三个合在一起是一个很好的记忆组合。前中后指的是根节点的访问位置左永远在右前面。所以前序是根左右中序是左根右后序是左右根。有一个很常见的考法已知前序和中序求后序或者已知中序和后序求前序。做题方法是先从前序或后序中确定根再根据中序划分左右子树递归处理。比如前序是ABDCE中序是DBAEC那么根是A中序中A左边是DB右边是EC然后继续递归就可以还原整棵树。4.2 递归实现与调用栈可视化递归写法非常干净几行搞定// 前序遍历 void preOrder(BiTree T) { if (T NULL) return; printf(%c , T-data); preOrder(T-lchild); preOrder(T-rchild); }把printf换到中间就是中序换到最后就是后序。很多学生不理解为什么换一下位置就能改变访问顺序我画个递归调用栈的流程图你就能明白了。假设树是这样的A / \ B C / \ D E前序遍历的访问顺序是A-B-D-E-C。先访问根A然后递归进入B节点访问B再进入D访问DD为空返回再进入E访问EE返回B的左子树和右子树都访问完了B返回回到A的右子树访问C。关键点在于递归函数的调用栈是后进先出的。前序遍历时A先入栈被访问然后B入栈访问D入栈访问D返回后E入栈访问E返回后C入栈访问。这个调用过程理解了递归遍历就没有秘密了。4.3 迭代实现显式栈模拟递归递归虽然好写但在二叉树深度很大的时候递归会消耗大量栈空间极端情况下直接栈溢出。面试中也经常要求写出非递归版本考察你对栈的理解。非递归前序遍历的思路是用一个显式栈来模拟递归的调用过程void preOrderIterative(BiTree T) { if (T NULL) return; stackBiTree st; st.push(T); while (!st.empty()) { BiTree node st.top(); st.pop(); printf(%c , node-data); // 注意先压右孩子再压左孩子因为栈是后进先出 if (node-rchild ! NULL) st.push(node-rchild); if (node-lchild ! NULL) st.push(node-lchild); } }为什么先压右孩子再压左孩子因为栈是后进先出的先压右孩子左孩子就会先弹出被访问正好符合“先左后右”的访问顺序。中序遍历的非递归则要麻烦一点核心思路是一直往左走到尽头一路上把节点压栈直到左边为空弹出栈顶访问然后转向右子树继续void inOrderIterative(BiTree T) { stackBiTree st; BiTree node T; while (node ! NULL || !st.empty()) { while (node ! NULL) { st.push(node); node node-lchild; } node st.top(); st.pop(); printf(%c , node-data); node node-rchild; } }这个代码要反复推敲一下。每次循环先从当前节点开始把左链全部压栈然后弹出访问再处理右子树。右子树为空就继续弹栈实现回溯。后序遍历的非递归更麻烦一些需要一个额外标记来区分节点是否已经被访问过左右子树这里先不展开你可以作为练习自己推导一遍。4.4 层序遍历队列的天下层序遍历跟前面的思路不同它用队列实现天然符合“先来先服务”的公平原则void levelOrder(BiTree T) { if (T NULL) return; queueBiTree q; q.push(T); while (!q.empty()) { BiTree node q.front(); q.pop(); printf(%c , node-data); if (node-lchild ! NULL) q.push(node-lchild); if (node-rchild ! NULL) q.push(node-rchild); } }层序用队列、前中后用栈递归隐含栈这是二叉树遍历的唯一口诀你只要记住这个对应关系就不会把实现方式搞混。层序遍历还有一个非常实用的变种就是按层分组输出这个在“求二叉树每层的平均值”和“按层打印”这类题目中很常见。做法是在遍历时记录当前队列的大小只处理当前层的节点下一层留在队列里while (!q.empty()) { int level_size q.size(); for (int i 0; i level_size; i) { BiTree node q.front(); q.pop(); printf(%c , node-data); if (node-lchild ! NULL) q.push(node-lchild); if (node-rchild ! NULL) q.push(node-rchild); } printf(\n); }这里的level_size就是当前层的节点数通过它把每一层隔开非常实用强烈推荐记住。5. 二叉树的高频操作深度、节点数、删除、判断5.1 求深度与节点数递归解法的经典入口求二叉树的深度是递归入门最经典的题目。思路是拆解为子问题整棵树的深度等于左子树深度和右子树深度的较大者加1。递归边界是空树深度为0。int maxDepth(BiTree T) { if (T NULL) return 0; int leftDepth maxDepth(T-lchild); int rightDepth maxDepth(T-rchild); return leftDepth rightDepth ? leftDepth 1 : rightDepth 1; }这段代码看起来简单但你要注意一个细节先递归左子树再递归右子树最后比较。这个顺序不能颠倒因为必须先知道子树的深度才能计算当前节点的深度。求节点数的思路类似节点总数等于左子树节点数加右子树节点数再加1。叶子节点数的判断条件则是左右孩子都为空。这三个问题深度、节点总数、叶子数是递归思想的三个闭环把这三个写熟练了你对递归的理解会上一个台阶。5.2 搜索二叉树的插入与删除搜索二叉树的操作是笔试面试的重点因为删除操作涉及多种情况很能考察你对指针和语法细节的掌握。插入很简单从根节点开始如果值比当前节点小往左走比当前节点大往右走直到找到空位置创建新节点放进去。插入的关键是记住父节点因为你需要把新节点挂到父节点的左或右。删除分三种情况叶子节点直接删父节点的相应指针置空。只有一个孩子用孩子顶替被删节点。有两个孩子用左子树中最大的节点或右子树中最小的节点来替换被删节点的值然后删除那个用来替换的节点。第三种情况比较绕代码我贴一下核心逻辑BiTree deleteNode(BiTree root, int key) { if (root NULL) return NULL; if (key root-data) { root-lchild deleteNode(root-lchild, key); } else if (key root-data) { root-rchild deleteNode(root-rchild, key); } else { // Case 1: 叶子节点 if (root-lchild NULL root-rchild NULL) { free(root); return NULL; } // Case 2: 只有一个孩子 if (root-lchild NULL) { BiTree tmp root-rchild; free(root); return tmp; } if (root-rchild NULL) { BiTree tmp root-lchild; free(root); return tmp; } // Case 3: 有两个孩子找右子树最小节点 BiTree minNode root-rchild; while (minNode-lchild ! NULL) { minNode minNode-lchild; } root-data minNode-data; root-rchild deleteNode(root-rchild, minNode-data); } return root; }这里的技巧是用递归的返回值直接作为新的子树根节点这样不用显式记录父节点代码简洁很多。你在自己写的时候要注意必须有返回值并且让你上层调用的地方接收否则删完节点后父节点的指针就悬空了。5.3 判断平衡二叉树判断一棵树是不是平衡二叉树既要判断左右子树深度差不超过1又要判断左右子树本身也是平衡的。注意这里有个性能陷阱如果不做优化每个节点都要计算深度复杂度会变成O(n^2)。优化的思路是自底向上利用后序遍历的特点在递归返回时顺手检查平衡性一旦发现不平衡立即返回标记避免重复计算。int checkBalance(BiTree T, int *height) { if (T NULL) { *height 0; return 1; } int leftH, rightH; if (!checkBalance(T-lchild, leftH)) return 0; if (!checkBalance(T-rchild, rightH)) return 0; if (abs(leftH - rightH) 1) return 0; *height (leftH rightH ? leftH : rightH) 1; return 1; }一次遍历同时解决深度计算和平衡性判断这种“边递归边做判断”的思路在二叉树算法里非常常见面试官很吃这一套。能把这个写出来说明你理解了后序遍历的本质。6. 常见问题与排查技巧实录6.1 最典型的几个报错与修复我帮人debug二叉树实验报告的时候遇到最多的是下面这些错误空指针访问递归遍历时没有判空直接访问node-data。树本来就是递归定义的空子树是合法的每次进入函数第一行应该是判空。递归出口丢失函数里忘了写if (T NULL) return导致无限递归。这个最常见的表现就是程序崩溃或栈溢出。传参方式错误在C语言里如果删除节点时直接传root而不返回新指针删除操作在函数内部完成了但对调用者的root没有影响。解决办法就是前面代码里的写法——返回新的子树根。遍历顺序混淆前序和中序的代码只差一行抄错printf位置会导致结果完全不对。建议背下来之前说的“根的位置”规律不要死记代码。6.2 遍历结果分析速查表这个表是我在刷题时整理的考试和面试时非常管用已知条件能否唯一确定二叉树方法前序 中序能前序定根中序分左右后序 中序能后序定根中序分左右前序 后序不能无法区分左右子树边界为什么前序加后序不能确定因为如果某个节点只有一个孩子前序和后序都只知道有一个孩子但不知道是左孩子还是右孩子。这点很多教材都容易忽略你理解后就不会再掉进这个坑里。另外层序遍历序列和中序遍历序列也能唯一确定二叉树思路类似层序先出现的节点一定在更上层用中序划分左右子树范围。6.3 递归调试的不传之秘调试递归函数很多人喜欢到处printf我发现最省事的方法是在函数入口打印当前参数和缩进。比如打印“进入节点值X深度N方向左/右”退出时打印“离开节点值X”。这样你能清晰看到递归的调用顺序判断访问顺序对不对。如果你用的是IDE断点设置在递归函数的入口处观察调用栈的变化那个效果更好。我看到很多学生在递归里打满了printf看半天还是搞不清楚换成调用栈观察一眼就知道问题在哪。还有一个很重要的自查动作测试用例要覆盖空树、只有根节点、左斜树、右斜树、完全二叉树这五种情况。我见过太多人用一个三层满二叉树测试通过就觉得没问题结果一上机就挂。每写一个函数就把这五种情况都跑一遍能帮你省下大量debug时间。7. 实用技巧与学习路径建议7.1 二叉树题目练习的最优顺序如果你是在备考或者准备面试我建议按照下面这个顺序刷题可以避免低效乱刷基础层求二叉树深度、求叶子节点数、求第k层节点数。这4道题用来吃透递归。遍历层前序、中序、后序、层序的递归和迭代各写一遍写完要能达到默写水平。结构层翻转二叉树、判断两棵树是否相同、判断对称二叉树。这几道题用于加深对递归返回值的理解。构造层由前序和中序构造二叉树、由中序和后序构造二叉树。搜索树层验证搜索二叉树、搜索二叉树第k小元素、删除搜索二叉树节点。做完这20道左右的题目二叉树这个知识点基本是稳的。不算多每天两题两个星期就能搞定。7.2 借助可视化工具建立直觉初学二叉树的人很多时候脑内没有图像代码跑完也不确定对不对。我建议你先用现成的可视化工具比如在线的二叉树可视化网站把树画出来把遍历顺序标出来然后再对照自己代码的输出结果。我自己常用的方式是在纸上画一棵5个节点的树手动模拟遍历顺序再用代码跑一遍对照答案。这个过程看起来很笨但对建立直觉帮助极大。写代码前先画图定位写完之后验证结果两个步骤缺一不可。7.3 习惯用空树作为递归边界最后分享一个我从工作里总结出来的小习惯所有树相关的递归函数第一行一定是判断当前节点是否为空。这个习惯看似基础但能帮你规避80%的空指针崩溃。不管函数返回int、指针还是布尔值空树的返回值都要想清楚。比如求深度返回0求节点数返回0判断是否平衡返回1删除节点返回NULL。边界想清楚了递归函数才不会在极端输入下崩掉。二叉树这块内容知识点密集但逻辑非常清晰它不像排序算法那样有那么多变体核心就那几个套路。把这个结构啃下来后续学习图、堆、搜索算法的时候你会明显感觉到思维的势能。