1 基本概念
1.1 节点与边
树形结构由有限个节点（Node）和连接节点的边（Edge）组成。节点是数据元素，边表示节点之间的层次关系。在一棵树中，任意两个节点之间只有一条唯一的路径相连。
1.1.1 根节点、父节点、子节点
- 根节点（Root）：一棵树中唯一没有父节点的节点，是整个树的起始点。
- 父节点（Parent）：若节点A通过一条边直接指向节点B，则A是B的父节点。
- 子节点（Child）：与父节点相对，B是A的子节点。每个节点可以有零个或多个子节点。
1.1.2 叶子节点与内部节点
- 叶子节点（Leaf）：没有子节点的节点，也称为终端节点。
- 内部节点（Internal Node）：至少有一个子节点的节点，根节点如果非叶子也算内部节点。
1.2 树的术语
1.2.1 度（Degree）与深度（Depth）
- 度：一个节点的子节点个数称为该节点的度。树中所有节点的最大度称为树的度。
- 深度（Depth）：从根节点到该节点的唯一路径上的边数。根节点的深度为0。
1.2.2 高度（Height）与层（Level）
- 高度（Height）：从该节点到其最远叶子节点的路径上的边数。叶子节点的高度为0。树的高度即为根节点的高度。
- 层（Level）：有时与深度同义，但常从1开始计数：根节点在第1层。深度和层数在不同文献中定义略有差异，但核心均反映层次顺序。
1.3 树的表示方法
1.3.1 父子链表表示
每个节点存储自身数据以及指向所有子节点的指针列表（或数组）。适用于子节点数量确定的静态树，例如完全二叉树可用数组表示：节点i的左子节点为2i+1，右子节点为2i+2。
1.3.2 孩子兄弟表示法
每个节点包含三个部分：数据、指向第一个子节点的指针、指向下一个兄弟节点的指针。此法可将任意多叉树转化为二叉树，便于统一处理。实际上是树与二叉树之间的桥梁。
2 树的分类
2.1 按子节点数量
2.1.1 二叉树（Binary Tree）
每个节点最多有两个子节点（左孩子、右孩子）的树。是计算机科学中最基础的树形结构。
2.1.1.1 满二叉树与完全二叉树
- 满二叉树：所有叶子节点在同一层，且每个内部节点都有两个子节点。节点数满足 \(2^{h+1}-1\)，其中h为树的高度。
- 完全二叉树：除了最后一层外，其余层都被填满，且最后一层的节点尽可能靠左。堆（Heap）通常用完全二叉树实现。
2.1.2 多叉树（N-ary Tree）
每个节点可有任意数量的子节点。如文件系统的目录、家谱图等。常见特例为三叉树、四叉树等。
2.2 按结构特点
2.2.1 二叉搜索树（BST）
左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。支持高效查找、插入和删除，平均时间复杂度为O(log n)，但极端情况（如有序插入）会退化为链表。
2.2.2 平衡二叉树（AVL树、红黑树）
为了防止二叉搜索树退化为链表，平衡二叉树通过旋转等操作保持左右子树高度差不超过某个阈值。AVL树要求高度差不超过1，严格平衡；红黑树通过颜色约束和旋转，保证最长路径不超过最短路径的两倍，是许多语言标准库中平衡树的实现基础。
2.2.3 堆（Heap）——一种特殊的树
堆是一种完全二叉树，且满足堆序性质：最大堆中父节点值大于等于子节点，最小堆则相反。常用于实现优先队列，插入和删除操作的时间复杂度为O(log n)。
2.3 按用途分类
2.3.1 哈夫曼树（Huffman Tree）
又称最优二叉树，用于无损数据压缩。通过将频率最高的字符放在离根最近的位置，实现最短的编码平均长度。构建过程每次合并两个权值最小的节点。
2.3.2 线段树（Segment Tree）
用于高效处理区间查询和更新问题，如区间和、区间最大值等。其每个节点代表一个区间，子节点分别代表左右半区间。适合静态序列的多次区间操作。
2.3.3 字典树（Trie）
又称前缀树，用于存储字符串集合。每个节点代表一个字符（或路径），从根到某个节点的路径表示一个字符串。常用于搜索引擎的自动补全、拼写检查。
3 基本操作与算法
3.1 树的遍历
3.1.1 深度优先遍历（DFS）
沿着树的深度遍历，尽可能深地访问子树，遇到叶子后退。实现通常借助递归或栈。
3.1.1.1 前序遍历
访问顺序：根节点 → 左子树 → 右子树。常用于复制树、打印树的结构。
3.1.1.2 中序遍历
访问顺序：左子树 → 根节点 → 右子树。在二叉搜索树中，中序遍历得到升序序列。
3.1.1.3 后序遍历
访问顺序：左子树 → 右子树 → 根节点。常用于删除树或计算表达式树的值。
3.1.2 广度优先遍历（BFS）/层序遍历
按层从上到下、从左到右依次访问节点。常用队列实现，可用于求树的最大宽度、判断完全二叉树等。
3.2 插入与删除节点
3.2.1 在二叉搜索树中插入
从根开始比较，若键值小于当前节点则向左，否则向右，直到找到空位置插入。插入操作不破坏二叉搜索树性质，但可能导致不平衡。
3.2.2 删除节点并保持平衡
删除二叉搜索树节点时分三种情况：叶子节点直接删除；只有一棵子树的节点用子树替代；有两棵子树的节点通常用中序后继（或前驱）替代，然后递归删除该后继。对于平衡树（如红黑树），还需执行颜色调整和旋转以恢复平衡。
3.3 树的构造与重建
3.3.1 已知遍历序列还原树
给定一棵二叉树的前序和中序遍历序列（或后序和中序），可以唯一确定该树。通过递归划分子序列构建根节点及左右子树。若只给前序和后序，一般无法唯一重建（除非树是满二叉树）。
3.3.2 列表/数组转树
常见于多叉树场景，例如给定父节点ID列表，可将扁平数据转换成树形结构。算法利用哈希表映射节点ID，逐步为每个节点添加子节点，最后返回根节点列表。
4 树形结构的实际应用
4.1 文件系统与目录树
操作系统中的文件系统使用树形目录组织文件。每个目录节点包含文件或子目录，根目录为“/”（Unix）或盘符（Windows）。路径遍历本质是树形结构的深度优先搜索。
4.2 数据库索引
4.2.1 B树与B+树
B树是一种多路平衡搜索树，每个节点可包含多个键和多个子节点，广泛应用于磁盘数据库的索引。B+树是B树的变体，所有数据都存储在叶子节点，且叶子节点通过指针形成链表，便于范围查询。MySQL的InnoDB引擎使用B+树作为主键索引。
4.2.2 R树（空间索引）
R树用于多维空间数据索引，如地理信息系统中点的位置、矩形区域。每个节点对应一个最小边界矩形（MBR），子节点MBR包含在其父节点MBR内，支持空间搜索和最近邻查询。
4.3 编程语言与编译
4.3.1 抽象语法树（AST）
编译器将源代码解析为抽象语法树，每个节点对应一种语法结构（如函数定义、变量声明、运算符）。AST是代码分析、优化和生成的中间表示，也用于IDE的语法高亮和错误检查。
4.3.2 JSON/XML的树形解析
JSON和XML数据结构天然是树形（键值对嵌套或标签嵌套）。解析器将其转化为内存中的树形对象，如JSON对象树或DOM节点树，方便程序遍历和修改。
4.4 前端与UI表现
4.4.1 DOM树与虚拟DOM
浏览器将HTML文档解析为文档对象模型（DOM）树，每个HTML标签对应一个节点，JavaScript可以操作DOM树动态修改页面。虚拟DOM（如React中的）是DOM树的轻量级JavaScript副本，通过比较新旧虚拟DOM的差异来最小化实际DOM操作，提高性能。
4.4.2 树形控件（TreeView）
UI组件（如文件浏览器、组织架构图）中常见的树形展示，节点可展开或折叠。实现通常基于递归渲染，每个节点包含子节点列表。
4.5 算法与数据结构衍化
4.5.1 并查集（Union-Find）中的树
并查集用树表示集合，每个节点指向其父节点。合并操作将一棵树的根指向另一棵，并通过路径压缩优化（将沿途节点直接连到根），使得树几乎扁平，查询效率接近常数。
4.5.2 决策树与随机森林
决策树是机器学习中用于分类和回归的树形模型，每个内部节点代表一个特征判断，叶子节点代表预测结果。随机森林是通过集成多个决策树（每棵树随机选择特征和数据子集）来提升准确性和稳定性，是典型的集成学习方法。
5 常见面试题与“梗”
5.1 经典代码题：翻转二叉树（Homebrew作者之梗）
翻转二叉树是指交换每个节点的左右子树。此问题因2015年苹果面试Homebrew作者Max Howell时被问及，Max未能答出，遂被拒绝。随后他发推吐槽，该题迅速成为程序员圈内名梗。解法简单：递归交换左右子节点。有趣的是，翻转后的二叉树仍然是二叉树，只是镜像对称。
5.2 树与递归的爱恨情仇：尾递归优化
树的深度优先遍历几乎天然适合递归写法，代码简洁优雅。但递归可能导致栈溢出（尤其是树高很大时）。尾递归优化（TCO）能被某些编译器识别，将递归转化为迭代，节省栈空间。然而大多数语言（如Python、Java）默认不进行TCO，因此面试时常要求写出非递归版本（如使用栈模拟）。
5.3 另类树：圣诞树（纯娱乐）与程序员的浪漫
程序员们用代码“画”圣诞树是一种节日传统。常见方式是用循环打印字符组成圣诞树的形状，或者用递归绘制分形树。更浪漫的是用树数据结构储存情话，写成二叉树“情书”，例如“左节点是‘我’，右节点是‘你’，根节点是‘爱’”——虽然逻辑上不够严谨，但充满程序员的幽默感。这些“另类树”虽无实际学术价值，却折射出开发者对树形结构的亲切与创造力。