maths-cs-ai-compendium 树结构深度指南二叉树遍历、BST、Trie、Union-Find 与 Fenwick 树实战【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium树Tree是文件系统、数据库索引、编译器与浏览器背后的层级数据结构也是算法面试中出现频率最高的主题之一。本文以 maths-cs-ai-compendium 第 14 章「数据结构与算法」中的 树结构章节 为核心系统讲解二叉树的四种遍历、二叉搜索树BST、前缀树Trie、并查集Union-Find以及线段树 / Fenwick 树的原理与完整可运行的 Python 实现并结合仓库内离散数学、图论、操作系统、机器学习等章节的交叉证据帮你建立起「递归三件套 模式识别」的树问题解题能力。读完本文你将能够徒手实现所有树类核心数据结构并独立解决从 Easy 到 Hard 的典型树问题。树的本质递归结构决定递归解法在进入代码之前先明确树的数学定义。仓库 第 13 章 · 离散数学 中给出树是连通且无环的图等价地它有 $n$ 个节点和 $n-1$ 条边有根树指定一个根节点其余每个节点有且只有一个父节点生成树包含图的所有节点而最小生成树MST在 图论章节 中被进一步探讨Kruskal 算法正是通过并查集实现的后文详述。树最重要的变体是二叉树每个节点至多有两个孩子左孩子和右孩子。树的递归定义——「一棵树是一个根节点加两棵子树」——决定了解决树问题的核心心法大多数树问题都可以递归求解。掌握「先解左子树、再解右子树、最后合并结果」的模式就能解决绝大多数树问题。这个模式与 第 14 章基础篇 中强调的递归三要素完全一致基准情形base case空树返回、递归情形把问题分解为更小的子树、信任递归trust the recursion假设递归调用已返回正确答案只需处理合并逻辑。文中反复出现的if not root: return ...就是树递归的基准情形。树在现实世界中无处不在仓库各章节均有佐证领域树的角色仓库出处编译器语法分析树parse tree第 13 章 · 编译流水线浏览器DOM 树第 13 章离散数学树定义机器学习决策树、随机森林第 6 章 · 经典机器学习操作系统CFS 调度器的红黑树、Btrfs/ZFS 的 B 树第 13 章 · 操作系统数据库索引使用的 B 树同上二叉树的四种遍历访问每个节点的标准方式有四种中序遍历 Inorder左、根、右对 BST 而言按升序访问所有节点前序遍历 Preorder根、左、右适用于序列化serialisation与树的复制后序遍历 Postorder左、右、根适用于删除节点与计算子树大小层序遍历 Level-orderBFS借助队列逐层访问。四种遍历的递归/迭代实现如下完整代码继承自原文档并可直接运行class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val] from collections import deque def level_order(root): if not root: return [] result, queue [], deque([root]) while queue: level [] for _ in range(len(queue)): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result关键陷阱递归遍历的 $O(n^2)$ 问题。上面三个递归版本在每一步都用拼接新列表而 Python 的列表拼接会复制两个列表的内容总代价为 $O(1 2 \cdots n) O(n^2)$。这与 基础篇 中「字符串拼接s c是 $O(n^2)$」是同一个隐藏代价问题。高效做法是传入共享的结果列表、原地 appenddef inorder_efficient(root, resultNone): if result is None: result [] if root: inorder_efficient(root.left, result) result.append(root.val) inorder_efficient(root.right, result) return result注意resultNone的写法——不要用def f(root, result[])这种可变默认参数它会让所有调用共享同一个缓存列表基础篇的 DP 陷阱表同样点名了这个错误。层序遍历的要点for _ in range(len(queue))在进入循环时快照当前层的大小保证每次迭代处理恰好一层这是 BFS 分层的标准技巧与 图论章节的 BFS 模板 中「入队时标记 visited」的原则相辅相成。递归模式的经典演练Easy · 二叉树最大深度def max_depth(root): if not root: return 0 return 1 max(max_depth(root.left), max_depth(root.right))递归模式基准情形空树 → 0→ 递归孩子 → 合并1 max。这个「base case recurse on children combine」的模板适用于几十道树问题树的高度计算与 基础篇 中height(root)的例子完全同构。Easy · 翻转二叉树def invert_tree(root): if not root: return None root.left, root.right invert_tree(root.right), invert_tree(root.left) return rootMedium · 最近公共祖先Lowest Common Ancestor问题找到同时是 $p$ 和 $q$ 祖先的最深节点。模式若 $p$、$q$ 都在左子树则 LCA 在左子树若都在右子树则在右子树若分居两侧一左一右当前节点就是 LCA。def lowest_common_ancestor(root, p, q): if not root or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root # p and q are in different subtrees return left if left else right陷阱该解法假设 $p$ 和 $q$ 都存在于树中。若它们可能不存在需要在回溯时额外标记「是否真的找到了两个节点」否则会返回假阳性。Hard · 二叉树最大路径和问题求任意两个节点之间的最大路径和路径不要求经过根。def max_path_sum(root): best [float(-inf)] def dfs(node): if not node: return 0 left max(dfs(node.left), 0) # ignore negative paths right max(dfs(node.right), 0) # path through this node (possibly as the bend) best[0] max(best[0], node.val left right) # return the max gain this node can contribute to its parent return node.val max(left, right) dfs(root) return best[0]核心洞察在每个节点要区分两个问题(1) 经过该节点的最佳路径left node right路径在此处「拐弯」(2) 该节点能贡献给父节点的最佳路径node max(left, right)因为一条路径不能分叉两层。混淆这两个量是最常见的错误。这里的dfs返回值与best全局最优解分离的设计是「后序自底向上 全局变量」的经典组合注意best [float(-inf)]用列表包装是为了在闭包内可写。二叉搜索树BSTBST 的性质对每个节点左子树所有值都更小右子树所有值都更大。平衡时搜索、插入、删除均为 $O(\log n)$。def search_bst(root, target): if not root: return None if target root.val: return search_bst(root.left, target) elif target root.val: return search_bst(root.right, target) else: return root def insert_bst(root, val): if not root: return TreeNode(val) if val root.val: root.left insert_bst(root.left, val) else: root.right insert_bst(root.right, val) return root陷阱BST 的 $O(\log n)$ 只在平衡时成立。按有序序列插入会退化成链表每次操作变为 $O(n)$。这正是 AVL 树、红黑树等平衡 BST存在的原因。仓库 操作系统章节 给出了教科书外的真实案例Linux 的CFS 调度器维护一棵红黑树按虚拟运行时间排序的平衡二叉搜索树每次调度决策 $O(\log n)$同一章节 还指出 Btrfs/ZFS 与数据库索引使用B 树平衡搜索树族这些正是「平衡性」在工业界的直接体现。Medium · 验证二叉搜索树def is_valid_bst(root, lofloat(-inf), hifloat(inf)): if not root: return True if root.val lo or root.val hi: return False return (is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi))陷阱只检查left.val root.val right.val是错的。约束是左子树所有节点都更小而非仅直接孩子。lo/hi边界把约束沿路径向下传播——这是「边界传播」模式的典型应用初值float(-inf)/float(inf)代表根节点无约束。Medium · BST 中第 K 小的元素模式BST 的中序遍历按升序访问节点第 $k$ 个被访问到的节点就是答案。def kth_smallest(root, k): count [0] result [None] def inorder(node): if not node or result[0] is not None: return inorder(node.left) count[0] 1 if count[0] k: result[0] node.val return inorder(node.right) inorder(root) return result[0]优化点result[0] is not None提前剪枝找到第 $k$ 小后不再遍历剩余节点用count [0]与result [None]列表包装是为了在闭包中修改变量Python 闭包对不可变变量只能读不能写。若需要频繁查询第 $k$ 小可改用[线段树/平衡树 节点计数]的增强版 BST见后文。前缀树TrieTrie字典树逐字符把字符串存储在树中每条边代表一个字符从根到标记节点的路径代表存储的字符串。Trie 的查找复杂度为 $O(L)$$L$ 为字符串长度与存储的字符串数量无关。class TrieNode: def __init__(self): self.children {} self.is_end False class Trie: def __init__(self): self.root TrieNode() def insert(self, word): node self.root for char in word: if char not in node.children: node.children[char] TrieNode() node node.children[char] node.is_end True def search(self, word): node self.root for char in word: if char not in node.children: return False node node.children[char] return node.is_end def starts_with(self, prefix): node self.root for char in prefix: if char not in node.children: return False node node.children[char] return True适用场景自动补全autocomplete、拼写检查、单词游戏、IP 路由表——凡是需要基于前缀的操作都优先考虑 Trie。注意search与starts_with的区别前者要求路径终点恰好是一个完整单词is_end为 True后者只要求前缀路径存在。Hard · 单词搜索 II问题给定字符棋盘和单词列表找出所有可由相邻格子路径组成的单词。模式先用单词列表建 Trie再从每个格子出发 DFS用 Trie 尽早剪枝——若当前前缀下没有任何单词starts_with为假立即停止该方向。陷阱不用 Trie 时需要对每个单词单独 DFS复杂度为 $O(w \cdot m \cdot n \cdot 4^L)$Trie 让所有单词共享前缀计算大幅削减重复工作。这与 基础篇 的「哈希表查找把重复计算转化为 $O(1)$ 查询」是同一思想——用结构共享消灭重复前缀的搜索。并查集Union-Find / Disjoint Set UnionUnion-Find维护一组不相交的集合核心操作有两个find(x)返回 $x$ 所在集合的代表元union(x, y)合并 $x$、$y$ 所在的集合。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.count n # number of connected components def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # path compression return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False # already connected # union by rank if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 self.count - 1 return True复杂度路径压缩path compression 按秩合并union by rank后两个操作均摊 $O(\alpha(n)) \approx O(1)$反阿克曼函数工程上视为常数。count字段实时追踪连通分量数量是后文连通分量问题的关键。适用场景连通分量、无向图环检测、Kruskal 最小生成树、等价项分组。离散数学章节 明确指出 Kruskal 算法「排序边贪心加入不产生环的最轻边」其中「不产生环」的判定正是并查集若边的两端点已在同一集合加入该边必成环。而 MST 与 图论章节 的连通性、图算法章节的 DFS 连通分量 互为补充DFS 递归写法空间 $O(n)$并查集更省且天然支持动态加边。Medium · 连通分量数量def count_components(n, edges): uf UnionFind(n) for u, v in edges: uf.union(u, v) return uf.count逐条 union 所有边后count就是连通分量数量。这是「动态连通性」的经典场景与图章节 BFS/DFS 计岛Number of Islands是同一问题的两种求解视角。Medium · 冗余连接Redundant Connection问题找出那条「删除后图变成树」的边即产生环的那条边。模式逐条处理边第一条「两端点已在同一分量」的边就是制造环的边。def find_redundant(edges): uf UnionFind(len(edges) 1) for u, v in edges: if not uf.union(u, v): return [u, v] # already connected → this edge creates a cycle这里UnionFind(len(edges) 1)是因为节点编号从 1 开始需要 $n1$ 个槽位$n$ 为边数恰好等于树中节点数。union 返回False表示两端已连通——该边制造了环直接返回。线段树Segment Tree与 Fenwick 树树状数组线段树支持区间查询子数组的 sum、min、max和单点更新均为 $O(\log n)$。它把数组递归分成两半用树节点缓存区间聚合值查询/更新只需沿树路径访问 $O(\log n)$ 个节点。**Fenwick 树二叉索引树 / BIT**是前缀和查询与单点更新的更简单、更快的替代方案。它利用一个巧妙的位运算技巧每个位置存储一段「由最低有效位lowest set bit决定范围」的部分和。class FenwickTree: def __init__(self, n): self.n n self.tree [0] * (n 1) def update(self, i, delta): i 1 # 1-indexed while i self.n: self.tree[i] delta i i (-i) # add lowest set bit def prefix_sum(self, i): i 1 total 0 while i 0: total self.tree[i] i - i (-i) # remove lowest set bit return total def range_sum(self, l, r): return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l 0 else 0)位运算直觉i (-i)提取整数i的最低有效位。update沿树向上走i lowbitprefix_sum沿树向下走i - lowbit两者都以 $O(\log n)$ 步完成。理解这一点就不需要死记代码。何时选哪种只需前缀和与点更新 → Fenwick 树代码短、常数小、内存省需要任意区间运算min、max、GCD 等不可逆运算→ 线段树。二者可视为「静态数组 动态更新」场景下的进阶替代与第 14 章前缀和基础形成从静态到动态的递进。陷阱原文档要点Fenwick 树的内部数组是 1 索引的而调用方传入的是 0 索引。update和prefix_sum入口必须统一i 1range_sum中l 0时要避免访问prefix_sum(-1)。漏掉任何一处偏移都会造成 off-by-one 错误。常见陷阱速查表陷阱示例修复只检查 BST 直接孩子left.val root.val漏掉深层违规传递lo/hi边界递归中 $O(n^2)$ 列表拼接inorder(left) [val] inorder(right)改为向共享列表 append忘记基准情形空树上无限递归if not root: return混淆「经过节点」与「贡献父节点」的路径最大路径和路径在两层分叉返回单分支给父节点双分支单独记录Fenwick 1 索引 vs 0 索引树数组 off-by-one入口统一i 1Union-Find 不做路径压缩最坏情况每次 find $O(n)$self.parent[x] self.find(self.parent[x])此外结合仓库其他章节还可补充两条实战经验Python 递归深度默认递归限制约 1000基础篇 明确提到。深度树如退化的 BST应优先迭代解法显式栈或用sys.setrecursionlimit谨慎调高完全二叉树的数组存储二叉堆是「父子下标满足 $2i1$、$2i2$」的完全二叉树详见 链表/栈/队列章节的堆部分——它是线段树「树形数组化」思想的近亲值得对比学习。课后练习NeetCode 题单以下题目按模式分组建议按「先看懂模式 → 徒手实现 → 计时训练」的顺序完成题名与原文档一致可在 LeetCode/NeetCode 上检索对应题目二叉树模式Invert Binary Tree — 基础递归Maximum Depth of Binary Tree — 递归深度Same Tree — 同步遍历Subtree of Another Tree — 嵌套递归Binary Tree Level Order Traversal — BFS 分层Binary Tree Maximum Path Sum — DFS 全局最优Serialize and Deserialize Binary Tree — 前序 空标记BST 模式Validate Binary Search Tree — 边界传播Kth Smallest Element in a BST — 中序遍历Lowest Common Ancestor of a BST — 利用 BST 有序性TrieImplement Trie — 基础操作Design Add and Search Words — Trie 通配符 DFSWord Search II — Trie 引导的回溯Union-FindNumber of Connected Components — 基础并查集Redundant Connection — 并查集环检测小结本文把 原树章节 的完整知识体系四种遍历、BST、Trie、Union-Find、线段树/Fenwick 树全部继承并逐项深化每段代码都保留了可直接运行的原版实现同时补充了复杂度分析、隐藏陷阱与仓库内交叉证据——树的数学定义来自离散数学递归心法来自基础篇红黑树与 B 树的工业应用来自操作系统决策树与随机森林见机器学习章节堆与完全二叉树见链表章节。掌握「基准情形 递归子树 合并」这一统一模式配合上述数据结构的选择直觉你将能从容应对绝大多数树类面试与工程问题。【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考