树是计算机编程中最重要、最核心的一种数据结构。
在日常生活中，树状结构也是广泛存在的，例如家族的族谱、公司部门结构图等。在计算机编程中，树更是无处不在，你平时接触到的二叉查找树、堆、并查集、线段树、树状数组、前缀树、红黑树，这些都是属于树这种数据结构的一种。
- 数据库索引就是 B+ 树
- 编译器的语法树
- 操作系统的文件系统
基本概念
- 节点：是树的基本单位，一棵树就是由一个一个节点组成的。
- 根节点：整颗树的顶端节点，它上面没有父节点。
- 父节点：一个节点的上一级节点。
- 子节点：一个节点派生出来的节点，只计算下一层。例如 A 节点的子节点就是 B、C，C节点的子节点就是 E、F
- 兄弟节点：具备相同父节点的节点互称为兄弟节点。
- 叶子节点：没有子节点的节点，称之为叶子节点，位于树的末端。
- 深度：就是有多少层。上图中深度为 4，因为一共有 4 层。
- 度：一个节点的子节点的个数称之为度。A 节点的度就为 2，D 节点的度为 3，C 节点的度也为 2.
树的表示法
-
图形表示法
-
符号表示法：用小括号先将根节点放入到括号里面，然后将子节点从左往右放入括号，对子节点的子节点也采用相同的方式。同层的子节点使用逗号隔开。
(A(B(D(G, H, I)), C(E(J), F)))
树的分类
二叉树
- 定义：每个节点最多有 2 个子节点（左、右子节点）。
- 变种：
- 满二叉树：所有非叶子节点均有 2 个子节点，且所有叶子在同一层。
- 完全二叉树：除最后一层外，其他层均满，且最后一层节点左对齐。
- 二叉搜索树(Binary Search Tree)：左子树所有节点值 < 根节点值 < 右子树所有节点值。用于快速查找、插入、删除
- 平衡二叉搜索树：通过旋转操作保持树高平衡，确保操作效率稳定在
O(logn)。常见类型：- AVL树：严格平衡（左右子树高度差 ≤ 1），适合读密集型场景。
- 红黑树：弱平衡（通过颜色标记规则），插入删除效率更高，广泛应用于系统级代码。
- Treap：结合 BST 和堆特性，随机优先级保证平衡。
- 伸展树(Splay Tree)：通过“伸展”操作将最近访问节点移至根，适合局部性访问。
多叉树
多叉树也存在多种类型：
-
B 树(B-Tree)：每个节点可包含多个键和子节点，所有叶子在同一层。常用于数据库索引、文件系统
-
B+ 树：针对 B 树的一种优化，非叶子节点仅存键，数据全存储在叶子节点，叶子节点通过指针链接。
-
字典树(Trie)： 每个节点存储字符，路径构成字符串，叶子节点标记单词结束。前缀匹配高效，常用于自动补全、拼写检查、IP路由表。
特殊用途树
-
堆(Heap)：一种完全二叉树，满足堆性质（最大堆/最小堆）
-
线段树(Segment Tree)：每个节点代表一个区间，支持区间查询与更新。常用于动态范围统计，例如区间最值、区间和。
-
哈夫曼树(Huffman Tree)： 构造带权路径最短的二叉树，用于无损数据压缩。常用于 zip 压缩、jpeg 编码。
-
并查集(Union-Find)： 森林表示集合，支持合并与查找操作。常用于连通性问题，例如社交网络好友关系。
-
KD树(K-Dimensional Tree)：二叉树，交替按不同维度划分空间。常用于多维数据近邻搜索，例如地理坐标查询的场景。
其他变种
-
二叉线索树(Threaded Binary Tree)： 利用空指针记录前驱/后继，加速遍历（中序、先序、后序）。
-
后缀树(Suffix Tree)：压缩字典树，存储字符串所有后缀。常用于模式匹配、生物信息学中 DNA序列分析等场景。
-
决策树(Decision Tree)：机器学习中的分类与回归模型，通过树结构划分特征空间。
-EOF-
