第六章 树：层级世界的骨架
1646 字
8 分钟
第六章 树：层级世界的骨架
第六章 树 (Tree) —— 总览与导航
一句话理解：树是具有层级关系的非线性数据结构。从文件系统到 DOM 树，从数据库索引到游戏场景图，树无处不在——它也是面试中考查密度最高的数据结构，没有之一。
为什么树需要一整章（六篇）？
前五章的数据结构（数组、链表、栈、队列、哈希表）都是线性的——元素排成一条线。但现实中大量问题天然具有层级 / 分支结构：
| 场景 | 树结构 |
|---|---|
| 文件系统 | 目录树（每个文件夹是一个节点） |
| HTML / XML | DOM 树 |
| 编译器 | 抽象语法树 (AST) |
| 数据库索引 | B+ 树 |
| 游戏引擎 | 场景树（父子节点继承 Transform） |
| AI 决策 | 行为树 (Behavior Tree) |
| 排序 / 调度 | 堆（完全二叉树） |
| 区间查询 | 线段树 / 树状数组 |
| 骨骼动画 | 骨骼层级树 |
树的变体极多，每种都有独立的算法和面试考法。因此本章拆分为六个子章节，每篇聚焦一个专题：
章节导航
📗 6.1 二叉树基础与遍历
从树的基本术语到四种遍历方式（前序 / 中序 / 后序 / 层序），涵盖递归与迭代实现、Morris 遍历的 O(1) 空间技巧，以及高频面试题：最大深度、对称性判断、路径总和等。
核心内容：
- 树的术语：根、叶、深度、高度、度
- 二叉树的三种表示（链式 / 数组 / 括号表达式）
- 前序 / 中序 / 后序遍历（递归 + 迭代栈写法）
- 层序遍历 (BFS)
- Morris 遍历（O(1) 空间的中序遍历——利用线索化）
- 面试题：LC 104 最大深度、LC 101 对称二叉树、LC 226 翻转二叉树、LC 112 路径总和、LC 236 最近公共祖先、LC 105 从前中序构建二叉树
📘 6.2 二叉搜索树 BST
从 BST 的有序性质到增删查的完整实现，深入
std::map/std::set的红黑树底层选型原因，以及 BST 高频面试题。
核心内容：
- BST 性质：左 < 根 < 右，中序遍历有序
- 查找、插入、删除的递归实现
- 删除的三种情况（叶节点、单子、双子——Hibbard 删除）
- BST 退化问题（有序插入 → 链表 → O(n)）
std::map/std::set为什么用红黑树而不是 BST- 面试题：LC 98 验证 BST、LC 230 第 K 小元素、LC 235 BST 最近公共祖先、LC 108 有序数组转 BST、LC 450 删除 BST 中的节点
📙 6.3 平衡树：AVL 与红黑树
从 AVL 的四种旋转到红黑树的五条性质，理解”为什么 STL 选红黑树而非 AVL”，以及平衡树在数据库索引中的应用。
核心内容：
- 为什么需要平衡？—— BST 退化的解决方案
- AVL 树：平衡因子、LL / RR / LR / RL 四种旋转（配完整图解）
- AVL 的插入与删除流程
- 红黑树：五条性质、插入修复（变色 + 旋转）的完整分析
- AVL vs 红黑树：查找密集用 AVL，插删频繁用红黑树
std::map实现细节与迭代器稳定性- 扩展：B 树 / B+ 树与数据库索引的关系
📕 6.4 堆与优先队列
从堆的数组表示到 sift-up / sift-down 的完整实现，手写堆排序，以及 Top-K问题的工程化解法。
核心内容：
- 完全二叉树与数组存储的映射关系
- 最大堆 / 最小堆的性质
- sift-up (插入) 与 sift-down (删除) 的实现
std::priority_queue底层回顾（与第 4 章呼应）std::make_heap/push_heap/pop_heap的 STL 堆操作族- 堆排序 (Heap Sort) 的完整实现与复杂度分析
- 手写支持 decrease-key 的索引堆 (Indexed Heap)
- 面试题：LC 215 第 K 大元素（重温）、LC 295 数据流的中位数（双堆）、LC 23 合并 K 个有序链表（最小堆）、LC 973 最接近原点的 K 个点
📔 6.5 线段树 & 树状数组
区间查询与修改的利器——线段树支持 O(log n) 的区间求和/最值/修改，树状数组用更少的代码实现前缀和动态维护。面试中低频但加分。
核心内容：
- 线段树：区间查询 / 区间修改、懒传播 (Lazy Propagation)、递归实现
- 树状数组 (BIT)：lowbit 技巧、前缀和查询、单点修改
- 线段树 vs 树状数组的取舍
- 面试题：LC 307 区域和检索、LC 315 逆序对计数
- 🎮 实时伤害统计（区间求和）、排行榜动态排名查询
📓 6.6 实战场景：场景树、骨骼动画与定时器
树结构在游戏引擎中的五大核心应用，每个场景配完整 C++ 实现。
核心内容：
- 场景树 (Scene Graph)：父子节点 Transform 继承、世界坐标计算
- 骨骼动画 (Skeletal Animation)：骨骼层级树、逆向运动学 (IK) 概念
- 行为树 (Behavior Tree)：Selector / Sequence / Decorator 节点的 AI 决策
- 定时器管理 (Timer Wheel)：时间轮层级结构
- 表达式求值与 AST：脚本引擎中的抽象语法树
- 树结构在分布式系统中的映射（ZooKeeper、DNS）
阅读建议
graph TD
A["6.1 二叉树基础"] --> B["6.2 BST"]
B --> C["6.3 平衡树"]
A --> D["6.4 堆"]
C --> E["6.5 实战场景"]
D --> E
C --> F["6.6 线段树"]
style A fill:#2d6a4f,stroke:#40916c,color:white
style B fill:#1b4332,stroke:#2d6a4f,color:white
style C fill:#d00000,stroke:#e85d04,color:white
style D fill:#e85d04,stroke:#f48c06,color:white
style E fill:#6a040f,stroke:#9d0208,color:white
style F fill:#7b2cbf,stroke:#9d4edd,color:white
- 面试急救：6.1 → 6.2 → 6.4（覆盖 80% 的面试题）
- 深入理解：6.1 → 6.2 → 6.3 → 6.5（平衡树 + 线段树，面试加分项）
- 工程导向：6.1 → 6.6（直接看树在游戏引擎中的应用）
面试题全景预览
| 子章节 | 高频面试题 | 数量 |
|---|---|---|
| 6.1 二叉树基础 | 最大深度、对称性、翻转、路径总和、LCA、构建树 | ~15 题 |
| 6.2 BST | 验证BST、第K小、删除节点、BST转排序链表 | ~10 题 |
| 6.3 平衡树 | AVL 旋转、红黑树性质（概念题为主） | ~5 题 |
| 6.4 堆 | 数据流中位数、Top-K、合并K链表、堆排序 | ~10 题 |
| 6.5 线段树 | 区间和查询、逆序对计数 | ~5 题 |
| 6.6 实战场景 | 场景图遍历、行为树设计（系统设计题） | ~5 题 |
| 合计 | ~50 题 |
💡 树是面试中题量最大的单一数据结构。如果时间有限，优先刷 6.1 的遍历类题目 和 6.4 的 Top-K 问题——这两块覆盖了树类面试的半壁江山。6.6 线段树是进阶加分项，时间充裕再看。
📖 上一章：第五章 哈希表：空间换时间的极致
📖 下一章：第七章 图：万物皆可连 — 图的存储与遍历、最短路径、最小生成树与拓扑排序。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
第六章 树：层级世界的骨架
https://firefly-7a0.pages.dev/posts/data_structure/tree/ 相关文章 智能推荐
1
6.2 二叉搜索树 BST
数据结构笔记 **面试突击 · BST。** 从二叉搜索树的有序性质到增删查的完整 C++ 实现，剖析 BST 退化问题与 std::map/std::set 的选型原因，手撕验证 BST、第 K 小元素、删除节点等高频面试题。
2
6.5 线段树 & 树状数组
数据结构笔记 **面试突击 · 线段树。** 区间查询与修改的利器——从线段树的递归实现到懒传播优化，从树状数组的 lowbit 技巧到逆序对计数，掌握区间问题的两大杀器。
3
第八章 字典树：前缀的力量
数据结构笔记 **面试突击 · 字典树。** 从标准 Trie 到压缩 Trie (Radix Tree)，手写插入/查找/前缀匹配的完整实现，剖析数组 vs 哈希两种子节点存储的工程取舍，掌握单词搜索 II、自动补全设计等高频面试题，深入游戏敏感词过滤与控制台命令补全实战。
4
6.3 平衡树：AVL 与红黑树
数据结构笔记 **面试突击 · 平衡树。** 从 AVL 的四种旋转到红黑树的五条性质，手写 AVL 插入与删除，深入理解 STL 为什么选红黑树不选 AVL，以及 B/B+ 树在数据库中的角色。
5
第三章 栈：后进先出的秩序
数据结构笔记 **面试突击 · 栈。** 从函数调用栈到单调栈，剖析 std::stack 的适配器模式，手撕柱状图最大矩形，深入游戏引擎中的 UI 栈、状态机与 Undo/Redo 实战。
随机文章 随机推荐
评论区
欢迎来到我的博客！
音乐
暂未播放
0:00 0:00
119
11
346
226,548
0 天
0 天前