上个月帮一个准备考研的朋友做数据结构串讲聊到二叉树那一章他跟我说“前面的链表还能画图硬推到了树这里递归一上代码就彻底看不懂了。”这句话我太熟了。几乎每个刚开始碰数据结构的人都会卡在同一个位置上不是不知道“先序、中序、后序”这三个口诀而是不知道递归在底层到底怎么跑更不知道这些遍历序列组合起来还能还原出一整棵树。今天这篇就专门把二叉树这块掰开揉碎讲一遍从结点定义、四种遍历、深度计算到根据先序中序还原二叉树再到搜索二叉树、AVL树、线索二叉树这些高频考点一次串个完整。无论你是考研、期末突击、软考还是面试前临时抱佛脚刷数据结构拿这篇文章当索引照着过会比翻教材来得更快。1. 二叉树在数据结构里的位置1.1 为什么只分“左”和“右”链表、栈、队列这类线性结构处理的是“一对一”的关系每个结点最多只有一个直接后继。但现实里的数据关系远不止“一排排站着”文件目录套子目录、公司组织架构、编译器的语法分析树全是“一对多”的层级关系。要表达这种关系就需要非线性结构而树是最自然的模型。那为什么偏偏是“二叉树”而不是三叉树、四叉树两个原因。第一两个分支足够表达任意多叉结构。把多叉树转成二叉树有一个很经典的方法叫“左孩子右兄弟”也就是说任意一棵树都能用“左指针指向第一个孩子右指针指向下一个兄弟”的方式转成二叉树信息量一点不丢。第二两个分支让代码结构异常简洁。你写递归的时候就知道了左子树右子树各处理一次逻辑是天然的二分。二叉树还有一个特殊品类叫“完全二叉树”它每一层都从左往右铺满只有最后一层允许缺右侧结点。完全二叉树因为序号连续可以直接用数组存父节点下标和子节点下标之间有着漂亮的数学关系堆排序、优先队列全建立在这个关系上面。可以说二叉树是“既能理解树结构又能适配计算机存储”的最佳折中。1.2 这几个基础概念建议刻进脑子里有些概念到面试前还在混淆我直接列一个最小清单结点的度结点拥有的子树个数二叉树里度只能是0、1、2。叶子结点度为0的结点也叫终端结点。树的深度高度根结点到最远叶子结点的路径上的结点层数。按“根在第1层”算只有一个根的树深度是1空树深度是0。满二叉树每一层都满第k层有2^(k-1)个结点。完全二叉树除了最后一层上面都是满的最后一层结点从左往右连续排列中间不能有空档。还有一个经常出现在选择题里的结论对于任何一棵非空二叉树叶子结点数 n0 等于度为2的结点数 n2 加1也就是 n0 n2 1。这个结论可以快速证明设总结点数 n n0 n1 n2边的数量 m n - 1每个结点除了根都有一条边指向它同时 m 0n0 1n1 2*n2 n1 2n2。联立可得 n0 n2 1。这个推导几乎每年考研选择题都有别死记自己推一遍就忘不了。1.3 二叉树在真实系统里解决什么问题很多人学二叉树觉得“这东西只活在考试里”其实二叉树的应用比想象中密集。最典型的是表达式求值一个四则运算表达式可以解析成表达式树叶子是操作数内部结点是运算符后序遍历这棵树就能得到后缀表达式计算机拿后缀表达式做栈运算非常顺。再比如哈夫曼树根据字符频率构建带权路径最短的二叉树压缩算法里常见的哈夫曼编码就是靠它生成的。数据库里的B树索引虽然不严格是二叉树但从二叉搜索树一路平衡化、多路化的演化路径本质上就是二叉树思维的延伸。堆是一种用完全二叉树实现的结构操作系统调度、TopK问题都在用。理解了二叉树再看这些工程结构会轻松很多。2. 先动手把一棵树存起来2.1 三种存储方式考试和工程各用哪个二叉树的存储方式主要有两种思路一种是顺序存储用数组另一种是链式存储用指针。顺序存储的核心是给结点编号根结点存下标0那么对于下标为 i 的结点左孩子下标是 2i 1右孩子是 2i 2父节点是 (i-1)/2。这种存储对完全二叉树极其友好几乎不浪费空间而且父找子、子找父都只要一个公式。但普通二叉树如果用数组存中间会有大量空位极端情况下一个只有右链的“斜树”数组长度要求是2的k次方级别空间浪费严重。链式存储则长得很像语言里的结构体每个结点自带两个指针。考试和面试里绝大多数题目都是基于链式二叉树的因为递归操作左子树右子树太自然了。三叉链表是二叉链表的增强版多了一个指向父节点的指针某些题目要求找父节点或者回溯时会用到但日常做题碰得少。对比下来顺序存储适合“空间紧凑的完全二叉树”链式存储适合“任意形态的二叉树以及需要频繁增删改的场景”。选择题喜欢问这个记住一个关键印象词完全二叉树用顺序普通二叉树用链式。2.2 二叉链表定义与“空指针域”的秘密C语言的二叉链表定义就是严蔚敏教材里那个经典结构typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;Python里对应写成类class TreeNode: def __init__(self, val): self.val val self.left None self.right None这里有一个特别爱考的小结论n个结点的二叉链表一共有 2n 个指针域其中真正指向孩子的指针数等于边数 n-1所以空指针域的数量是 2n - (n-1) n1。也就是说一棵有10个结点的二叉树它的链式存储里一定有11个空指针。这个数字看起来平平无奇但它就是后面线索二叉树的地基——线索二叉树就是把这些空指针“废物利用”起来存前驱和后继信息。2.3 用先序扩展序列创建一棵二叉树创建一个二叉树最直观的方式是“手动new结点再连接”但在代码题里更常见的是给出一个先序扩展序列让你递归建树。所谓扩展序列就是遇到空孩子的位置用一个特殊符号比如#占位。比如先序序列ABD##E##C##对应一棵根为A、左孩子为B、右孩子为CB的左孩子为D、右孩子为E的树。C语言实现长这样void CreateBiTree(BiTree *T) { char ch; scanf( %c, ch); if (ch #) { *T NULL; } else { *T (BiTree)malloc(sizeof(BiTNode)); (*T)-data ch; CreateBiTree((*T)-lchild); CreateBiTree((*T)-rchild); } }注意几个细节。第一scanf的格式串里那个空格很关键它能跳过前一次输入残留的换行符不然代码会莫名其妙读错字符。第二函数参数用的是二级指针 BiTree *T因为我们要在函数内部修改指针本身的值让它指向新分配的结点一级指针传进去只能修改指针指向的内容改不了指针本身。这也是C语言里最常见的坑之一很多初学者就是在这里被绕晕。Python版本更简单因为它天然传引用def create_by_preorder(data): if not data: return None ch data.pop(0) if ch #: return None root TreeNode(ch) root.left create_by_preorder(data) root.right create_by_preorder(data) return root这个递归过程本身也透露了遍历的顺序先建根再建左子树再建右子树。把这行逻辑记住后面理解先序遍历就顺了。3. 遍历先序、中序、后序、层序3.1 “序”的本质是根的位置四种遍历里先序、中序、后序都是深度优先层序则是广度优先。很多人背口诀“根左右、左根右、左右根”背得很熟但一到具体题目就分不清。其实核心就一句话按“根被访问的时机”命名。先序遍历根最先被访问然后访问左子树再访问右子树即根左右。中序遍历先去左子树逛一圈再访问根最后去右子树即左根右。后序遍历先左、再右、最后才轮到根即左右根。举一棵具体的树A / \ B C / \ \ D E F先序遍历结果A B D E C F 中序遍历结果D B E A C F 后序遍历结果D E B F C A 层序遍历结果A B C D E F你看中序遍历结果里A把序列分成左右两半左边D B E全是左子树的结点右边C F全是右子树的结点。这个“中序序列天然能分离左右子树”的性质后面还原二叉树时会用到极致。3.2 递归遍历三行代码换个位置就是另一种遍历递归遍历的代码量少得惊人。以Python为例def preorder(root): if root is None: return print(root.val, end ) preorder(root.left) preorder(root.right) def inorder(root): if root is None: return inorder(root.left) print(root.val, end ) inorder(root.right) def postorder(root): if root is None: return postorder(root.left) postorder(root.right) print(root.val, end )三个函数结构完全一样只是 print 的位置不同。print 在最前就是先序在中间就是中序在最后就是后序。这个“三行代码搞定三种遍历”的版本一定要自己手敲几遍敲多了你会有一种肌肉记忆。递归遍历的核心是“信任递归”调用 preorder(root.left) 时你不需要在脑子里把整棵左子树全部展开只需要相信这个调用能按先序把左子树全部访问完。很多初学者看递归喜欢一层一层往深处钻钻到第5层就乱了。正确姿势是想清楚“当前结点该做什么”和“子问题交给递归”然后设置好终止条件root is None时返回剩下的交给递归自己跑。3.3 非递归遍历用栈把递归现场搬出来面试手撕题里非递归遍历出现的概率高得离谱而且要求必须会用栈模拟。因为在最坏情况下二叉树会退化成一条链递归深度等于结点数极易栈溢出所以生产环境里的树操作常写成非递归。先序非递归最简单的写法是“根入栈出栈访问右孩子先入栈左孩子后入栈”def preorder_iter(root): if root is None: return stack [root] while stack: node stack.pop() print(node.val, end ) if node.right: stack.append(node.right) if node.left: stack.append(node.left)因为栈是后进先出入栈顺序必须右先左后这样弹出时才能保证左子树先被访问。这个反直觉的点特别容易写反。中序非递归就更有意思了思路是“一路向左压栈没有左孩子就弹栈访问然后转向右子树”def inorder_iter(root): stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() print(cur.val, end ) cur cur.right画个图就明白了先从根出发把根、根的左孩子、左孩子的左孩子……全部压进去直到最左下角。弹出一个结点并访问这个结点没有右孩子就继续弹上一个有右孩子就移动到右孩子再重复“一路向左”的过程。这个算法是笔试和面试的重灾区很多人死记代码但下次还是忘建议找一棵具体的树在纸上把栈的变化过程一步步写出来写一次就通了。后序非递归涉及“第二次经过结点才能访问”的问题需要加标记或者用双栈复杂度更高一点面试偶尔会考。我的建议是先把先序、中序理解透再碰后序不然很容易被绕晕。3.4 层序遍历按层推进的队列思想层序遍历的代码没有递归版本因为它天然是广度优先广度优先的标配结构是队列。from collections import deque def levelorder(root): if root is None: return q deque([root]) while q: node q.popleft() print(node.val, end ) if node.left: q.append(node.left) if node.right: q.append(node.right)流程很直白根先入队出队一个结点就访问它同时把它的左右孩子接到队尾。因为队列是先进先出所以上一层左边结点的孩子会先于右边结点的孩子被访问这就实现了“按层从左往右扫”的效果。层序遍历的变体很多比如求二叉树的最大宽度、判断是否是完全二叉树都是在层序模板上改条件值得牢牢掌握。4. 二叉树的深度递归和层序两种解法4.1 深度、高度、层数教材差异别踩坑求深度这个事看起来简单但每年都有不少人在概念上栽跟头。深度和高度是两个方向深度是从根往下数高度是从叶子往上数。对二叉树整体来说根结点的深度等于树的高度通常就是最大层数。但描述某个结点的时候这两个值就不一样了A结点的深度是它到根的距离高度是它到最远叶子的距离。还有些教材把根的深度规定为0而不是1这时候一棵6个结点的完全二叉树深度就不是3而是2。不同教材、不同题库的约定不一样做题先看题目是否明确“根在第1层”。我一般建议默认根在第1层遇到公式题再根据题目语境调整。4.2 递归求深度返回值是怎么一层层传上去的求深度最常见的解法是递归代码短到让人怀疑int maxDepth(BiTree T) { if (T NULL) { return 0; } int leftDepth maxDepth(T-lchild); int rightDepth maxDepth(T-rchild); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }核心是一棵树的深度 max(左子树深度, 右子树深度) 1。空树深度是0作为递归出口。初学者最难理解的是返回值传导。看前面那棵树A / \ B C / \ \ D E FD、E、F都是叶子它们的左右孩子是NULL所以叶子结点的 leftDepth0、rightDepth0max取0再加1返回1表示叶子自身为1层。到B结点时左子树D返回1右子树E返回1B返回2。到C结点左孩子是NULL返回0右孩子F返回1C返回2。最后到A左子树返回2右子树返回2max取2再加1得到3。这就是整棵树的深度。这个推导过程值得在纸上画一遍它会把“递归返回值怎么一层层向上汇总”这件事彻底搞明白。4.3 层序求深度和完全二叉树的深度公式递归求深度代码简单但在极端链式结构下递归深度太大可以用层序遍历来求。思路是每次处理完一整层就深度加1def max_depth_level(root): if root is None: return 0 q deque([root]) depth 0 while q: size len(q) depth 1 for _ in range(size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return depth每轮循环开始时队列里的结点正好是同一层的全部结点用一次for循环把它们全部弹出同时把下一层结点入队循环结束后depth自然就加到了树的层数。这个模板在求“最大宽度”时也能复用。完全二叉树还有一种纯数学求法结点数为 n 的完全二叉树深度是 floor(log2 n) 1。比如6个结点的完全二叉树log2(6)≈2.58取整是2加1等于3。这个公式在选择题里能救命省去画图时间。5. 已知先序和中序还原整棵二叉树5.1 为什么先序中序能唯一确定树二叉树的遍历序列很像一副拼图的碎片某些组合能完整复原某些组合不行。先序序列的第一个元素一定是根结点拿到根结点之后在中序序列里找到根的位置根左边的元素全是左子树的结点根右边的元素全是右子树的结点。先序序列里紧接着的“左子树长度”那部分又正好是左子树的先序序列。这样一来根定了、左右子树的范围也定了剩下的问题被缩小成两个规模更小的子问题天然适合递归。后序中序同理后序序列的最后一个元素是根同样能用中序序列分离左右子树。所以考研和面试题里最常见的就是这两种组合。5.2 手推一遍先序ABDGCEF、中序DGB AECF用一道典型题走一遍。设先序序列为A B D G C E F中序序列为D G B A E C F。第一步先序第一个元素是 AA是整棵树的根。在中序里找AA左边是D G B右边是E C F所以A的左子树有3个结点右子树有3个结点。第二步处理左子树。先序序列里A后面的B D G长度是3正好就是左子树的先序。左子树先序第一个元素是BB是左子树的根。中序D G B里B在最右边说明B的右子树为空D和G都在B左边。再看先序D GD是左子树的根中序D G里D在G左边说明D没有左孩子、右孩子是G。第三步处理右子树。先序里剩下的C E F是右子树先序C是右子树的根。中序E C F里C左边是E右边是F所以C的左孩子是E右孩子是F。最终还原出这棵树A / \ B C / / \ D E F \ G整个过程不需要画很多图只要盯住“先序定根、中序分左右”这两句话就够了。我建议你拿另几组序列自己练一遍重点体会“左子树长度”这个桥梁是怎么串联两条序列的。5.3 递归代码实现还原代码上Python实现非常清晰def build_tree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left build_tree(preorder[1:1 idx], inorder[:idx]) root.right build_tree(preorder[1 idx:], inorder[idx 1:]) return rootidx就是根在中序里的下标同时也是左子树的结点数。所以左子树的先序是 preorder[1:1idx]左子树的中序是 inorder[:idx]右子树的先序是 preorder[1idx:]右子树的中序是 inorder[idx1:]。这个切片边界是写代码最容易出错的地方建议对照一个小例子手动试一次宁可慢一点也要把边界想清楚。后序中序的做法一样只是根从先序第一个变成了后序最后一个。5.4 为什么只有先序和后序不行问答题常考这类“为什么”。先序和后序虽然都能定出根但根的孩子是谁、到底是左孩子还是右孩子经常说不清。最经典的例子先序A B后序B A。单独看B它既可以当A的左孩子也可以当A的右孩子两颗树形态不同但先序和后序序列完全相同。所以仅凭先序后序无法唯一确定一棵二叉树。这是很关键的一道送分题理解了例子就能答对。6. 从基础二叉树延伸搜索树、平衡树、线索树6.1 搜索二叉树中序有序的查找结构搜索二叉树BST是一种在普通二叉树基础上加了大小约束的结构左子树所有结点值都小于根右子树所有结点值都大于根。这个约束带来了一个强悍的性质——中序遍历结果是有序的。写一句中序代码BST排出来的就是从小到大。插入逻辑很自然一直到空位就挂上def insert(root, val): if root is None: return TreeNode(val) if val root.val: root.left insert(root.left, val) else: root.right insert(root.right, val) return root查找效率平均是O(log n)但这是建立在树长得比较均匀的前提下。如果插入序列本身有序比如连续插入1、2、3、4BST就会退化成一条链表查找效率掉到O(n)。这个退化问题直接催生了平衡树的需求。删除操作更麻烦一点分三种情况被删结点是叶子直接删只有一个孩子把孩子顶上有两个孩子可以用右子树的最小结点或者左子树的最大结点替代再递归删除那个替代结点。面试时能把三种情况分清楚基本就过关了。6.2 AVL树让树保持“不高不矮”AVL树是严格平衡的二叉搜索树核心指标是平衡因子左子树高度减右子树高度。AVL要求任意结点的平衡因子绝对值不能超过1否则就要旋转调整。调整有四种基本形态LL型、RR型、LR型、RL型。LL型是左子树的左子树过高往右旋转一次解决RR型是右子树的右子树过高往左旋转一次LR型是左子树的右子树过高需要先左旋再右旋RL型是右子树的左子树过高需要先右旋再左旋。不要死背旋转方向我的理解方式是“把冒头的那个结点拎起来让中间值坐上去”。画图推几次就知道旋转本质是把失衡的那条路径掰回中间位置。AVL树保证了树高严格在O(log n)级别所以查找、插入、删除最坏都是O(log n)代价是插入删除时旋转操作本身也有额外开销。嵌入式、操作系统这些对稳定性敏感的场景里AVL的严格平衡有时候比红黑树的宽松平衡更合适这也是热搜词里出现“嵌入式 二叉树之avl树”的原因。6.3 线索二叉树把空指针变废为宝前面提到过n个结点的二叉链表里有n1个空指针域资源闲置太可惜。线索二叉树就是在这上面做文章如果左孩子指针为空就让它指向按某种遍历顺序得到的前驱结点如果右孩子指针为空就让它指向后继结点。为了区分指针到底指向孩子还是线索每个结点需要额外增加两个标志位常用的是 ltag 和 rtag0表示孩子1表示线索。中序线索二叉树用得最多因为中序序列本身就是把树“拉直”成有序序列线索化之后就可以像遍历链表一样顺序访问所有结点不用递归也不用栈。这在频繁需要找前驱后继的场景里比如某些文本编辑器、索引结构很有价值。线索化过程本质上还是中序遍历只是在访问结点时要额外判断左右孩子为空并挂上线索。考试题常考“给一棵树画出它的中序线索二叉树”思路是先写中序序列再找出每个空指针指向前驱还是后继画起来就不乱了。7. 常见题型与避坑经验7.1 高频考点速查表我把复习时最常遇到的题型按“题目问什么-核心思路-出现场景”整理了一下考查点核心思路常考场景空指针域数量n个结点空指针域n1选择题、填空题叶子数与度为2的关系n0 n2 1选择题、判断题求深度递归max(左,右)1层序按层计数大题、机试已知先序中序还原树先序定根中序分左右递归分治大题、面试手撕三种遍历序列互推找根、定左右、切长度选择、简答判断完全二叉树层序出现空结点后不能再有非空结点选择、面试判断平衡二叉树后序遍历边求高度边截断面试、408线索二叉树找前驱后继根据ltag/rtag判断直接指还是回退选择、大题这表不是用来背的是用来做自检的。看到某一行能自己说出思路并写出核心代码这章才算过关。7.2 递归理解与调试建议很多人递归写不对不是不会写函数而是老想“在脑子里完整跑完递归”。我建议改用“黑盒思路”假设递归函数已经能正确解决子问题只关注当前层要拼什么最后把终止条件写对。如果真的跑不通就在递归函数里加打印把当前结点的值、调用前的状态打出来。比如在preorder开头加一句print(fenter: {root.val})结束前加一句print(fleave: {root.val})一跑就能看到完整的调用轨迹。这种调试方式对理解递归的压栈、弹栈过程帮助极大。还有一个小技巧递归函数的返回值不要憋着不接。像求深度、还原二叉树这些场景递归调用的结果要返回给上一层很多人漏写return或者忘接返回值导致结果永远是“致命伤”。写完代码先拿最小例子推一遍比如只有一个根的树确认返回值能正确出来再往上加复杂场景。7.3 我踩过的几个坑第一个坑是深度起点二义性。我复习时用两本教材一本根深度记为0另一本记为1结果同一道题答案不一样。后来我养成习惯做题先找题干有没有“根在第1层”的字样没有就默认按1面试时直接问面试官“根节点深度按1算还是按0算”通常不会被扣分反而显得严谨。第二个坑是还原二叉树时切分序列的边界。第一次手写 build_tree 这类代码时我在切片上反复试错最后总结出一句话“先序跳过一个根取前idx个就是左子树”。现在写代码都是先在草稿纸列出两个序列把根的位置画出来再写切片公式写完基本一次过。第三个坑是判断完全二叉树想当然。有人觉得“只要某个结点没有左孩子它就不能有右孩子”就够了这是不严谨的。更靠谱的做法是层序遍历遇到空结点后如果后面还能出现非空结点就不是完全二叉树。否则就是。我在好几个模拟题里靠这个判断模板救回来了你们也可以直接用。我自己刚学二叉树那会儿最大的体会就是一定要拿着纸笔把递归调用栈画一遍尤其是中序非递归那一路向左的过程。画完一遍很多题不用背也能写出来。这篇就写到这里希望这些经验能让你少走点弯路。