做数据结构的同学绕不开“树”这个坎。前面几篇我们一直在跟线性结构较劲数组、链表、栈、队列顶多再玩玩串和广义表都是一条路走到黑的结构。到了二叉树这一章你会发现思维模式完全变了从“一对一”跳到了“一对多”递归开始成为主角很多经典算法题也在这里扎堆出现。这篇笔记我想把二叉树最核心的内容串一遍包括基本概念、遍历方式、深度计算、搜索二叉树的增删查以及我实际写代码时踩过的一些坑。适合正在学数据结构、准备考研或者刷算法题的同学参考也欢迎已经工作但想回头巩固基础的朋友一起聊。1. 为什么二叉树是数据结构的分水岭1.1 从线性思维到树形思维的转变先说说我自己的感受。链表和数组再怎么折腾本质上还是在一条线上做文章最多就是双向、循环脑子里始终有个“前驱后继”的概念。到了树这里一个节点可以有多个“后继”数据之间出现了层级关系。这个转变如果没想明白后面学图、学搜索、学动态规划都会觉得别扭。二叉树是树形结构里最简单也最实用的一种。每个节点最多伸出两个分支左子树和右子树。正因为分支数被限制在二很多性质变得非常好推导比如深度为 k 的二叉树最多有 2^k - 1 个节点第 i 层最多有 2^(i-1) 个节点这些结论在满二叉树和完全二叉树上可以直接验证。从应用角度看编译器里的表达式树、文件系统的目录结构、数据库索引里的 B 树底层思路都能跟二叉树扯上关系。甚至后续要学的堆、哈夫曼树、红黑树本质上都是在二叉树基础上做变换。所以把二叉树啃扎实等于给后面一大堆内容铺路。1.2 树和二叉树的区别要分清很多初学者会把“树”和“二叉树”混着说其实严格来讲它们不是一回事。树要求每个节点可以有任意多个孩子而二叉树的每个节点最多只有两个孩子并且左右子树是有顺序的调换位置会变成不同的树。这种“左右有序”的特性特别重要。比如你用二叉树表示一个算术表达式减法或除法如果左右子树一换整个表达式的语义就变了。所以代码实现的时候左孩子指针和右孩子指针必须区分清楚不能因为结构上长得像就随便互换。2. 二叉树的核心概念与关键性质2.1 节点、度、深度、高度先把名词叫准学二叉树有几个术语必须较真不然做题的时候容易被绕晕。节点Node是树的基本组成单位包含数据和指向子节点的引用。度Degree指的是一个节点拥有的子树个数二叉树里节点的度只能是 0、1、2 这三种情况。度为 0 的节点叫叶子节点这个在统计题里非常高频。深度Depth和高度Height这两个概念最容易被混淆。深度是从根节点往下数根节点深度为 0 或 1不同教材定义不一样考试时以题目说明为准高度是从叶子节点往上数叶子节点高度为 0 或 1。我这里采用国内教材比较常见的定义根节点深度为 1单个节点高度为 1。做题前先确认教材口径不然每题都会差一个 1。还有个硬核结论需要记住在任意一棵非空二叉树中叶子节点数等于度为 2 的节点数加 1。这个性质我在“已知两种遍历序列求另一种遍历序列”的题目里反复用到推导过程不复杂感兴趣可以自己画几棵树验证一下。2.2 满二叉树与完全二叉树满二叉树Full Binary Tree指每一层的节点数都达到最大值也就是第 i 层有 2^(i-1) 个节点整棵树有 2^k - 1 个节点k 是深度。这种树长得很对称适合用来推导公式但实际业务中很少见。完全二叉树Complete Binary Tree稍微宽松一些它要求最后一层可以不满但节点必须从左到右连续排列不能左边空着右边却有节点。为什么要定义这种结构因为完全二叉树可以用数组存索引之间存在直接的计算关系编号为 i 的节点左孩子是 2i右孩子是 2i1父节点是 i/2。这个性质是堆排序的基石也是后面学线段树的前提。2.3 搜索二叉树BST到底在搜什么搜索二叉树也叫二叉排序树、二叉查找树它的规则很简单左子树上所有节点的值都小于根节点右子树上所有节点的值都大于根节点且左右子树本身也满足这个条件。换句话说中序遍历一棵 BST 得到的结果一定是有序的。这个“中序有序”的性质特别重要因为它把“查找”变成了一个二分的过程。查找一个值时从根出发比当前节点小就走左比当前节点大就走右平均时间复杂度为 O(log n)。如果树长得特别歪比如按有序序列依次插入BST 会退化成链表查找复杂度直接变成 O(n)。这个退化问题后面专门讲。3. 二叉树的节点定义与遍历实现3.1 用 C 语言定义二叉树节点学习数据结构我建议至少用 C 语言手写一遍节点定义和遍历不要一上来就依赖标准库。C 语言的结构体和指针能把“引用”这个概念暴露得比较清楚方便理解内存层面的关系。节点定义长这样#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;每个节点只有三个成员数据域 val左孩子指针 left右孩子指针 right。这个结构看起来跟双向链表很像但组织关系完全不同。链表的节点之间是前后逻辑二叉树的节点之间是父子逻辑。建议在纸上画一棵不少于 7 个节点的树然后把这个结构手工对应一遍很多疑惑会自然消失。3.2 手动创建一棵测试二叉树写算法题的时候经常需要手动构建一棵树来验证代码。我习惯写一个辅助函数一次性用数组初始化节点再通过左右指针把它们串起来TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } TreeNode* buildDemoTree() { // 1 // / \ // 2 3 // / \ \ // 4 5 6 TreeNode* n1 createNode(1); TreeNode* n2 createNode(2); TreeNode* n3 createNode(3); TreeNode* n4 createNode(4); TreeNode* n5 createNode(5); TreeNode* n6 createNode(6); n1-left n2; n1-right n3; n2-left n4; n2-right n5; n3-right n6; return n1; }我习惯把测试树的形态用注释直接画出来这样后面看代码的时候不用重新脑补结构。这里要特别注意malloc 出来的节点用完要 free否则会有内存泄漏这是很多人刷题时不会考虑、但实际工程里一定会遇到的事。3.3 前序、中序、后序遍历递归版本遍历是二叉树最核心的操作几乎所有题目都建立在遍历的基础上。所谓前序、中序、后序指的是根节点被访问的时机分别在最前、中间、最后。前序遍历先访问根再遍历左子树最后遍历右子树。中序遍历先遍历左子树再访问根最后遍历右子树。后序遍历先遍历左子树再遍历右子树最后访问根。递归实现非常简洁void preorder(TreeNode* root) { if (root NULL) return; printf(%d , root-val); preorder(root-left); preorder(root-right); } void inorder(TreeNode* root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); inorder(root-right); } void postorder(TreeNode* root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-val); }以中序遍历为例调用顺序是不停地往左走到空回溯访问根再往右走。这跟你用手在树上比划“从左下角开始绕一圈”的路径是吻合的。初学的时候建议用不超过 3 层的树手动推演一遍递归过程把函数调用栈画出来基本就通了。这三个遍历顺序对应不同的应用场景。前序遍历可以用来复制一棵树因为你先处理根再递归处理左右结构信息不会丢。中序遍历在 BST 里能直接得到有序序列是很多查找类问题的抓手。后序遍历适合做树的删除因为你需要先递归释放左右子树最后才能释放根节点。3.4 层序遍历与队列的配合层序遍历广度优先遍历是按从上到下、从左到右的顺序访问节点。它跟递归的套路不太一样更依赖队列的先进先出特性。思路是根节点入队循环中取出队头节点并访问再将其左右孩子依次入队。#include string.h #define MAXN 100 void levelOrder(TreeNode* root) { if (root NULL) return; TreeNode* queue[MAXN]; int head 0, tail 0; queue[tail] root; while (head tail) { TreeNode* cur queue[head]; printf(%d , cur-val); if (cur-left) queue[tail] cur-left; if (cur-right) queue[tail] cur-right; } }队列如果用数组实现要注意容量上限。实际考试或面试时如果树的规模不确定建议写一个简单的链式队列或者直接借用 C 的std::queue避免数组溢出这种低级问题。层序遍历还有一个很常见的变种按层分组输出也就是每层打印一行。这个可以用一个变量记录当前层的节点数循环内处理完一整层再进入下一层。4. 二叉树的深度计算与递归心法4.1 最大深度和最小深度的区别二叉树的最大深度也叫高度在面试中几乎是必考题。递归写法特别优雅int maxDepth(TreeNode* root) { if (root NULL) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }思路是当前这棵树的深度等于左子树深度和右子树深度中较大者加 1。空树深度记作 0。这个递归强调了一个关键点你需要信任子问题能给出正确结果。不要试图在脑子里展开整棵树的递归过程否则层数一多就懵了。只看当前节点和它的左右子树返回值就能写出正确代码这就是递归的精髓。最小深度比最大深度稍微绕一点。它定义的是从根节点到最近叶子节点的路径长度。很多人直接写int minDepth(TreeNode* root) { if (root NULL) return 0; int leftDepth minDepth(root-left); int rightDepth minDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }这个写法在部分用例上是错的。比如一棵树只有右子树、没有左子树那左子树的最小深度是 0按上面的写法会返回 1但实际从根到最近叶子节点的路径长度不是 1因为根节点根本没有左孩子你不能把“左边不存在”当成“左边有叶子”。正确的写法应该加一个判断如果左子树为空就直接返回右子树的最小深度加 1如果右子树为空就返回左子树的最小深度加 1两边都不为空才取较小值。这是非常经典的“看似对、实则错”的坑值得记录下来。4.2 统计节点数和叶子节点数统计节点总数的递归也很直接int countNodes(TreeNode* root) { if (root NULL) return 0; return 1 countNodes(root-left) countNodes(root-right); }统计叶子节点数需要加一个条件当某个节点左右孩子都为空时它就是叶子返回 1。int countLeaves(TreeNode* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return countLeaves(root-left) countLeaves(root-right); }这两个函数虽然简单但我建议把前面提到的性质“叶子节点数 度为 2 的节点数 1”结合着验证一遍。你在同一棵树上分别统计叶子节点数和度为 2 的节点数会发现这个等式始终成立。这种验证方式能帮你把抽象公式变成肌肉记忆远比死记硬背可靠。4.3 递归函数的“三步走”写法我总结了一个模板适合绝大多数二叉树递归题确定函数签名和返回值想清楚你要从子问题那里获得什么信息。写递归出口通常是root NULL时返回什么以及是否需要对叶子节点做特殊处理。递归调用左右子树根据子问题的结果组合出当前节点的答案。写完之后用一小棵只有两层的树做“最小验证”再手推几个边界用例基本不会出大问题。很多同学在递归里卡住是因为总想把每一步递归调用栈都看透。其实没必要递归是一种“自底向上”的委托思想把子问题交给函数本身去处理就行。5. 搜索二叉树的增删查与退化问题5.1 查找和插入操作的实现BST 的查找很简单TreeNode* bstSearch(TreeNode* root, int target) { if (root NULL || root-val target) return root; if (target root-val) return bstSearch(root-left, target); return bstSearch(root-right, target); }插入操作是在查找失败的位置挂上新节点。关键点是递归函数要返回“插入后的子树根节点”这样父节点的指针才能正确更新TreeNode* bstInsert(TreeNode* root, int val) { if (root NULL) return createNode(val); if (val root-val) { root-left bstInsert(root-left, val); } else if (val root-val) { root-right bstInsert(root-right, val); } return root; }注意这里用else if而不是单纯的else意思是如果值已经存在就什么都不做。这取决于你希望 BST 是否允许重复值。教材一般默认不重复但实际业务里如果要做计数器可以把val扩展成“值 出现次数”两个字段这样插入重复值时只在次数上做累加树的结构不会畸变。5.2 删除节点的三种情况BST 的删除是经典考点因为它的处理逻辑分三种情况被删节点是叶子直接返回 NULL让父节点对应指针指向空。被删节点只有一个孩子用孩子节点顶上当前节点。被删节点有两个孩子需要在右子树里找最小节点或者左子树里找最大节点用它的值覆盖当前节点然后递归删除那个最小节点。代码实现TreeNode* bstDelete(TreeNode* root, int target) { if (root NULL) return NULL; if (target root-val) { root-left bstDelete(root-left, target); } else if (target root-val) { root-right bstDelete(root-right, target); } else { if (root-left NULL) { TreeNode* rightChild root-right; free(root); return rightChild; } if (root-right NULL) { TreeNode* leftChild root-left; free(root); return leftChild; } // 左右孩子都存在找右子树中的最小节点 TreeNode* minNode root-right; while (minNode-left ! NULL) { minNode minNode-left; } root-val minNode-val; root-right bstDelete(root-right, minNode-val); } return root; }这里最容易被忽略的地方是用右子树最小节点覆盖根节点之后还要递归删除那个最小节点不然树里会出现两个重复值。还有一种写法是直接摘除最小节点把它挪上来但那种实现需要维护父节点指针写起来更容易出错。我建议先掌握“值覆盖 递归删除”这种写法它思路清楚不容易漏指针。5.3 退化成链表的问题与平衡思路如果按 1, 2, 3, 4, 5 这样的顺序插入 BST树会变成一条只有右孩子的链查找效率和链表没有区别。这就是为什么红黑树、AVL 树这类平衡二叉树会出现。它们通过旋转操作让树保持相对平衡保证高度在 O(log n) 级别。这篇笔记不打算展开平衡树的具体实现但希望你在学 BST 时就能意识到这个隐患。刷 LeetCode 和数据结构实验题的时候经常要构造极端用例来验证自己的 BST 实现。如果发现插入大量有序数据后程序性能明显下降别怀疑是编译器的问题大概率是树已经退化成链表了。6. 常见问题与排查技巧实录6.1 空指针访问与野指针问题链式二叉树最烦的错误就是对空指针解引用。常见场景是在遍历时直接访问root-left-val而没有先判断root-left是否为空。排查方法很简单所有涉及指针访问的代码先问自己“这个指针一定非空吗”。如果答案是“不一定”就加空判断。递归写法里root NULL的出口必须放在函数最前面否则后续逻辑一执行就崩。还有一种野指针问题出现在释放二叉树上。释放一棵树应该用后序遍历先释放左子树、再释放右子树、最后释放根节点。如果先释放根节点再访问左右指针就是典型的 use-after-free。void destroyTree(TreeNode* root) { if (root NULL) return; destroyTree(root-left); destroyTree(root-right); free(root); }6.2 遍历结果对不上先检查建树逻辑很多同学写测试的时候发现遍历输出和预期不一致第一反应是遍历写错了。其实很多情况下是树本身就没建对。建议先写一个简单的打印函数校验每个节点的父子和左右关系再确认遍历逻辑。我自己的习惯是建完树后先用层序遍历打印一遍因为层序能直观反映树的形状只要树画得对层序结果一眼就能看出来。6.3 递归深度过大导致栈溢出当树的深度超过几千层时递归实现会爆栈。这是递归写法在工程上的天然短板。刷题平台一般不会出这么深的用例但实际项目里处理极不平衡的搜索树时可能会遇到。这种时候需要把递归改成显式栈迭代。前序和中序用栈模拟的思路比较直接后序会更麻烦一点可以借助两个栈或者“先访问根再入栈右左”的方式细节这里不展开属于后续进阶内容。我在做算法题的过程中有个体会越来越深二叉树题目几百道核心其实就那么几个原型——遍历、深度、路径、公共祖先、序列化、BST 套路。把最基础的递归遍历和几个关键操作练到“手比脑子快”后面遇到变形题就不会慌。建议你每一版代码都亲手敲一遍不要只看别人的答案数据结构这个东西眼睛会了不等于手会了。