1 定义与基本概念
1.1 树的数学定义
在图论中，树（Tree）被定义为一个连通且无环的无向图。形式化地，树是一个由有限个节点（Vertex）和连接节点的边（Edge）组成的结构，满足：任意两个节点之间有且仅有一条简单路径，且边的数量等于节点数减一。在计算机科学中，树通常指有根树（Rooted Tree），即指定一个特殊节点为根。
1.2 基本术语
1.2.1 根节点与叶子节点
根节点（Root）是树中唯一没有父节点的节点，通常作为遍历的起点。叶子节点（Leaf）是树中没有子节点的节点，位于树的末端。
1.2.2 父节点、子节点与兄弟节点
在树中，若节点A通过一条边直接连接到节点B，且A更靠近根节点，则称A为B的父节点（Parent），B为A的子节点（Child）。具有相同父节点的多个子节点互称为兄弟节点（Sibling）。
1.2.3 节点的度与树的深度
节点的度（Degree）是指该节点拥有的子节点数量。树的度是所有节点中最大的度。树的深度（Depth）或高度（Height）是指从根节点到最远叶子节点的路径上的边数（或节点数，依定义而异）。根节点的深度通常定义为0。
2 树的分类
2.1 二叉树
二叉树（Binary Tree）是每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。二叉树是树结构中最基本且最常用的类型。
2.1.1 二叉搜索树
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，满足对于任意节点，其左子树中所有节点的值小于该节点的值，右子树中所有节点的值大于该节点的值。这种性质使得查找、插入和删除操作的平均时间复杂度为O(log n)。
2.1.2 平衡二叉树
平衡二叉树（Balanced Binary Tree）是为了避免二叉搜索树退化为链表而设计的，通过保持树的高度平衡来保证操作效率。常见平衡二叉树包括AVL树和红黑树。
2.1.2.1 AVL树
AVL树是最早提出的自平衡二叉搜索树，其任何节点的左右子树高度差（平衡因子）不超过1。通过旋转操作（左旋、右旋、左右旋、右左旋）来维持平衡，确保查找、插入和删除的时间复杂度为O(log n)。
2.1.2.2 红黑树
红黑树（Red-Black Tree）是一种近似平衡的二叉搜索树，通过节点颜色的约束（红或黑）以及旋转和变色操作来维持平衡。它保证了最长路径不超过最短路径的两倍，广泛应用于C++ STL的map和set、Java的TreeMap等。
2.2 多路树
多路树（Multi-way Tree）允许每个节点有多个子节点，通常用于磁盘存储和数据库索引以减少树的高度。
2.2.1 B树
B树（B-Tree）是一种平衡的多路搜索树，节点可以包含多个键和多个子节点。所有叶子节点位于同一层，内部节点的键用于分割子树范围。B树通过合并和分裂节点来保持平衡，适合读写大规模数据的场景。
2.2.2 B+树
B+树是B树的变体，内部节点仅存储键作为路由信息，所有数据（或指向数据的指针）存储在叶子节点中。叶子节点通过链表相连，便于范围查询。B+树是主流数据库索引（如MySQL的InnoDB引擎）的默认数据结构。
2.3 堆
堆（Heap）是一种特殊的完全二叉树，常用于实现优先队列。堆中每个节点的值满足堆序性质：最大堆中父节点值大于等于子节点值，最小堆中父节点值小于等于子节点值。
2.3.1 最大堆与最小堆
最大堆（Max-Heap）的根节点存储最大值，任意子树的根节点都大于等于其子节点。最小堆（Min-Heap）则相反，根节点存储最小值。堆常用于堆排序和动态优先级管理。
2.3.2 堆的存储与操作
堆通常采用数组顺序存储，利用索引关系快速定位父节点和子节点（对于索引i的节点，左子节点为2i+1，右子节点为2i+2，父节点为(i-1)/2）。基本操作包括插入（上浮）和删除根节点（下沉），时间复杂度均为O(log n)。
3 树的遍历
3.1 深度优先遍历
深度优先遍历（Depth-First Search, DFS）沿着一条路径尽可能深入，直到无法继续再回溯。根据访问根节点的次序，分为三种：先序、中序、后序。
3.1.1 先序遍历
先序遍历（Preorder Traversal）的访问顺序为：根节点 → 左子树 → 右子树。常用于复制树或输出树的结构。
3.1.2 中序遍历
中序遍历（Inorder Traversal）的访问顺序为：左子树 → 根节点 → 右子树。在二叉搜索树中，中序遍历可得到有序序列。
3.1.3 后序遍历
后序遍历（Postorder Traversal）的访问顺序为：左子树 → 右子树 → 根节点。常用于删除树或计算表达式树的值。
3.2 广度优先遍历（层序遍历）
广度优先遍历（Breadth-First Search, BFS）按层次从上到下、从左到右依次访问节点。通常借助队列实现，用于计算树的宽度或寻找最短路径。
4 树的存储与表示
4.1 链式存储结构
链式存储通过节点对象（包含数据域和指向子节点的指针）来表示树。二叉树节点通常包含左指针和右指针；多路树节点则使用指针数组。链式结构灵活，便于动态插入和删除，但占用较多内存。
4.2 顺序存储结构（数组表示）
顺序存储将树的节点按某种顺序（如层序）存放在连续数组中。对于完全二叉树，可以通过索引直接计算父子关系。该方法节省指针开销，但插入和删除操作成本较高，适用于堆等静态结构。
5 树的应用
5.1 文件系统与目录结构
操作系统中的文件系统采用树形目录结构，根目录（如“/”或“C:\”）作为根节点，子目录和文件作为子节点。这种结构支持路径解析和权限管理。
5.2 编译器中的抽象语法树
编译器在语法分析阶段将源代码解析为抽象语法树（Abstract Syntax Tree, AST），树的节点对应语言结构（如表达式、语句、函数），便于后续语义分析和代码生成。
5.3 数据库索引（B树与B+树）
数据库系统使用B树或B+树作为索引结构，以支持高效的范围查询和点查询。B+树的顺序叶子链表特别适合范围扫描，是现代关系型数据库的核心组件。
5.4 表达式树与决策树
表达式树（Expression Tree）将算术表达式表示为树，叶子节点为操作数，内部节点为运算符，可用于求值和符号计算。决策树（Decision Tree）是机器学习中的分类和回归模型，内部节点表示特征判断，叶子节点表示结果。