在数据结构的世界里，树（Tree） 是一种极其重要的非线性结构，它完美模拟了自然界中树的层次关系，从文件系统、组织结构，到算法中的二叉搜索树、堆，再到 AI 中的决策树，树的身影无处不在。今天我们就从零开始，彻底搞懂树的定义、核心术语和关键性质，帮你打下坚实的算法基础。

---

一、树的定义：什么是树？

树是n（n≥0）个结点的有限集合，满足两个核心条件：

1. 有且仅有一个根结点（Root）：这是树的起点，没有双亲结点；
2. 其余结点可分为 m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树，称为根结点的子树。

简单来说，树是一种一对多的层次结构，和线性表（一对一）、图（多对多）有本质区别。

• 当 n=0 时，称为空树；
• 树中不存在回路，任意两个结点之间有且仅有一条路径；
• 一棵有 n 个结点的树，恰好有n-1 条边，这是树最基础的特征之一。

---

二、树的核心术语：一张图看懂所有概念

1. 结点间的基础关系

术语	定义	示例（以图中树为例）
双亲（父结点）	某个结点的直接前驱结点	B、C、D 的双亲是 A，L、M 的双亲是H
孩子（子结点）	某个结点的直接后继结点	D 的孩子是 H、I、J，B 的孩子是 E、F
兄弟结点	同一个双亲的孩子结点	B、C、D 互为兄弟，L、M 互为兄弟
祖先结点	从根结点到该结点所经分支上的所有结点	K 的祖先为 A、B、F
子孙结点	以某结点为根的子树中的所有结点	D 的子孙为 H、I、J、L、M

2. 结点与树的属性

术语	定义	示例
结点的度	该结点拥有的孩子（子结点）的个数	D 的度为 3，A 的度为 3，E 的度为 0
叶结点（终端结点）	度为 0 的结点，没有孩子	E、G、K、L、M、I、J 都是叶结点
分支结点（非终端结点）	度大于 0 的结点	A、B、C、D、F、H 都是分支结点
树的度	树中所有结点的度的最大值	本树中结点最大度为 3，因此树的度为 3
结点的深度	结点所在的层次（根结点深度为 1）	A 深度 1，B 深度 2，K 深度 4
结点的高度	以该结点为根的子树的层数（叶结点高度为 1）	K 高度 1，B 高度 3，A 高度 4
树的高度 / 深度 / 层数	树中结点的最大深度（等于根结点的高度）	本树高度为 4，深度为 4，层数为 4
路径与路径长度	两个结点之间的结点序列，路径长度为经过的边数	A→D→H→L 的路径长度为 3
有序树 / 无序树	有序树：子树从左到右有顺序，不可互换；无序树：子树无顺序	二叉树是典型的有序树
森林	m（m≥0）棵互不相交的树的集合	把根结点 A 删除，B、C、D 为根的三棵树就构成森林

3. 特殊树：度为 m 的树 vs m 叉树

对比项	度为 m 的树	m 叉树
相同点	树中所有结点的度最多为 m	树中所有结点的度最多为 m
不同点	至少有一个结点的度等于 m；是对现有树的描述	所有结点的度可以都小于 m，甚至可以是空树；是对树结构的约束
示例	度为 3 的树：必须有一个结点度为 3，其余≤3	三叉树：所有结点度≤3 即可，允许全树结点度都小于 3

---

三、树的关键性质

性质 1：结点数、边数、度数的核心关系

这是树最基础、最常用的性质：

• 总边数 = 总结点数 - 1（n 个结点的树有 n-1 条边）
• 总结点数 = 所有结点度数之和 + 1（根结点没有双亲，度数和仅统计孩子数）
• 若设n0​为叶结点数，n1​为度 1 的结点数，n2​为度 2 的结点数…nm​为度 m 的结点数，则：n=n0​+n1​+n2​+...+nm​n=(0⋅n0​+1⋅n1​+2⋅n2​+...+m⋅nm​)+1

示例：一棵度为 4 的树 T 中，有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，求叶结点数n0​。

• 总度数和 = 20×4+10×3+1×2+10×1=80+30+2+10=122
• 总结点数n=122+1=123
• 又n=n0​+10+1+10+20=n0​+41
• 因此n0​=123−41=82

性质 2：m 叉树的结点数上限

对于m 叉树（或度为 m 的树）：

• 第i层最多有个结点（根结点在第 1 层，i≥1）
• 高度为h的 m 叉树，最多有个结点（等比数列求和：m0+m1+...+mh−1）

---

性质 3：高度为 h 的树的结点数范围

• 高度为 h 的 m 叉树：最少有h个结点（每层 1 个结点，形成单链），最多有个结点（满 m 叉树）
• 高度为 h 的度为 m 的树：最少有h−1+m个结点（前h−1层每层 1 个，最后一层m个结点，保证有一个结点度为 m），最多同样是​个结点

性质 4：n 个结点的 m 叉树的高度范围

• 最小高度：⌈logm​(n(m−1)+1)⌉（等价于⌈logm​(n−1)+1⌉），对应完全 m 叉树的高度
  • 推导：满 m 叉树结点数m−1mh−1​≥n，解得h≥logm​(n(m−1)+1)，向上取整
• 最大高度：n（m 叉树允许所有结点度≤m，形成单链，高度为 n）
• 度为 m 的树的最大高度：n−m+1（必须有一个结点度为 m，因此前n−m层每层 1 个，最后一层m个结点）

四、树的应用场景：为什么树如此重要？

树的层次结构完美适配了现实中的很多场景：

1. 文件系统：电脑的文件夹结构就是典型的树，根目录是根结点，子文件夹是子结点，文件是叶结点；
2. 组织结构：公司的部门架构、家族族谱，都是树的层次关系；
3. 算法结构：二叉搜索树、平衡二叉树、堆、B 树、红黑树，是数据库索引、排序算法的核心；
4. AI 与机器学习：决策树、随机森林，用树结构做分类与回归；
5. 编译原理：语法分析树，用于解析代码的语法结构。

---

五、总结：树的核心知识点速记

类别	核心要点
定义	n 个结点的层次结构，n-1 条边，无回路，唯一根结点
关键术语	度、叶结点、分支结点、深度、高度、路径、有序树、森林
核心性质	总结点数 = 度数和 + 1；m 叉树第 i 层最多mi−1个结点；高度 h 的 m 叉树最多m−1mh−1​个结点
易混点	度为 m 的树≠m 叉树；结点深度≠结点高度

---

六、思考题（检验学习效果）

1. 一棵二叉树有 10 个度为 2 的结点，5 个度为 1 的结点，求叶结点数？
2. 一棵高度为 4 的三叉树，最多有多少个结点？最少有多少个结点？
3. 100 个结点的三叉树，最小高度是多少？

（答案：1. 11；2. 最多 40 个，最少 4 个；3. 5）