树与二叉树Trees Binary Trees速记模板一、基本概念树 层次结构 根 子树集合性质N个结点 → N−1条边必背术语超级重点✔ degree度孩子个数✔ leaf度为0✔ depth深度根→该点根深度0✔ height高度该点→最深叶叶高度0✔ 树高 根的高度 最深节点深度易错点❌ 深度 vs 高度混❌ 路径长度 边数不是点数二、二叉树核心性质1. 每层最大节点数第i层最多2的i-1次方高度k最大节点2的k次方-12. 核心公式必考n0 n2 1叶子数 度为2节点 13. 推导记忆n n0 n1 n2边数 B n1 2n2n B 1 → 合并得 n0 n2 1三、遍历Traversal1. 三种DFS遍历✔ Preorder根→左→右✔ Inorder左→根→右✔ Postorder左→右→根2. Level-order层序✔ 队列实现✔ BFS遍历3. 非递归中序重点✔ 栈 ✔ 一路左压栈 → 弹出访问 → 转右子树4. 表达式树✔ 前序 前缀表达式✔ 中序 中缀表达式✔ 后序 后缀表达式四、线索二叉树Threaded Tree核心思想n个节点 → n1个空指针浪费 用空指针✔ 指向中序前驱左线索✔ 指向中序后继右线索优点✔ 不用递归✔ 不用栈✔ O(1)遍历五、真题讲解统一速解2.【R1-9】complete binary tree last level✔ 完全二叉树结构固定✔ 最后一层影响总节点数结论按结构约束判断不是简单3n→ ❌ False3.【R1-8】每个节点都是子树根✔ True定义性质4.【R2-20】complete tree level constraints→ 用满二叉树上界估计核心✔ 第k层最多2^(k-1)✔ 叶子在最后两层5.【R2-11】level-order index规律left child 2i right child 2i16.【R1-9】general tree → binary tree traversal ❌ False原因✔ binary tree转换改变结构✔ traversal顺序不保持postorder对应7.【2-6】degree统计 leaf核心leaf n - Σdegree0 nodes贡献或用n0 n2 1变形8.【2-4】100 leaves, no degree-1 nodes核心n0 n2 1 n1 0→ n 2n0 -19.【1-3】array存完全二叉树✔ 同一层判断index i层 floor(log2 i)→ 判断层级相同10.【2-8】四叉树 quadtree degree 问题核心类似推广leaf Σ(di - 1)*ni 111.【1-9】2016 nodes 16 single-child nodes关键公式n0 n2 1n1不影响叶子关系 → 可存在 → ✔ True12.【1-10】complete binary tree array✔ sibling条件i and i1 / i even-odd pair→ 判断位置关键3. 关键技巧✔ root找最后/第一个 ✔ inorder切分左右 ✔ 递归重建✔ 每个节点都是子树根 → True✔ preorder postorder可唯一确定 → False✔ inorder postorder唯一建树 → True✔ preorder inorder唯一建树 → True八、考试最重要总结✔ n0 n2 1✔ 每层最多 2^(i−1)✔ 树高 log n✔ preorder root first ✔ inorder BST排序基础 ✔ postorder root last✔ 完全二叉树 → 数组2i规则 ✔ 表达式树 → 后序建树树 层次结构 n0n21 DFS三种遍历 BFS层序 结构可唯一还原 一、拓扑排序到底在解决什么问题拓扑排序解决的是“有依赖关系的任务应该按什么顺序执行”比如学AI前要先学线代修数据结构前要先学C语言做项目要先完成模块A再做模块B这些都可以建模成图A → B 表示A必须在B之前完成 二、必须满足的条件DAG✔ 拓扑排序只适用于DAGDirected Acyclic Graph有向无环图如果有环 A → B → C → A 谁先做都不对 ❌所以无法排序只要有循环依赖就不存在拓扑序⚙️ 三、Kahn算法入度法在干什么你记的三句话其实就是算法本体✔ 1. 入度0入队入度 有多少前置任务入度 0 → 没有依赖 → 可以做 所以先把所有“可以直接做的任务”放进队列✔ 2. 出队执行从队列拿一个点 代表“这个任务完成了”✔ 3. 删除边核心做完这个任务后 它指向的后续任务依赖减少1也就是A -- B -- C如果 A 做完删除 A→B B 入度 -1如果 B 入度变成0 → B 可以做了 四、整个过程本质是什么拓扑排序其实不是“排序”而是不断消除依赖关系的过程可以理解成 “依赖流动模型”入度0 → 可执行集合 → 执行 → 释放依赖 → 新节点入队 五、一个直觉例子图A → C B → C C → D第一步入度A:0B:0C:2D:1队列[A,B]执行 AC 入度变1执行 BC 入度变0 → 入队队列[C]执行 CD 入度变0 → 入队执行 D结束拓扑序可能A → B → C → D 或 B → A → C → D 说明拓扑排序不唯一 六、考试最爱考的本质总结你一定要记住这3句本质理解✔ 1. 入度依赖数 In-degree number of dependencies入度就是“还不能做的理由”1. In-degree represents unresolved prerequisites that block execution✔ 2. 拓扑排序消除依赖 Topological sort eliminate dependencies每删除一条边就是“解除一个限制”2. Removing an edge removes one constraint✔ 3. DAG保证不会卡死 DAG prevents deadlock因为一定存在入度0的点3. There always exists a node with in-degree zero⚠️ 七、常见坑考试高频❌ 1. 有环怎么办队列会空 但还有点没处理 ⇒ “无法拓扑排序”❌ 2. 入度0不一定唯一可以多个点同时入队 顺序不唯一❌3. “删除边”不是物理删除更新入度数组 一句话终极理解考试背这个 拓扑排序就是不断把“没有依赖的点”拿出来执行并减少其他点的依赖直到所有点完成。FDS期末冲刺总地图树 图 排序 Hash 流一、树Tree1. 基础性质✔ N个节点 → N−1条边✔ depth根到节点根0✔ height节点到最深叶叶0✔ n0 n2 1叶子二度节点12. 二叉树✔ 每层最多2^(i−1)✔ 高度k最多2^k−1✔ 完全二叉树数组存储 → 左2i 右2i13. 遍历✔ preorder根左右✔ inorder左根右BST排序基础✔ postorder左右根表达式建树✔ levelorder队列BFS4. 树核心题型✔ 结构重建inpost唯一✔ preorderpostorder不唯一✔ 表达式树后序建树✔ threaded tree利用空指针优化遍历✔ Expression tree: build via post-order traversal✔ Threaded tree: optimize traversal by using null pointers二、图Graph1. DFS✔ O(VE)✔ visited防重复✔ 连通分量DFS次数割点Articulation Point✔ root子树≥2✔ non-rootLow[v] ≥ Num[u]2. BFS✔ 最短路无权图 ✔ 队列 ✔ 层序扩展✔ Shortest path (unweighted graph) ✔ Queue ✔ Level-order expansion3. 拓扑排序✔ DAG才有DAG有向无环图directed acyclic graph✔ 入度0入队✔ 删除边4. 最短路✔ BFS无权✔ Dijkstra非负权✔ DAG拓扑排序DP5. MST最小生成树✔ Kruskal按边排序并查集 ✔ Prim点扩展类似Dijkstra✔ Kruskal: sort edges Disjoint Set Union ✔ Prim: expand vertices (similar to Dijkstra)核心性质✔ cut最小边必选✔ |E|V−1✔ MST≠最短路三、排序Sorting1. 下界✔ comparison sort ≥ Ω(N log N) ✔ 来自决策树 N!排列2. 插入排序✔ O(NI)I逆序对✔ 最好O(N) ✔ 稳定3. 希尔排序✔ gap insertion ✔ 不稳定 ✔ 原始O(N²)4. 归并排序✔ O(N log N) ✔ 稳定 ✔ O(N)空间5. 堆排序✔ O(N log N) ✔ 不稳定 ✔ O(1)空间6. 快速排序✔ 平均O(N log N) ✔ 最坏O(N²) ✔ pivot决定性能 ✔ partition确定最终位置✔ Pivot determines performance ✔ Partition defines the final position7. 非比较排序✔ bucketO(NM)✔ radixO(P(NB))✔ LSD低位→高位必须稳定✔ MSD高位→递归✔ LSD: least significant digit → most significant digit (stable sort required)✔ MSD: most significant digit → recursive processing四、Hashing散列1. 核心目标平均O(1)查找/插入/删除2. 冲突解决Separate Chaining✔ 链表 ✔ αN/M ✔ α≈1最佳 ✔ α可1Open Addressing✔ 表内探测 ✔ α 0.5方法✔ lineari✔ quadratici²✔ double hashingi·h2(x)3. 性质✔ linear → primary clustering 集聚✔ quadratic → secondary clustering✔ double hashing → 最优4. Rehashing✔ 表太满 → 扩容2倍素数 ✔ O(N)重建 ✔ amortized O(1)5. Robin Hood✔ 平衡探测距离 ✔ 降低方差 ✔ 插入复杂✔ Balances probe distances ✔ Reduces variance ✔ Complex insertion logic五、网络流Flow1. 核心思想✔ residual graph✔ augmenting path✔ reverse edge反悔机制2. Max Flow算法✔ BFS增广 Edmonds-Karp✔ O(VE²)✔ Dinic更快3. 核心定理✔ Max Flow Min Cut4. 关键机制✔ 每次选增广路✔ 更新正反边✔ 无路径即最优⭐ 一句话总纲 树 结构 遍历 n0n21 图 DFS/BFS 最短路 MST 拓扑 排序 NlogN下界 五大排序模型 Hash O(1)均摊 冲突处理 Flow residual graph 增广路⭐ FDS本质数据结构 “如何组织数据 如何高效操作 如何在约束下优化时间复杂度” 一、网络流到底在干什么在一个有容量限制的网络中寻找从源点 S 到汇点 T 的最大“流量”。可以类比水管系统 信息流 交通流 每条边有容量 capacity最多能走多少 二、核心三大思想必须理解1️⃣ Residual Graph残量图当前“还能再走多少流”的图每条边被拆成两条正向边表示还能加多少流反向边表示“可以撤销多少流”关键 为什么要有反向边之前走错了路可以“退回去重新分配”这就是反悔机制 举个直觉例子S → A → T 容量都是 5如果你先送了 3 单位流S→A 剩 2A→T 剩 2同时 反向边出现A→S 有 3可以退回3T→A 有 3residual graph 残量图 “还能调整的空间”2️⃣ Augmenting Path增广路从 S 到 T 的一条路径且所有边 residual capacity 0 它在干嘛找一条“还能再塞流”的路✔ 一次增广做什么找一条路径 找瓶颈最小剩余容量 统一加流 关键点 每次增广都会 push 一点流 改变 residual graph3️⃣ Reverse Edge反向边 / 反悔机制这是整个网络流的灵魂允许“撤销之前的流量” 为什么必须要反悔因为你一开始可能选错路径S → A → T (先占满) S → B → T但可能 最优解应该是S → B → A → T✔ 反向边允许你把 A→T 的流退回来 改走更优路径网络流不是贪心是“可修正的贪心”⚙️ 三、Max Flow算法1️⃣ Edmonds-Karp 埃德蒙兹 - 卡普算法EK用 BFS 找最短增广路按边数✔ 步骤BFS 找 S→T 路径 Find S-to-T paths via BFS找最小残量瓶颈 Locate minimum residual capacity (bottleneck)增广 Augment flow更新 Update residual graph重复 Repeat⏱ 复杂度O(VE²) 特点简单稳定 但慢2️⃣ Dinic重点优化版✔ 核心优化 分层图 DFS一次性推多流✔ 两步① BFS建层图只保留“从浅到深”的边② DFS增广一次尽可能推满⏱ 复杂度O(E√V) 或 O(EV^{1/2})实际更快 直觉EK 一条一条试Dinic 批量推进 四、核心定理必须背⭐ Max Flow Min Cut✔ 什么是 Cut把图分成两部分S 在一边 T 在另一边割掉的边就是 cut✔ Min Cut使得割断 S→T 的边容量最小 定理含义最大能送多少流 最少要切多少容量才能阻断 直觉理解流是“水” cut 是“堵水坝”⚙️ 五、关键机制总结考试必写✔ 1. 每次选增广路 找还能走的路径✔ 2. 更新正反边正向边减少反向边增加关键✔ 3. 无增广路即最优 当 S 到 T 再也走不通当前流量 最大流 六、 网络流本质是不断在 residual graph 中寻找可行路径并通过“正向加流 反向撤销”不断修正直到无法改进为止。 七、考试高频陷阱❌ 1. 忘反向边 → 直接错核心机制❌ 2. 误以为是贪心 → 网络流不是贪心是“可修正系统”❌ 3. 不理解 residual graph → EK / Dinic 都写不出来