1. 树为什么值得被单独拿出来反复讲几年前我第一次在代码里接触树的时候第一反应是这不就是带指针的结构体吗数组、链表都还没整明白为什么还要搞一个分支结构出来后来真正在项目里处理文件目录、解析表达式、做搜索建议的时候才意识到一个问题——线性数据结构表达不了层级关系。你想想文件系统里一个文件夹套着另一个文件夹公司的组织架构里一个部门下面挂好几个小组语法分析里一个表达式嵌套另一个表达式。这些东西用数组怎么存用链表怎么存硬存是可以但你翻找某个子节点的时候得从头遍历到尾效率直线下滑代码写起来也别扭。树结构的价值恰恰在这里它用天然的嵌套方式模拟现实世界的层级关系并且让查找、插入、删除这些操作有了明确的路径可走而不是靠暴力遍历。后来我做那个模拟项目X的权限模块用户角色、菜单、按钮三级权限全部用树形数据来组织前端渲染左侧菜单直接递归遍历 tree后端的权限判断也顺着树链往上找父级整个系统的逻辑一下就顺了。所以这篇文章不是什么面试八股文而是把树这个结构从头到尾拆开揉碎从最基础的名词定义到二叉树的分类再到遍历的递归与非递归写法最后落到二叉搜索树和实际工程场景。不管你是刚开始学数据结构的同学还是写了两年代码想回头补基础的同学我尽量用大白话把每个概念讲清楚代码也直接给出可运行的版本看完你就能自己上手。2. 先把节点、边这些名词钉死再往上看结构树的定义听起来很绕树是 n 个节点的有限集合n0 时叫空树n0 时只有一个根节点其余节点分成 m 个互不相交的有限集合每个集合又是一棵树。其实翻译成人话就是——一个根节点往下长出一堆子树子树里再长出子树层层嵌套。2.1 节点、根、叶子树的人话版骨架每次讲树我习惯先画一个最朴素的图A / \ B C / \ \ D E F把这个图里的角色认全后面所有定义都不难理解根节点整棵树最顶上的那个节点这里就是 A。根节点没有父节点是一棵树的入口。父节点与子节点A 下面连着 B 和 CA 就是 B、C 的父节点B、C 就是 A 的子节点。叶子节点没有子节点的节点比如 D、E、F它们是这棵树最末端的位置。兄弟节点同一个父节点下的几个节点B 和 C 就是兄弟关系。子树任何一个节点连同它下面的所有后代整体构成一棵子树。比如 B 加上 D、E 就是一个子树C 加上 F 也是。节点的度一个节点拥有的子节点个数。B 的度是 2C 的度是 1D 的度是 0。整棵树的度指的是所有节点中最大的那个度。树的深度与节点的高度这两个词最容易搞混。深度是从根节点往下数的层数根节点深度为 0也有教材从 1 开始考试时先看题目约定高度是从叶子节点往上数的层数叶子高度为 0。我习惯的记忆方式是深度是从上往下挖了多深高度是从底下往上垒了多高。2.2 路径、层次和有向边的理解树里还有个概念叫路径指的是从某个节点到另一个节点所经过的节点序列。比如从 A 到 E路径就是 A - B - E路径长度是经过的边数也就是 2。这里值得单独拎出来说的一点是树是一种有向无环结构。每条边都有明确的方向只能从父节点指向子节点不能反向更不能形成循环。你要是画出 A - B - E 然后又从 E 指回 A那就不叫树了变成了图。很多初学者画着画着就多出一条线然后就问为什么这不是树——因为它违反了每个节点只有一个父节点这个铁律。树的层次也很直观根节点在第 0 层它的直接子节点在第 1 层以此类推。这个层在做层序遍历、计算树的宽度时会经常用到。2.3 树的存储方式左孩子右兄弟与链式存储理论概念清楚了工程上还得解决怎么存的问题。最常用的有三种双亲表示法每个节点记住自己的父节点是谁用数组就行。这种办法找父节点非常快但找子节点得遍历全表。孩子表示法每个节点用一个链表挂它的所有子节点。找子节点方便找父节点又变麻烦了。左孩子右兄弟表示法每个节点固定两个指针一个指向它的第一个孩子一个指向它的下一个兄弟。这个办法巧妙地把一棵多叉树转成二叉树来存很多底层库爱用这种。实际操作里最常用的还是孩子表示法 数组的组合。比如前端拿到的菜单树、部门树基本就是 JSON 数组每个元素里有id、parentId、children字段这就是孩子在内存里的自然表示。3. 二叉树的几副面孔满二叉树、完全二叉树与退化树聊完通用树接下来这颗星球上最出名的树就是二叉树了。二叉树就是每个节点最多只有两个子节点的树左右是有顺序的左边孩子和右边孩子调换位置就是两棵不同的树。3.1 满二叉树与完全二叉树别再靠看起来满不满判断先看两棵树的示意图满二叉树 1 / \ 2 3 / \ / \ 4 5 6 7 完全二叉树 1 / \ 2 3 / \ / 4 5 6满二叉树除叶子节点外每个节点都有左右两个孩子而且所有叶子都在同一层。也就是说整棵树是一个萝卜一个坑地填满了节点总数是 2 的 k 次方减 1k 是高度。上图第一棵高度为 3节点数 7符合公式。完全二叉树稍微宽松一点只有最后一层的叶子可能没填满而且这些叶子必须从左到右连续排列中间不能有空缺。第二棵图的 6 号节点有左孩子但最后一层最右边缺了一个位置它是完全二叉树。但如果第二棵树的 6 号节点右侧出现了 7 号而 5 号位置空缺那就不完整了因为从左到右不连续。为什么要死磕完全二叉树因为它可以用数组完美存储。从上到下、从左到右按下标顺序排进数组任意节点的父节点是(i-1)/2左孩子是2i1右孩子是2i2不需要任何指针纯靠下标计算就能跳转。堆这个数据结构就是建立在这个特性上的。3.2 退化二叉树看着像链表的东西还有一种极端情况叫退化二叉树每个节点只有一个孩子一直往一侧长形状基本就是一条直线比如 1 - 2 - 3 - 4。这种结构来自树的名分但遍历起来的时间复杂度和链表没有任何区别。后面讲二叉搜索树的时候会专门说为什么这种情况让人头疼。3.3 二叉树的节点数、边数的几个常用结论做题的时候有几个小结论可以直接用省得反复推导二叉树第 i 层最多有 2^i 个节点根节点算第 0 层。高度为 k 的二叉树最多有 2^(k1) - 1 个节点。叶子节点数 n0 和度为 2 的节点数 n2 满足n0 n2 1。最后一个结论很有用。假设一棵二叉树有 5 个度为 2 的节点那叶子节点一定是 6 个。记住这个关系很多选择题一秒钟就能出答案。4. 遍历到底怎么走先中后层四种方式全拆解树的遍历是基础中的基础也是后面所有树算法求深度、序列化、树的构建的前提。我的建议是先理解递归写法再去抠非递归写法别一开始就把自己绕晕。4.1 前序、中序、后序遍历递归版本还是用这棵树做例子A / \ B C / \ \ D E F三种深度优先遍历的定义就一句话前序遍历先访问根节点再遍历左子树最后遍历右子树。中序遍历先遍历左子树再访问根节点最后遍历右子树。后序遍历先遍历左子树再遍历右子树最后访问根节点。递归代码非常短下面是 Python 版本可以用上面这棵树直接跑class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def preorder(root): if not root: return print(root.val, end ) preorder(root.left) preorder(root.right) def inorder(root): if not root: return inorder(root.left) print(root.val, end ) inorder(root.right) def postorder(root): if not root: return postorder(root.left) postorder(root.right) print(root.val, end )跑一下这棵树的输出前序A B D E C F中序D B E A C F后序D E B F C A记忆技巧我自创了一个根在哪就叫什么序。根在前就是前序根在中间就是中序根在最后就是后序。遍历左子树的顺序永远在右子树之前这个不变。4.2 层序遍历用队列宽度优先横扫层序遍历就像给树拍照一层一层从左到右扫过去输出 A B C D E F。它不用递归天然适合用队列实现from collections import deque def level_order(root): if not root: return queue deque([root]) while queue: node queue.popleft() print(node.val, end ) if node.left: queue.append(node.left) if node.right: queue.append(node.right)这里有个很容易犯的错误把 queue 写成了栈。如果每次从尾部取节点而不是头部就变成了深度优先输出顺序会乱掉。用deque的时候记住popleft才代表出队别顺手写pop()。4.3 非递归遍历为什么要会以及怎么写面试和实际工作中递归写法虽然清晰但递归调用深度一上来可能把调用栈撑爆。这时候就得靠显式栈来做非递归遍历。前序非递归最好理解用一个栈先压根节点然后循环弹栈、访问、先压右孩子再压左孩子因为栈是后进先出先压右孩子才能保证左孩子先被弹出访问。def preorder_iter(root): if not root: 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 stack or cur: while cur: stack.append(cur) cur cur.left cur stack.pop() print(cur.val, end ) cur cur.right后序非递归的方案比较多我目前比较推荐双栈或者标记法。标记法的思路是在节点入栈时同时记录是否已访问过子树如果左右都已处理完就弹出访问否则先把右子树、左子树入栈。代码略长但逻辑很统一不会像先序倒序那种技巧一紧张就写岔。5. 二叉搜索树让树从存储结构变成查找结构前面讲了树的形状和遍历但光会走一遍不算真本事。二叉搜索树Binary Search Tree缩写 BST才是把树变成实用数据结构的第一个关键形态。5.1 BST 的三个铁律BST 的定义很简单对于每个节点左子树里所有节点的值都小于它右子树里所有节点的值都大于它而且左右子树本身也必须是 BST。注意是所有节点不是直接孩子。5 的左子树里有 1 和 3都必须小于 5右子树里有 8 和 10都必须大于 5。如果只和直接孩子比较很容易在深层节点那里翻车。5.2 BST 的查找最多走树的高度BST 的查找思路就是二分查找的树形版。从根节点开始比目标值大就走向左子树比目标值小就走向右子树相等就返回。def search_bst(root, target): cur root while cur: if cur.val target: return True elif target cur.val: cur cur.left else: cur cur.right return False这个操作的时间复杂度是 O(h)h 是树的高度。平衡状态下 h 约等于 log n查找一万个节点的树只需要十几次比较这才是 BST 的价值所在。5.3 BST 的插入找到空位挂上去插入操作更直观从根出发按查找的路径往下走遇到空位就放进去。关键是要维护父节点不能丢指针。def insert_bst(root, val): if not root: return TreeNode(val) cur root while True: if val cur.val: if cur.left is None: cur.left TreeNode(val) break cur cur.left else: if cur.right is None: cur.right TreeNode(val) break cur cur.right return root5.4 BST 的删除三种情况第三种最容易出错删除节点比插入麻烦一点因为要保持 BST 性质。会遇到三种情况叶子节点直接删掉让父节点对应的指针变成 None。只有一个孩子用这个孩子顶替被删节点位置。有两个孩子这时候不能直接删。标准做法是找被删节点的中序后继右子树里最小的节点或者中序前驱左子树里最大的节点用它替代被删节点然后再删掉那个被移动的节点。我当初写这个逻辑的时候最常犯的错误是没有保存待删除节点的父节点导致删完后原树断了。后来习惯用递归返回值来重建连接代码会稳很多def delete_bst(root, val): if not root: return None if val root.val: root.left delete_bst(root.left, val) elif val root.val: root.right delete_bst(root.right, val) else: if not root.left and not root.right: return None if not root.left: return root.right if not root.right: return root.left # 找右子树最小节点 min_node root.right while min_node.left: min_node min_node.left root.val min_node.val root.right delete_bst(root.right, min_node.val) return root这段代码的巧妙之处在于返回值直接覆盖父节点的指针省去了手动维护 parent 的麻烦。递归在树这种本身就是递归定义的结构上写起来确实比迭代舒服。5.5 退化问题BST 是怎么变成链表的BST 本身不保证平衡。如果你按升序插入 1、2、3、4、5它会变成一条斜线查找最后一个元素需要从头一路走到尾复杂度退化成 O(n)。这就是开头提过的退化二叉树。解决这个问题的思路就是让树在插入、删除后自动调整形状保持左右子树高度差不越过阈值于是有了 AVL 树、红黑树这些平衡树。工程上 JDK 的 TreeMap、C 的 map 默认用的是红黑树数据库索引用的则是 B 树。它们都是 BST 的进阶变体核心思想没变只是多了旋转这套自我调节的动作。6. 树在真实项目里怎么落地以及几个容易踩的坑聊完理论说点实际操作中会遇到的东西。很多人学完树做题全会但一回到业务代码就懵了不知道为什么奢时候该用树。我拿自己做过的项目和接触过的开源库给你梳理几个典型的应用场景再分享几个新手常踩的坑。6.1 树在工程里的几大典型去向文件目录与菜单系统操作系统文件树、前端侧边栏菜单、后台权限目录全是树形数据。前端拿到扁平列表后经常要先把它转成嵌套 children 结构再渲染。这个转换逻辑值得自己手写一遍理解了父与子的关系工作中会用得很熟练。表达式解析与编译器1 2 * 3这个表达式可以表示成语法树根是 左孩子是 1右孩子是一个 * 节点两个子节点分别是 2 和 3。编译器要做运算优化、生成中间代码全靠遍历这棵树。堆与优先队列堆就是完全二叉树的一种应用用数组存储常用于实现优先队列、Top K 问题、定时任务调度。决策树与机器学习决策树模型本质上就是一棵树。每个节点是一个特征判断条件叶子是分类结果。虽然训练过程比这复杂得多但推断的时候就是一次从根到叶子的遍历。数据库索引B 树是多路搜索树把大量索引项组织在有限高度里保证磁盘读取次数可控。6.2 自己动手把扁平菜单列表转成树形结构这是前端面试和实际业务里都超级常见的一道题。输入是一个扁平数组menus [ {id: 1, parent_id: None, name: 系统管理}, {id: 2, parent_id: 1, name: 用户管理}, {id: 3, parent_id: 1, name: 角色管理}, {id: 4, parent_id: 2, name: 新增用户}, ]目标是把它们变成嵌套结构。最直接的做法是两层循环外层找根节点内层挂子节点。更好一点的做法是用一个哈希表先遍历一次把所有节点按 id 存好再遍历一次把每个节点挂到父节点的 children 上def build_tree(menus): nodes {item[id]: {**item, children: []} for item in menus} root [] for item in menus: node nodes[item[id]] parent_id item[parent_id] if parent_id is None or parent_id not in nodes: root.append(node) else: nodes[parent_id][children].append(node) return root这段代码里面有个很多教程不讲的细节节点必须存引用不能拷贝。如果你在挂子节点时用copy()复制了一份数据后续对子节点的修改不会同步到父节点的 children 里渲染出来永远是空。6.3 树的序列化与反序列化调试和传输的好帮手实际调试的时候光打印节点值看不出整棵树的形状。我经常写一个简单的层序序列化函数把树转成带null的列表一眼就能看出结构def serialize(root): if not root: return [] result [] queue deque([root]) while queue: node queue.popleft() if node: result.append(node.val) queue.append(node.left) queue.append(node.right) else: result.append(None) while result and result[-1] is None: result.pop() return result序列化之后的数据既方便打印观察也能传到前端做展示甚至可以作为测试用例的输入格式。6.4 递归深度不得不防的栈溢出树的递归代码好看但也最容易在深度大时出问题。我曾遇到过一次生产环境报RecursionError排查半天才发现是某条数据链路过深用户权限嵌套了几百层直接把 Python 默认的递归限制打爆了。遇到这种情况有几个应对办法提前设大递归深度sys.setrecursionlimit(10000)这是临时方案治标不治本。改用迭代遍历或显式栈把递归消耗的调用栈搬到堆上。在构建树之前先做深度校验超过阈值就走平铺结构或者改用其他方案。我在实际项目中偏向于先校验再递归。尤其是处理不可控的外部数据时深度和环都要检查否则递归不仅可能溢出还可能死循环。6.5 判断二叉树是否对称递归思维的经典练兵最后给大家一个很能检验递归有没有真懂的题目判断一棵二叉树是否轴对称。思路是把左右子树拆开对比左节点的左子树对应右节点的右子树左节点的右子树对应右节点的左子树。代码写出来很简短def is_symmetric(root): def mirror(left, right): if not left and not right: return True if not left or not right: return False return (left.val right.val and mirror(left.left, right.right) and mirror(left.right, right.left)) return mirror(root.left, root.right) if root else True这道题我之所以想拎出来讲是因为它帮你把树的递归到底怎么传参数这个卡点解决了——对称不是比较同一个节点的左右孩子而是交叉比较。理解了这个后面遇到合并二叉树翻转二叉树这些题目思路都会顺畅很多。7. 从树的定义到实操我的几个总结性体会写到这里树的基础概念、操作方法、实际应用都过了一遍。最后说几个我自己反复体会到的点希望能帮你少走一点弯路。第一学树一定要先学会画图。哪怕是简笔画把节点和指针画出来遍历顺序就不会错。我在纸上画一遍前序和中序比盯着代码看半小时有效得多。树的很多题本质上就是看图说话。第二递归不熟不要急先用最小的树推演。比如只有一个根节点、根节点左右各一个孩子三步就能把递归展开看明白。等你熟练了再去看非递归写法会突然理解为什么栈里要先压右再压左。第三不要只背代码要理解遍历的时机。前序是进节点就打印中序是左子树回来再打印后序是左右都回来了再打印。这套时机逻辑贯穿了几乎所有的树形算法比如求树的深度用后序重建二叉树用前序加中序序列化用层序各有各的适配场景。树这个结构确实值得沉下心好好啃。它不是靠死记硬背能会的知识点而是需要你在纸上画、在代码里跑、在错误中试。等你真正用树解决过一两个实际问题比如把一个混乱的目录结构梳理清楚、把权限树正确渲染出来那种原来如此的感觉比看十篇教程都管用。