数据结构基础——第三板块：树与二叉树（Trees Binary Trees）

树与二叉树（Trees & Binary Trees）速记模板

一、基本概念

树 = 层次结构 = 根 + 子树集合
性质：N个结点 → N−1条边（必背）

术语（超级重点）

✔ degree（度）：孩子个数
✔ leaf：度为0
✔ depth（深度）：根→该点（根深度=0）
✔ height（高度）：该点→最深叶（叶高度=0）
✔ 树高 = 根的高度 = 最深节点深度

易错点

❌ 深度 vs 高度混
❌ 路径长度 = 边数不是点数

二、二叉树核心性质

1. 每层最大节点数

第i层最多：2的（i-1）次方

高度k最大节点：2的k次方-1

2. 核心公式（必考）

n0 = n2 + 1

叶子数 = 度为2节点 + 1

3. 推导记忆

n = n0 + n1 + n2
边数 B = n1 + 2n2
n = B + 1 → 合并得 n0 = n2 + 1

三、遍历（Traversal）

1. 三种DFS遍历

✔ Preorder：根→左→右
✔ Inorder：左→根→右
✔ Postorder：左→右→根

2. Level-order（层序）

✔ 队列实现
✔ BFS遍历

3. 非递归中序（重点）

✔ 栈 ✔ 一路左压栈 → 弹出访问 → 转右子树

4. 表达式树

✔ 前序 = 前缀表达式
✔ 中序 = 中缀表达式
✔ 后序 = 后缀表达式

四、线索二叉树（Threaded Tree）

核心思想

n个节点 → n+1个空指针浪费

👉 用空指针：

✔ 指向中序前驱（左线索）
✔ 指向中序后继（右线索）

优点

✔ 不用递归
✔ 不用栈
✔ O(1)遍历

五、真题讲解（统一速解）

2.【R1-9】

complete binary tree + last level

✔ 完全二叉树结构固定
✔ 最后一层影响总节点数

结论：按结构约束判断，不是简单3n

→ ❌ False

3.【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 = 2i+1

6.【R1-9】

general tree → binary tree traversal ❌ False

原因：

✔ binary tree转换改变结构
✔ traversal顺序不保持postorder对应

7.【2-6】

degree统计 leaf

核心：

leaf = n - Σdegree>0 nodes贡献

或用：n0 = n2 + 1（变形）

8.【2-4】

100 leaves, no degree-1 nodes

核心：

n0 = n2 + 1 n1 = 0

→ n = 2n0 -1

9.【1-3】

array存完全二叉树

✔ 同一层判断：

index i层 = floor(log2 i)

→ 判断层级相同

10.【2-8】

四叉树 quadtree degree 问题

核心：

类似推广：

leaf = Σ(di - 1)*ni + 1

11.【1-9】

2016 nodes + 16 single-child nodes

关键公式：

n0 = n2 + 1

n1不影响叶子关系 → 可存在 → ✔ True

12.【1-10】

complete binary tree array

✔ sibling条件：

i and i+1 / 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规则 ✔ 表达式树 → 后序建树

树 = 层次结构 + n0=n2+1 + DFS三种遍历 + BFS层序 + 结构可唯一还原

🧠 一、拓扑排序到底在解决什么问题？

拓扑排序解决的是：

“有依赖关系的任务，应该按什么顺序执行？”

比如：

• 学AI前要先学线代
• 修数据结构前要先学C语言
• 做项目要先完成模块A再做模块B

这些都可以建模成图：

👉A → B 表示：A必须在B之前完成

📌 二、必须满足的条件：DAG

✔ 拓扑排序只适用于：

DAG（Directed 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:0
• B:0
• C:2
• D:1

队列：[A,B]

执行 A：

• C 入度变1

执行 B：

• C 入度变0 → 入队

队列：[C]

执行 C：

• D 入度变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 + 流）

一、树（Tree）

1. 基础性质

✔ N个节点 → N−1条边
✔ depth=根到节点（根=0）
✔ height=节点到最深叶（叶=0）
✔ n0 = n2 + 1（叶子=二度节点+1）

2. 二叉树

✔ 每层最多2^(i−1)
✔ 高度k最多2^k−1
✔ 完全二叉树：数组存储 → 左2i 右2i+1

3. 遍历

✔ preorder：根左右
✔ inorder：左根右（BST排序基础）
✔ postorder：左右根（表达式建树）
✔ levelorder：队列BFS

4. 树核心题型

✔ 结构重建：in+post唯一
✔ preorder+postorder不唯一
✔ 表达式树：后序建树
✔ threaded tree：利用空指针优化遍历

✔ Expression tree: build via post-order traversal

✔ Threaded tree: optimize traversal by using null pointers

二、图（Graph）

1. DFS

✔ O(V+E)
✔ visited防重复
✔ 连通分量=DFS次数

割点（Articulation Point）

✔ root：子树≥2
✔ non-root：Low[v] ≥ Num[u]

2. BFS

✔ 最短路（无权图） ✔ 队列 ✔ 层序扩展

✔ Shortest path (unweighted graph) ✔ Queue ✔ Level-order expansion

3. 拓扑排序

✔ DAG才有DAG（有向无环图directed acyclic graph）
✔ 入度=0入队
✔ 删除边

4. 最短路

✔ BFS：无权
✔ Dijkstra：非负权
✔ DAG：拓扑排序DP

5. MST（最小生成树）

✔ Kruskal：按边排序+并查集 ✔ Prim：点扩展（类似Dijkstra）

✔ Kruskal: sort edges + Disjoint Set Union ✔ Prim: expand vertices (similar to Dijkstra)

核心性质

✔ cut最小边必选
✔ |E|=V−1
✔ MST≠最短路

三、排序（Sorting）

1. 下界

✔ comparison sort ≥ Ω(N log N) ✔ 来自决策树 + N!排列

2. 插入排序

✔ O(N+I)（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 position

7. 非比较排序

✔ bucket：O(N+M)
✔ radix：O(P(N+B))
✔ 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最佳 ✔ α可>1

Open Addressing

✔ 表内探测 ✔ α < 0.5

方法

✔ linear：i
✔ quadratic：i²
✔ double hashing：i·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

五、网络流（Flow）

1. 核心思想

✔ residual graph
✔ augmenting path
✔ reverse edge（反悔机制）

2. Max Flow算法

✔ BFS增广 = Edmonds-Karp
✔ O(VE²)
✔ Dinic更快

3. 核心定理

✔ Max Flow = Min Cut

4. 关键机制

✔ 每次选增广路
✔ 更新正反边
✔ 无路径即最优

⭐ 一句话总纲

👉 树 = 结构 + 遍历 + n0=n2+1
👉 图 = DFS/BFS + 最短路 + MST + 拓扑
👉 排序 = NlogN下界 + 五大排序模型
👉 Hash = O(1)均摊 + 冲突处理
👉 Flow = residual graph + 增广路

⭐ FDS本质

数据结构 = “如何组织数据 + 如何高效操作 + 如何在约束下优化时间复杂度”

🌊 一、网络流到底在干什么？

在一个有容量限制的网络中，寻找从源点 S 到汇点 T 的最大“流量”。

可以类比：水管系统 🚰 信息流 📦 交通流 🚗

每条边：有容量 capacity（最多能走多少）

🔥 二、核心三大思想（必须理解）

1️⃣ Residual Graph（残量图）

当前“还能再走多少流”的图

每条边被拆成两条：

正向边：表示还能加多少流

反向边：表示“可以撤销多少流”（关键！）

💡 为什么要有反向边？

之前走错了路，可以“退回去重新分配”

这就是反悔机制

📦 举个直觉例子

S → A → T 容量都是 5

如果你先送了 3 单位流：

• S→A 剩 2
• A→T 剩 2

同时👉 反向边出现：

• A→S 有 3（可以退回3）
• T→A 有 3

residual graph 残量图 = “还能调整的空间”

2️⃣ Augmenting Path（增广路）

从 S 到 T 的一条路径，且所有边 residual capacity > 0

💡 它在干嘛？

找一条“还能再塞流”的路

✔ 一次增广做什么？

找一条路径 找瓶颈（最小剩余容量） 统一加流

📌 关键点：

👉 每次增广都会： push 一点流 改变 residual graph

3️⃣ Reverse Edge（反向边 / 反悔机制）

这是整个网络流的灵魂🔥

允许“撤销之前的流量”

💡 为什么必须要反悔？

因为你一开始可能选错路径：

S → A → T (先占满) S → B → T

但可能👉 最优解应该是：

S → B → A → T

✔ 反向边允许你：把 A→T 的流退回来 ，改走更优路径

网络流不是贪心，是“可修正的贪心”

⚙️ 三、Max Flow算法

1️⃣ Edmonds-Karp 埃德蒙兹 - 卡普算法（EK）

用 BFS 找最短增广路（按边数）

✔ 步骤：

1. BFS 找 S→T 路径 Find S-to-T paths via BFS
2. 找最小残量（瓶颈） Locate minimum residual capacity (bottleneck)
3. 增广 Augment flow
4. 更新 Update residual graph
5. 重复 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 都写不出来