系统性地梳理“树”的关键知识点。
一、核心概念与术语
想象一棵倒置的、家族树状的结构：
- 节点：树中的每个元素。
- 根节点：树最顶层的节点，没有父节点。
- 父节点/子节点：一个节点指向的下级节点是其子节点，它自己则是这些子节点的父节点。
- 兄弟节点：拥有同一个父节点的节点互称兄弟节点。
- 叶子节点（终端节点）：没有子节点的节点。
- 子树：一个节点及其所有后代节点构成一棵子树。
- 节点的度：一个节点拥有的子节点数目。
- 树的度：树中所有节点中最大的度。
- 路径与路径长度：从一个节点到另一个节点所经过的节点序列。路径长度为边的数量。
- 层次：根节点为第1层，其子节点为第2层，以此类推。
- 深度/高度：
- 节点的深度：从根节点到该节点的唯一路径长度（根节点深度为0或1，定义不同）。
- 节点的高度：从该节点到最远叶子节点的路径长度（叶子节点高度为0或1）。
- 树的高度/深度：根节点的高度或所有节点深度的最大值。
(这是一个简单的二叉树示意图，展示了基本结构)
二、树的分类（重点）
1. 二叉树
每个节点最多有两个子节点（左子节点和右子节点）。它是许多复杂树结构的基础。
- 满二叉树：除叶子节点外，每个节点都有两个子节点，且所有叶子节点都在同一层。
- 完全二叉树：除最后一层外，其他层都是满的，且最后一层的节点都尽量靠左排列。堆就是一种完全二叉树。
2. 二叉搜索树
一种特殊的二叉树，对于任意节点：
- 其左子树上所有节点的值 < 该节点的值。
- 其右子树上所有节点的值 > 该节点的值。
- 左右子树也分别是BST。优点：中序遍历可以得到有序序列。查找、插入、删除的平均时间复杂度为 O(log n)。缺点：如果插入顺序不当（如顺序插入1,2,3,4...），会退化成一条链，时间复杂度恶化至 O(n)。
3. 平衡二叉搜索树
为了解决BST可能失衡的问题而设计，通过旋转操作保持左右子树高度差在一定范围内（通常不超过1）。
- AVL树：严格的平衡，查找效率极高，但维护平衡的旋转操作开销较大。
- 红黑树：一种“近似平衡”的BST，它通过着色规则和旋转，确保从根到叶子的最长路径不超过最短路径的两倍。它是工程中应用最广泛的平衡树之一（如Java的
TreeMap， C++ STL的map/set）。
4. 多路查找树
每个节点可以有多个子节点，主要用于解决磁盘I/O效率问题（减少树的高度）。
- B树：一种平衡的多路查找树，用于文件系统和数据库索引。一个M阶B树，每个节点最多有M个子节点。
- B+树：B树的变种，所有数据都存储在叶子节点，并且叶子节点通过指针链接成有序链表。这是现代关系型数据库（如MySQL）索引的标准结构，非常适合范围查询。
5. 其他特殊用途的树
- 字典树（Trie）：专门用于处理字符串。利用字符串的公共前缀来节省存储空间，并实现快速查找、前缀匹配。常用于搜索引擎、拼写检查。
- 堆：一种特殊的完全二叉树，满足堆序性质（父节点值总大于/小于子节点值）。用于实现优先队列和堆排序。
- 线段树 & 树状数组：用于高效处理数组区间查询和更新问题（如区间求和、求最值）。
三、树的遍历
遍历是树操作的基础，分为深度优先遍历和广度优先遍历。
深度优先遍历（DFS）
按深度方向一直往下走，通常使用递归或栈实现。
- 前序遍历：根 -> 左 -> 右
- 应用：复制树的结构、计算前缀表达式。
- 中序遍历：左 -> 根 -> 右
- 应用：在BST中得到升序序列。
- 后序遍历：左 -> 右 -> 根
- 应用：释放树的内存、计算后缀表达式。
广度优先遍历（BFS）
按层次从上到下、从左到右遍历，使用队列实现。
- 层序遍历：访问每一层的所有节点。
- 应用：按层级处理数据，求树的最小深度/宽度。
四、重要性与应用总结
树结构是计算机科学的基石之一，其应用无处不在：
- 文件系统：目录和文件的层级结构就是一棵树。
- 数据库索引：B+树是关系数据库索引的核心。
- 高效搜索：BST、AVL、红黑树用于实现有序映射和集合。
- 编译器：语法分析生成抽象语法树。
- 路由算法：网络路由协议中的决策树。
- 机器学习：决策树算法直接以树作为模型。