二叉树这个名字刚入行那会儿听着特别“学院派”总觉得是课本里才有的东西。后来真正写代码、调性能、看开源项目源码才发现它无处不在。文件系统的目录层级、数据库索引的底层结构、编译器解析表达式、游戏里的场景组织甚至我们手机上应用列表的展开与收起背后都能找到二叉树的身影。这篇文章我想用比较“白话”的方式把二叉树的定义、术语、存储、遍历和实战场景一次讲透适合刚学数据结构的初学者、准备技术面试的求职者以及已经写过不少代码但没系统梳理过树结构的朋友。1. 二叉树到底在说什么1.1 从一张淘汰赛对阵表说起理解二叉树最舒服的方式我觉得是看体育比赛的淘汰赛对阵表。一场比赛只有两个对手赢的人晋级输的人离场。把每个参赛者看成节点把每场比赛看成父节点整个赛程就是一棵倒过来的树——最上面是决赛往下不断分出半决赛、八强赛直到最底层的所有参赛选手。这种“一分为二”的结构就是二叉树最核心的气质任何一个节点最多只能有两个分支而且这两个分支有明确顺序左边就是左边右边就是右边互换之后意义完全不一样。很多初学者会把二叉树和普通的多叉树混淆。普通树的节点可以有任意多个孩子比如电脑里的文件夹一个目录里可以放几十个文件这是多叉树二叉树则严格限制在“两个以内”。凭什么非要这么限制因为计算机科学里大量精妙算法都建立在“二分”这个动作上——两个分支意味着每走一步只有两条路可选配合递归的思想问题规模可以稳定地变小。二分查找、归并排序这些经典算法内里渗透的都是二分逻辑二叉树正是这种思想最直观的载体。所以可以这么说二叉树是“分而治之”策略在数据结构里最浓缩的体现。1.2 二叉树真正解决的问题它解决的第一类问题是表达层级关系。谁是谁的父节点谁和谁在同一层这种关系用数组或链表都表达得别扭而树天然就是为层级而生的。我看过很多同学用嵌套列表硬凹目录结构代码长得没法维护换成树之后一下子清爽了。第二类问题是快速查找。以二叉搜索树为例左子树的值都小于根右子树的值都大于根查找一个数字时每走一步就可以舍弃一半的可能性平均复杂度是 O(log n)。这个“对数级别”的复杂度支撑起了各类查找表、索引结构的高效运行。第三类问题是维护动态有序数据。数组擅长随机访问但插入和删除要搬动大量元素链表擅长插入删除但查找只能从头走。平衡二叉树介于两者中间在查找、插入、删除三个维度上都保持对数复杂度非常适合需要频繁增删和查找的业务场景。从这些角度看二叉树不只是一个“考试必背概念”而是一套组织数据、解决问题的工具。后面所有内容默认讨论的都是最常见的链式存储二叉树。为了直观讨论我建议你边读边在纸上画一棵小树根节点是 1左孩子是 2右孩子是 3节点 2 下面再有左孩子 4 和右孩子 5。后面所有概念和遍历代码我们都可以拿这棵小树来当例子。2. 核心概念与必备术语2.1 节点、根、叶子这些称谓必须一次性记清一棵二叉树由若干个节点组成节点之间通过指针或引用相连。最顶层的节点叫根节点它没有父节点是一棵树的起点。没有孩子的节点叫叶子节点或者叫终端节点有孩子的节点叫内部节点。一个节点下面的两个分支分别叫左子树和右子树子树本身也是二叉树所以它们还可以继续分叉。树里还有个概念叫“度”指的是一个节点拥有子树的数量。二叉树的每个节点度最大为 2叶子节点的度是 0。另一个容易忽略的概念是“子树”以任意节点为起点它和它的所有后代共同构成一棵子树。这意味着大树里面套着小树这种嵌套结构在写递归时特别重要因为递归函数的每一次调用其实都是在处理一棵更小的子树。用代码来表示一棵二叉树最常见的就是“三个字段”的节点类class TreeNode: def __init__(self, val): self.val val self.left None self.right Noneval 存数据left 和 right 指向左右孩子。很多初学者只把 left 和 right 当成两个普通变量其实它们是指向节点的引用正是这一层又一层引用才把零散的节点串成了有结构的树。理解这一点后面写递归和对树做修改才不会懵。2.2 深度、高度、层级到底怎么算这三个词是笔试和面试的高频词也是最容易混淆的一组概念我在这里一次说清楚。节点深度从根节点从上往下数。如果约定根节点深度为 0那根的孩子深度就是 1再往下依次加 1。有些教材会把根节点深度记为 1两种都行但写代码前必须先约定好不然结果总是差一层。节点高度从叶子节点从下往上数。叶子节点高度为 0它的父节点高度为 1再往上依次加 1。树的高度等于根节点的高度也就是从根到最远叶子节点经过的边数。拿我们的小树来看根是 1孩子是 2 和 32 下面有 4 和 5。那么节点 4 的深度是 2、高度是 0节点 2 的深度是 1、高度是 1整棵树的高度是 2。在递归代码里“树的高度等于 max(左子树高度, 右子树高度) 1”是出现频率极高的模式把这句话想透很多递归就顺了。层级一般从 1 开始数根节点在第一层。第 k 层最多有 2 的 k 减 1 次方个节点。这个公式在判断一棵树是不是满二叉树、计算空间占用时很有用。2.3 满二叉树、完全二叉树、平衡二叉树、二叉搜索树这些名词看起来多其实各有各的用途。满二叉树除了叶子节点外每个节点都有两个孩子而且所有叶子都在同一层。这种树非常“对称”每一层都填满了节点。当树的高度为 h 时满二叉树的总节点数是 2 的 h 次方减 1。完全二叉树最后一层之前的所有层都是满的最后一层的节点从左到右连续排列中间不留空。完全二叉树最大的价值在于它是“堆”的数据基础也正是因为这种树的形态规整它才能用数组紧凑存储。平衡二叉树指任意节点的左右子树高度差不超过 1。这个限制让树保持“匀称”查询时不会出现某条路径特别深的情况。实战中使用的 AVL 树、红黑树本质上都是通过旋转、变色等手段维持平衡让查找复杂度稳定在 O(log n)。二叉搜索树简称 BST它要求左子树所有节点值小于根右子树所有节点值大于根。这个性质让查找、插入、删除都能沿着一条路径走是数据库索引和各类查找表的理论基础。不过需要注意如果数据按升序或降序插入BST 会退化成一根链表性能直接掉到 O(n)。所以实际项目里很少直接用“裸 BST”而是用它的自平衡变体。堆一种特殊的完全二叉树。最大堆要求父节点大于等于子节点堆顶是最大值最小堆相反。堆是优先队列的底层实现后面我会单独讲。把这些形态分清不是为了死记名词而是遇到实际问题时能快速选择合适的数据组织方式。就像盖房子选材料一样先搞清楚每种结构的脾气性格才好下手。3. 二叉树的存储与构建方式3.1 链式存储最直观、最好理解的方案链式存储就是用刚才的 TreeNode 类把节点一个个创建出来再用 left 和 right 连接起来。构建那棵小树代码长这样root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5)看起来简单但它说明了一个关键点树的结构是由引用关系定义的节点里存什么值反而是次要的。面试里经常让候选人手写节点类并构造测试用例练的就是这种“用引用搭结构”的基础能力。链式存储的优点很直接结构直观、好理解、插入删除只需要修改局部引用。缺点是每个节点都要额外存两个引用占用内存多而且节点分散在内存各处对 CPU 缓存不太友好。不过在常规业务场景下这点开销可以接受所以它是实现二叉树最主流的方式。3.2 数组存储紧凑但有限制的方案数组存储的思路是把树“压扁”进一个一维数组节点之间的父子关系靠下标换算。以下标从 0 开始为例下标为 i 的节点左孩子下标是 2 * i 1下标为 i 的节点右孩子下标是 2 * i 2下标为 i 的节点父节点下标是 (i - 1) // 2这套公式成立的前提是树接近完全二叉树。完全二叉树除了最后一层外没有空缺放进数组几乎不浪费空间。堆就是这样实现的用数组存数据push 时插到末尾再“上浮”pop 时把末尾元素放到堆顶再“下沉”所有位置移动都靠下标计算完全不需要指针。如果拿一棵普通二叉树硬塞进数组中间空缺的位置要么留空要么用 None 占位。一旦树很斜比如高度 10 的斜树按完全二叉树的下标去放理论空间可能膨胀到指数级别这不是浪费是灾难。所以我的建议是堆、线段树这类接近完全二叉树的结构用数组存储普通二叉树直接用链式存储简单又安全。3.3 层序数组重建二叉树的实操思路不少笔试题目会给一个按层序遍历顺序排列的数组比如 [1, 2, 3, 4, 5, None, None]要求还原成二叉树。核心思路就是利用下标关系但实现上我建议用队列法比硬算下标更不容易错。from collections import deque def build_tree_from_array(arr): if not arr or arr[0] is None: return None root TreeNode(arr[0]) queue deque([root]) index 1 while index len(arr): node queue.popleft() if arr[index] is not None: node.left TreeNode(arr[index]) queue.append(node.left) index 1 if index len(arr): break if arr[index] is not None: node.right TreeNode(arr[index]) queue.append(node.right) index 1 return root这段代码有两个容易踩坑的细节。第一数组里的 None 不代表“跳过这个位置”而是代表“这里没有节点”所以 index 依然要前进只是不创建节点。第二队列里弹出的节点和数组下标不是一一对位的队列里存的是“等待分配孩子的节点”按顺序分配左孩子和右孩子。建议第一次写的时候手动模拟一遍队列进出过程比干看代码直观得多。4. 二叉树遍历前序、中序、后序与层序4.1 深度优先遍历的三种顺序遍历是二叉树最核心的操作没有之一。深度优先的思路是沿着一条路径尽可能走到底再回过头来处理另一条路径。根据“当前节点、左子树、右子树”的访问顺序分成前序、中序、后序。前序遍历先访问当前节点再左子树最后右子树顺序是 根-左-右。中序遍历先左子树再当前节点最后右子树顺序是 左-根-右。后序遍历先左子树再右子树最后当前节点顺序是 左-右-根。代码上三者几乎一样差别只在“什么时候处理当前节点”def preorder(root, res): if not root: return res.append(root.val) preorder(root.left, res) preorder(root.right, res) def inorder(root, res): if not root: return inorder(root.left, res) res.append(root.val) inorder(root.right, res) def postorder(root, res): if not root: return postorder(root.left, res) postorder(root.right, res) res.append(root.val)我见过不少同学代码背得滚瓜烂熟一到变形题就乱。这里给一个记忆技巧名字本身就是“当前节点在什么时候被访问”的说明。前序就是先看根中序就是左边看完了轮到根后序就是左右都看完了最后轮到根。拿我们的小树跑一遍结果前序[1, 2, 4, 5, 3]中序[4, 2, 5, 1, 3]后序[4, 5, 2, 3, 1]强烈建议自己拿笔画一次把访问顺序标在节点旁边。看完之后你会发现“哦原来是这么个顺序”比任何解释都有效。另外记住一个常用结论中序遍历二叉搜索树结果是有序递增序列这个性质后面做很多题都能用上。4.2 层序遍历与队列实现层序遍历也叫广度优先遍历它一层一层往下走同一层内从左到右访问。上面那棵小树的层序结果是 [1, 2, 3, 4, 5]。标准实现用队列from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: node queue.popleft() result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result如果题目要求“把每一层的节点单独输出”可以每次先记录当前队列的长度 size然后只弹出 size 个节点这样正好把一层全部取出来。后面很多题比如按层输出、求每层最大值、二叉树的右视图都是在这个“按层取”的写法上做文章。层序遍历依赖队列是因为我们需要记住“下一批谁来访问”。队列先进先出天然符合同一层从左到右的访问顺序。提醒一句别只盯着 while queue 这个模板动手模拟一遍队列进出真正想清楚“先来先服务”的过程变体题才能一眼看穿。4.3 遍历结果能反推二叉树吗一个经典问题已知前序和中序遍历序列能不能重建原二叉树答案是可以。思路是前序的第一个节点一定是根在中序序列里找到根的位置它左边就是左子树的中序序列右边就是右子树的中序序列同时可以在前序序列里划出对应的左右子树范围然后递归重建。如果只有前序和后序一般来说无法唯一确定二叉树。因为没有中序序列提供“左右分界”的信息很多种结构都能生成同一对前后序组合。这个结论笔试常考理解了原理比死记结论有用二叉树的“形状信息”藏在成对遍历的交叉关系里少了一个维度就拼不回去。如果你递归基础弱可以先拿三节点的小树手推一遍。根为 1、左子 2、右子 3前序 [1,2,3]中序 [2,1,3]看它们怎么一步步切分。推懂了再扩展到更复杂的树会发现本质就是“找根、切左右、递归”三个动作。4.4 迭代版遍历显式栈替代递归递归遍历虽然优雅但深度大时容易爆栈而且很多面试官会追问迭代写法。前序遍历的迭代版最容易理解用一个栈先压右孩子再压左孩子弹出时访问。def preorder_iter(root): if not root: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res中序迭代稍微绕一点需要沿着左子树一路压栈到头之后弹栈访问再转向右子树def inorder_iter(root): res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left node stack.pop() res.append(node.val) cur node.right return res后序迭代有一个取巧的办法先做“根-右-左”的遍历再把结果反转就得到“左-右-根”。本质上和“先压左再压右”是对称的。这种思路理解起来很简单但用之前要把为什么反转能成立想清楚别只是背代码。5. 二叉树在实战中的典型应用场景5.1 二叉搜索树与有序数据的快速查找二叉搜索树最贴近日常应用。它要求左子树所有节点值小于根、右子树所有节点值大于根所以查找时每走一步就能排除一棵子树平均复杂度 O(log n)。很多数据库索引、内存排序结构都用这个思路。但裸的 BST 有个致命弱点数据如果按递增或递减顺序插入树会退化成一条链查找复杂度跌到 O(n)。因此工程上不会直接用裸 BST而是用红黑树、AVL 树这些自平衡版本它们在插入删除后通过旋转、变色等手段让树保持紧凑。面试里经常问“为什么不用数组排序加二分查找”答案是“动态”二字。数组插入删除要搬动大量元素而树只需要改局部引用。如果数据是静态的、不增不减那数组配合二分确实更快但只要数据在变化树的高效动态维护能力就体现出来了。5.2 堆与优先队列堆是一种完全二叉树最小堆的根永远是最小值最大堆的根永远是最大值。它最经典的应用是优先队列取最大或最小元素、插入新元素都只要沿树高度走 O(log n)。实际中任务调度、求 Top K、Dijkstra 最短路算法底层都是堆。很多人一开始不理解为什么不用“排序后取第一个”关键在于堆只维护“最大或最小”这个信息不需要让整个序列保持完整有序。这其实是数据结构的经典思维先想清楚自己到底需要哪些操作频繁发生再选结构。如果你只需要频繁取极值排序就是浪费。5.3 表达式树与表达式求值编译器解析算术表达式时经常会把表达式解析成一棵表达式树叶子节点是操作数内部节点是运算符。比如表达式 (a b) * (c - d)根节点是乘号左子树是加号节点挂 a、b右子树是减号节点挂 c、d。对表达式树做后序遍历得到的就是后缀表达式可以直接用栈求值做中序遍历得到的近似是中缀表达式。树的层级天然表达了运算优先级越深的节点越先计算括号的作用只是改变树的形状而树的形状改变又反映在节点位置和层次上。把表达式树理解清楚再回头看后缀表达式求值就不再是死记硬背的知识点。5.4 哈夫曼编码与数据压缩哈夫曼树是一种带权路径长度最短的二叉树常用于构造最优前缀编码。构建过程很朴素把每个待编码字符看成一个节点权重用出现频率每次取出两个权重最小的节点合并成一个新节点直到最后剩下一棵树。从根节点到某个叶子节点的路径上左转记 0右转记 1就得到每个字符的二进制编码。出现越频繁的字符离根越近编码越短所以整体数据量会明显下降。这个算法诞生很多年了至今仍然是不少压缩方案的基础模块。它还展示了“树的路径可以编码信息”这个抽象思路理解它对很多领域都有启发。5.5 层级数据与不需要指针的树除了上面这些二叉树及其变种广泛出现在文档对象模型、抽象语法树、文件系统目录、路由前缀匹配等场景。凡是需要“表达层级”或“二分决策”的地方大概率都有树的身影。有时候我们不需要显式定义节点比如某些后台系统的组织架构数据用父子 id 存在表里查询时再临时组装成树有时候我们又把树当索引用把海量数据组织成可以快速剪枝的结构。所以说树不是一个孤立概念它代表了一种解决问题的通用框架把大问题分小块把层级结构用节点关系表达出来。6. 常见问题与排查技巧实录6.1 递归遍历栈溢出怎么办递归实现二叉树很优雅但代价是每递归一层就占用一段调用栈内存。如果树高度达到几千上万层Python 会直接抛 RecursionError。排查时先看树是不是因为构建逻辑问题变得过深比如 BST 斜树如果业务确实需要处理深树就把递归改成显式栈的迭代版本。前面我已经给了前序和中序的迭代写法后序用“根右左反转”的思路也能应付。我的建议是只要递归版本测试通过、性能在可接受范围内就不急着优化先保证正确性如果确实遇到深树场景再动手改成迭代。6.2 遍历结果和预期不符怎么办最常见翻车原因有三个。第一左右子树接反了。构建树时把 left 和 right 赋值颠倒了遍历结果自然不对。排查方式是画图把树画出来再对着遍历顺序一步步核对。第二递归收集结果的方式有问题。比如想把子树结果加入列表却忘了返回值或者用了全局变量递归前没有清空。第三空节点处理不一致。如果递归函数没有处理 root 为 None 的情况访问 root.val 会直接抛异常。所有遍历递归都建议先在函数最前面处理空节点。还有一个实用技巧打印中间日志。在递归函数入口打印当前节点值和递归深度很快就能看到遍历顺序是在哪个位置断掉的。死盯代码往往不如一句日志来得快。6.3 初学者最容易踩的坑汇总坑点现象建议深度/高度定义不一致代码少算或多算一层写代码前先约定根深度为 0递归返回条件忘写空节点操作抛异常每个递归函数先写 None 判断数组存储斜树空间浪费严重普通二叉树用链式别硬塞数组层序构建数组含 None节点挂接错位手动模拟队列进出过程二叉搜索树插入重复值查找行为不确定先明确是否允许重复及处理规则只背中序遍历结论换棵树就写错多画图亲手推导后序迭代死记模板只会一种写法理解入栈出栈顺序与访问时机经常有人问“有没有一个万能模板解决所有二叉树题”。我的看法是模板是递归框架和遍历骨架具体代码永远要按题改真正要玩熟的是“访问时机”和“节点信息收集方式”。把这两样想透绝大多数二叉树题都能手到擒来。我自己学二叉树时最大的转折点是某天晚上拿纸笔把一棵树的前中后序和层序全部手工走了一遍每一步都标上访问顺序。从那以后递归写起来不慌了面试题里的重建二叉树、层序变体也慢慢变成了送分题。后来带人写项目我总是建议先画图再写代码先想清楚“这一层我要得到什么、传给父节点什么”再动手敲键盘。如果你正被递归和树绕得头晕别急找一棵小树慢慢走一遍亲手体会一次“访问时机决定遍历顺序”比看十篇博客都有用。树这种东西光看是学不会的拿支笔画一画很快就能找到感觉。