1. 树到底是用来干什么的1.1 从数组和链表说起很多人学数据结构的第一站是数组和链表。数组像一排放好的储物柜每个格子有编号你想取第三个格子里的东西一步就能到缺点是中间插个新东西得把后面的全部往后挪。链表像一列火车每节车厢只记住下一节在哪插入删除很灵活但你想找第10节车厢必须从车头一节一节数过去。这两种结构各有利弊但都有一个共同的短板数据量大了以后查找、插入、删除的效率很难兼顾。数组查找快但插入删除慢链表插入删除快但查找慢。有没有一种结构能把两者的优点结合起来树就是答案之一。树这种结构把数据按照分层的方式组织起来。最顶上有一个根节点下面挂着一层一层的子节点就像公司的组织架构、家族的族谱、电脑里的文件夹系统。因为有了层级关系树可以在每一步都排除掉一大半的搜索范围查找效率天然比链表高插入删除也只需要改动局部的几个节点不会像数组那样大面积搬移。1.2 谁需要学树学到什么程度如果你是计算机专业的学生树是考试和面试的常客二叉树的遍历、二叉搜索树、平衡树这些概念躲不开。如果你是转行学编程、准备面试的开发者树更是高频考点——很多经典算法题比如判断一棵树是否平衡、求二叉树的最大深度、验证二叉搜索树都是围绕树展开的。就算你日常工作里很少手写树但数据库的索引、操作系统的文件目录、编译器的语法分析、路由器的路由表底层全是树的影子。这篇文章的目标是让你彻底搞懂树的基础概念和核心操作包括术语、存储方式、遍历方式、插入删除查找以及常见的坑。我会尽量用图示配合代码把每一步为什么这样做讲明白而不是只丢一堆定义让你背。2. 树的术语与基本概念拆解2.1 一张图认识树的基本结构先想象一棵倒过来的树根在最上面树枝往下分叉叶子在最下面。数据结构里的树和自然界的树方向相反根在上、叶子在下但分支层级的本质是一样的。一个典型的树长这样A ← 根节点 / \ B C ← A的子节点 / \ \ D E F ← B的子节点 / C的子节点 / \ G H ← E的子节点这里A是整棵树的根B和C是A的孩子D和E是B的孩子G和H是E的孩子。没有子节点的节点D、F、G、H叫叶子节点。一个节点下面直接连的节点叫它的孩子它自己就是这些孩子的父亲同一层的B和C互称兄弟。2.2 必须吃透的十个核心术语很多初学者看树的代码一头雾水往往是因为术语没搞清。下面这十个术语是必须吃透的底子术语定义类比根节点树的最顶层节点没有父节点公司的CEO子节点某个节点直接连接的下一层节点直属下属父节点某个节点的直接上层节点直接上级兄弟节点同一个父节点下的多个子节点同一个部门里的同事叶子节点没有子节点的节点一线员工子树任意节点和它的所有后代组成的整体一个独立的小部门节点的度节点拥有的子节点个数管着几个人树的度所有节点中最大的度管人最多的那个岗位层数深度从根开始算根是第0层或第1层职级高度从某个节点到最远叶子节点的边数距离一线岗位还有几级这里有一个容易混淆的点深度和高度。深度是从根往下的距离根节点的深度是0有的教材算1高度是从下往上算叶子节点的高度是0。判断一棵树是否平衡时用的就是子树的高度差。注意不同教材对深度从0还是从1开始定义不统一做题和面试时先和对方确认口径否则容易出现差一错误。2.3 树的存储方式链式存储与顺序存储树的实现方式主要有两种链式存储和顺序存储。链式存储最直观每个节点是一个对象里面存数据再加两个或若干个指针指向子节点。以二叉树为例class TreeNode: def __init__(self, val): self.val val self.left None self.right None顺序存储则是用数组来存树核心规律是如果一个节点在数组中的下标是i那么它的左孩子下标是2i1右孩子下标是2i2父节点下标是(i-1)//2。这个规律要求树尽量是完全二叉树下面会讲否则数组中会留大量空位浪费空间。我用一个例子说明两者的差别。假设要存下面这棵小树1 / \ 2 3 / 4链式存储就是四个节点对象互相指来指去干净利落。顺序存储则是[1, 2, 3, 4, None, None, None]4的下标是3它父节点2的下标是(3-1)//21刚好对应。但如果树长得歪歪扭扭比如某个节点只有右孩子没有左孩子数组里就得留空位空间浪费比较严重。我的建议是日常写算法、刷题、写业务代码默认用链式存储简单直接不容易错。只有需要频繁用数组特性比如堆排序、优先级队列的时候才用顺序存储。3. 二叉树最常用的树形态3.1 为什么二叉树是重点严格来说树可以允许一个节点有任意多个子节点比如一个节点下面挂5个孩子也没问题。但实际学习和应用中二叉树是最核心的形态原因有两个第一任何多叉树都能转换成二叉树。转换方法是每个节点只保留第一个孩子作为左子节点其余孩子作为这个左子节点的右链。这个技巧在算法题里偶尔会出现知道有这回事就行。第二二叉树的结构最简单但已经能表达足够复杂的逻辑。二叉搜索树、堆、哈夫曼树、表达式树全部建立在二叉树的基础上。面试中90%的树相关题目都是二叉树把二叉树吃透其他树触类旁通。3.2 满二叉树与完全二叉树这两个概念看起来相似但定义完全不同。满二叉树每一层都铺满了节点不存在空位。如果高度是k那么节点总数是2^(k1)-1根在第0层。完全二叉树除了最后一层其他层都是满的而且最后一层的节点都靠左排列。注意最后一层靠左这个条件很关键。举几个例子满二叉树: 完全二叉树: 不是完全二叉树: 1 1 1 / \ / \ / \ 2 3 2 3 2 3 / \ / \ / \ / / \ \ 4 5 6 7 4 5 6 4 5 6左边这棵树的每层都满了是满二叉树。中间这棵树的第三层有3个节点且靠左排列是完全二叉树。右边这棵树的第三层节点6没有和节点5连续靠左中间跨过了空位所以不是完全二叉树。为什么要区分这两个概念因为完全二叉树正好能用数组紧凑存储而且堆一种特殊的完全二叉树就是靠这个性质实现O(log n)的插入和取最小值操作的。满二叉树则常用于推导一些数学性质比如叶子节点数和总节点数的关系。3.3 二叉搜索树BST的核心规则二叉搜索树是二叉树在有序方向上的延伸规则只有一句话对于任意节点左子树所有节点的值都小于它右子树所有节点的值都大于它。这个规则带来的最大好处是查找效率。在二叉搜索树里找某个值每次比较后要么去左子树要么去右子树搜索范围直接缩小一半。如果树是平衡的查找时间复杂度是O(log n)但如果树退化成一条直线比如按升序插入节点查找就变成了O(n)和链表没区别。我见过很多新手把二叉搜索树当成排序好的数组这是误区。二叉搜索树不要求整体有序只要求局部满足左小右大的规则。中序遍历一棵二叉搜索树时输出的序列才是严格递增的这算是一个重要的性质。提示判断一棵树是不是二叉搜索树不能只比较每个节点和它的左右孩子还要保证整个左子树都小于当前节点、整个右子树都大于当前节点。很多新手栽在这个细节上后面我会专门讲。4. 树的遍历四种方式一次讲透4.1 前序遍历根 → 左 → 右遍历是树最基础的操作也是后面所有高级操作的前提。遍历分两种大方向深度优先DFS和广度优先BFS。深度优先又分前序、中序、后序三种。前序遍历的顺序是先访问根节点再遍历左子树最后遍历右子树。看这棵示例树1 / \ 2 3 / \ 4 5前序遍历的结果是1, 2, 4, 5, 3。过程是先输出1然后进入左子树输出2再进入2的左子树输出4回退进入2的右子树输出5回退到根进入右子树输出3。前序遍历的特点是先处理当前节点再往下钻适合用在复制树、序列化树的场景——因为先访问根重建的时候可以先建根再建子树。4.2 中序遍历左 → 根 → 右中序遍历的顺序是先遍历左子树再访问根节点最后遍历右子树。同样以上面的树为例结果是4, 2, 5, 1, 3。中序遍历最经典的应用就是二叉搜索树。因为二叉搜索树满足左小右大中序遍历会得到一个有序序列所以判断一棵树是否是二叉搜索树最直接的方法就是中序遍历后看结果是否递增。中序遍历的过程可以用一句话概括先一路往左走到底输出回退一格输出再往右走一步接着一路往左。很多递归代码看不懂就是因为没在脑子里模拟这个过程建议自己拿纸画一棵树把每一步的输出写在节点旁边走个两三遍就通了。4.3 后序遍历左 → 右 → 根后序遍历的顺序是先遍历左子树再遍历右子树最后访问根节点。示例树的结果是4, 5, 2, 3, 1。后序遍历的特点是先处理孩子再处理自己这个特性非常适合做树的删除和统计。比如删除一棵树你得先删光所有孩子再删根否则根删了孩子就找不到了。计算一棵树的高度也是一样先算左子树高度和右子树高度取最大值加1就是当前节点的高度——典型的后序遍历逻辑。4.4 层序遍历从上到下、从左到右前面三种都是深度优先沿着一条路走到黑再回退。层序遍历不一样它一层一层从上往下扫也就是广度优先。示例树的层序遍历结果是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 result4.5 递归与迭代的实现对比树的遍历实现方式有两种递归和迭代。递归版本代码极短逻辑清晰但需要注意栈溢出的风险——如果树的高度非常大比如几万层递归会不断压调用栈导致程序崩溃。迭代版本用显式的栈或队列来控制代码稍微长一点但不会有调用栈溢出的问题。前序遍历的递归版本def preorder(root): if not root: return print(root.val) preorder(root.left) preorder(root.right)前序遍历的迭代版本用栈def preorder_iter(root): if not root: return stack [root] while stack: node stack.pop() print(node.val) # 注意先压右孩子再压左孩子 if node.right: stack.append(node.right) if node.left: stack.append(node.left)这里为什么要先压右孩子再压左孩子因为栈是后进先出先压进去的会最后被处理。我们要先访问左子树就要让左孩子后进栈、先出栈。这个细节很多新手反过来写结果遍历顺序就错了。我个人建议初学阶段先把递归吃透因为递归版本和树的递归定义天然匹配。等递归写熟了再练习迭代版本面试时两种都要能写出来。5. 核心操作实战插入、删除、查找5.1 插入操作与平衡问题以二叉搜索树为例插入操作的规则是从根节点开始如果要插入的值比当前节点小往左走比当前节点大往右走直到找到一个空位置把新节点放进去。def insert(root, val): if not root: return TreeNode(val) if val root.val: root.left insert(root.left, val) else: root.right insert(root.right, val) return root这段代码的返回值是插入完成后的子树根节点因为插入可能在左子树也可能在右子树改完之后必须把新子树挂回原来的位置。很多新手漏掉最后一行return root导致整棵树被改坏。插入操作的时间复杂度取决于树的形状。理想情况下是O(log n)但如果你一直按顺序插入比如插入1, 2, 3, 4, 5树会变成一条向右延伸的链插入就退化成了O(n)。这就是为什么要引入平衡二叉树AVL树、红黑树——它们会在插入后自动调整结构保证树的高度始终是O(log n)。写插入代码时的自查方法插入完成后对树做一次中序遍历如果输出序列是递增的说明插入逻辑基本正确。5.2 删除操作的三类情况删除节点比插入复杂得多核心在于删掉一个节点后如何保持二叉搜索树的性质。删除分三种情况第一种删除叶子节点。最简单直接让父节点对应的指针指向空即可。第二种删除只有一个子节点的节点。让这个节点的子节点顶替它的位置相当于隔代继承。第三种删除有两个子节点的节点。不能直接删需要找一个替身来顶替。通常的做法是找到右子树中最小的节点或者左子树中最大的节点把这个节点的值复制到当前节点然后递归地删除那个最小节点。为什么要找右子树最小节点因为它比当前节点的所有左子树都大又比右子树中其他节点都小顶替上来不会破坏二叉搜索树的性质。def delete(root, val): if not root: return None if val root.val: root.left delete(root.left, val) elif val root.val: root.right delete(root.right, val) else: # 情况1叶子节点 if not root.left and not root.right: return None # 情况2只有一个子节点 if not root.left: return root.right if not root.right: return root.left # 情况3有两个子节点 # 找到右子树的最小节点 min_node root.right while min_node.left: min_node min_node.left root.val min_node.val root.right delete(root.right, min_node.val) return root注意删除操作里最容易踩的坑是忘掉return。递归删除本质上是在返回一棵改好的子树每一层都必须把返回值接住否则父节点指向的还是旧节点删除等于白做。第三种情况有个替代方案用左子树的最大节点做替身。两种方案都能成立选哪个看个人习惯但要注意替身不能是当前节点自己而且要递归删除替身原来所在的位置否则会出现重复值。5.3 查找操作与时间复杂度分析查找的逻辑和插入很像只是不需要改结构def search(root, val): if not root or root.val val: return root if val root.val: return search(root.left, val) return search(root.right, val)查找的时间复杂度平衡的二叉搜索树是O(log n)退化的链式树是O(n)。对比一下数组查找O(n)如果无序、链表查找O(n)、哈希表查找O(1)。那为什么还要用树因为哈希表只能做等值查找没办法高效地做范围查找比如找出所有大于10且小于20的值。二叉搜索树在范围查找上有天然优势定位到边界节点后中序遍历就能把范围内的值全部输出。一个很常见的面试题是求第k小的元素。思路就是利用中序遍历的有序性遍历到第k个节点直接返回。如果树经常被修改还可以在每个节点维护一个子树节点数字段做到O(log n)查找第k小这就是顺序统计树的思路。6. 树的扩展形态与真实应用场景6.1 平衡二叉树AVL与红黑树普通二叉搜索树有个致命弱点输入顺序不好时性能会退化。平衡二叉树就是为了解决这个问题。AVL树严格保证任意节点的左右子树高度差不超过1插入或删除后如果失衡通过旋转左旋、右旋、左右旋、右左旋来恢复平衡。红黑树更复杂一些它不追求严格平衡而是通过节点颜色和几条约束规则保证最长路径不超过最短路径的两倍。这个弱平衡的特性让红黑树在插入删除时旋转次数更少实际性能往往更好。Java语言的基础库里的有序映射、有序集合底层用的就是红黑树。我在实际项目中很少需要手写AVL或红黑树但理解它们的原理很重要——知道平衡是怎么来的能帮你在系统设计里正确地选择数据结构。6.2 堆、哈夫曼树与文件系统堆是一种特殊的完全二叉树分为大顶堆和小顶堆。大顶堆的每个节点都大于等于它的子节点所以堆顶永远是最大值。堆用数组存储插入和删除堆顶都是O(log n)初始化建堆是O(n)。堆排序、优先级队列比如任务调度系统按优先级处理任务、Top K问题全靠它。哈夫曼树是带权路径长度最短的树核心用途是数据压缩。构造方法是把每个字符的出现频率作为权值每次取两个最小的节点合并成一个新节点重复直到只剩一棵树。出现频率越高的字符在哈夫曼树中的路径越短编码也就越短。文件系统也是典型的树结构。一个根目录下面挂着多个子目录每个子目录又能继续往下挂形成了无限层级的树。你在终端里敲cd /home/user/docs本质就是在树里从根节点走一条路径到目标节点。6.3 树在数据库与搜索引擎中的应用数据库索引大量使用B树和B树。B树是多叉平衡树一个节点可以存多个关键字和多个子节点指针这样能显著降低树的高度减少磁盘IO次数。B树在B树基础上做了改进所有数据都存储在叶子节点叶子节点之间用指针串成链表范围查询和遍历特别方便。这就是为什么关系型数据库的索引底层普遍采用B树。搜索引擎里的倒排索引虽然本身不是树但构建和查询过程中大量用到树的结构来组织词项。语法分析器解析代码时会把源代码解析成抽象语法树AST每一层代表一种语法结构。编译器对这个树进行遍历、优化最后生成机器码。可以说只要涉及层级关系或者快速查找有序数据树几乎都是绕不开的选项。7. 常见问题与调试经验实录7.1 递归导致栈溢出我调过一棵深度极大的树递归遍历直接报栈溢出。原因很简单递归每深入一层就占用一层调用栈树有几万层调用栈就被压爆了。解决办法有两个方向一是改写成迭代版本用显式的栈来模拟递归二是限制递归深度。写生产代码时如果树的深度不可控优先考虑迭代。7.2 空指针与边界条件树的代码中空指针错误排第一。最常见的是访问node.left或node.right时没检查节点是否为None。比如计算树的高度如果你直接访问空节点的孩子程序必然崩溃。我的习惯是所有涉及树的递归函数第一行就写空判断def height(root): if not root: return 0 return 1 max(height(root.left), height(root.right))另一个容易漏的边界是树本身为空时函数能否正确处理。比如中序遍历空树应该返回空列表而不是报错。刷题时建议养成一个条件反射——先把空树的测试用例跑一遍。7.3 遍历顺序混淆前序、中序、后序的名字描述的是根节点的位置根在前 → 前序根在中 → 中序根在后 → 后序左右子树的相对顺序永远都是左先右后变的只是根节点的访问时机。把握住这条规律写代码时就不会乱。还有一个常见混淆点给定前序中序可以唯一确定一棵二叉树给定后序中序也可以唯一确定但只给前序后序不行。原因在于前序和后序都只体现了树的边界信息无法区分左右子树的分界点。这个结论面试偶尔会问记住即可。7.4 我的几点实操建议第一学树一定要画图。我见过太多人盯着代码硬想效果很差。随便拿张纸画一棵五六个节点的树手动模拟遍历过程把每一步的访问顺序写下来再和代码输出的结果比对几轮下来就有手感了。第二调试树相关的代码最有效的办法是可视化打印。写一个把树横向打印成文本的小工具或者用调试器观察每个节点的左右孩子别靠脑补。我在本地就常备一个打印树的工具函数虽然丑了点但排查问题特别快。第三刷题顺序建议这样走先练四种遍历的递归和迭代写法再练求深度/高度、判断对称、判断二叉搜索树最后再碰删除节点、最近公共祖先这类综合题。每道题做完用手画几组不同的测试用例验证不要只跑示例数据。说实话树这个知识点刚开始接触会觉得抽象但它是理解后面所有复杂数据结构的基石——堆、并查集、线段树、B树都是从树的基本概念生长出来的。我在实际工作中用树的频率远高于其他数据结构光是文件目录的递归遍历、权限树的判断、多级分类的组装就够我把这套东西反复实践了。把这篇文章里的基础吃透后面再遇到平衡树、红黑树、B树这些进阶内容你会发现它们不过是二叉树加上了一些额外的规则而已。