二叉树核心知识点全解析：从遍历到删除，搞定高频面试题

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，右孩子下标为2i+1，父节点下标为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，访问D，D为空返回，再进入E，访问E，E返回，B的左子树和右子树都访问完了，B返回，回到A的右子树，访问C。

关键点在于：递归函数的调用栈是后进先出的。前序遍历时，A先入栈被访问，然后B入栈访问，D入栈访问，D返回后E入栈访问，E返回后C入栈访问。这个调用过程理解了，递归遍历就没有秘密了。

4.3 迭代实现：显式栈模拟递归

递归虽然好写，但在二叉树深度很大的时候，递归会消耗大量栈空间，极端情况下直接栈溢出。面试中也经常要求写出非递归版本，考察你对栈的理解。

非递归前序遍历的思路是用一个显式栈来模拟递归的调用过程：

void preOrderIterative(BiTree T) { if (T == NULL) return; stack<BiTree> 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) { stack<BiTree> 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; queue<BiTree> 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。边界想清楚了，递归函数才不会在极端输入下崩掉。

二叉树这块内容，知识点密集但逻辑非常清晰，它不像排序算法那样有那么多变体，核心就那几个套路。把这个结构啃下来，后续学习图、堆、搜索算法的时候，你会明显感觉到思维的势能。