二叉树与二叉搜索树
二叉树（Binary Tree）是最基础、最重要的非线性数据结构——每个节点最多有两个子节点（左孩子、右孩子），整棵树由「根节点 + 左子树 + 右子树」递归构成。它把线性结构里的「前后关系」升级为「父子层级关系」，是表达式树、决策树、哈夫曼树、B 树/B+ 树等一切树形结构的根基，也是理解堆、并查集、线段树、字典树（Trie）的前置知识。二叉搜索树（BST） 是加了有序约束的二叉树（左子树值 < 根 < 右子树值），把链表的「动态增删」与有序数组的「快速查找」融合在一起——理想情况下查找/插入/删除都是 O(log n)，相当于一棵「天然的二分查找结构」。
二叉树的全部考点围绕两条主线：①遍历——前序（根左右）、中序（左根右）、后序（左右根）三种深度优先（DFS）+ 层序（BFS）广度优先，递归写法直观、迭代写法靠栈（DFS）或队列（BFS），Morris 遍历甚至能把空间压到 O(1)；②有序化与平衡——BST 的中序遍历天然得到升序序列，但退化为链表时操作退化到 O(n)，于是引入平衡树（AVL 严格平衡高度差 ≤ 1、红黑树弱平衡但增删旋转少）把高度稳定压在 O(log n)。红黑树因增删查都稳定 O(log n) 且旋转次数少，成为工业标准（C++ map/set、Java TreeMap、Linux 内核 CFS 调度、 epoll 都用它）。
评价
优点
- 天然递归结构：一棵二叉树 = 根 + 左子树 + 右子树，递归定义让大多数操作（遍历、求高度、翻转、判断对称）只需处理「根」再递归子树，代码极简
- BST 兼顾查找与增删：有序约束让查找走「二分」路径 O(h)，插入/删除也只需调整一条路径上的指针，不搬移数据（对比有序数组增删 O(n)）
- 中序得有序序列：BST 的中序遍历天然升序——这是「一边动态增删一边维护有序性」最自然的结构，省去反复排序
- 承载面广：堆（完全二叉树 + 数组映射）、哈夫曼树（带权路径最短）、字典树（多叉前缀树）、线段树/树状数组（区间操作）都以二叉树为模型
缺点
- 退化为链表：BST 按有序序列插入会退化成单链表，操作从 O(log n) 退化到 O(n)——这是 BST 必须配合平衡机制的硬伤
- 需要额外指针开销：每个节点要存左、右孩子指针（链式存储），平衡树还要存父指针/颜色/高度位，内存开销比数组大
- 不缓存友好：链式存储节点分散在堆上，遍历时跳跃访问缓存命中率低（数组存储的堆则缓存友好，但只适合完全二叉树）
本叶地图
- 入门 —— 树的术语（根/叶/深度/高度/度）、二叉树定义、满/完全/完美二叉树区别、链式存储（节点+左右指针）vs 数组存储（下标 2i+1/2i+2）、递归思维（左右子树）
- 遍历：前序、中序、后序与层序 —— 四种遍历的递归+迭代写法、中序得有序序列（BST）、Morris 遍历 O(1) 空间、层序 BFS 用队列、前序+中序还原树
- 二叉搜索树与平衡树 —— BST 性质（左<根<右）、查找/插入/删除 O(h)、删除三情况（叶子/单子/双子-后继）、退化为链表 O(n) 问题、AVL 旋转与红黑树性质、为何红黑树是工业标准
- 参考 —— 二叉树 API 速查、复杂度表、四种遍历代码模板、BST 操作模板、平衡树对比（AVL/红黑/TreeMap）、易错点
交互演示
- 二叉树可视化演示 —— 二叉树结构与四种遍历过程