一、树的概念
1.1 树的定义
树型结构是一类重要的非线性数据结构。
- 有一个特殊的结点，称为根结点，根结点没有前驱结点。
- 除根结点外，其余结点被分成 k 个互不相交的集合，其中每一个集合又是树，称这棵树为根节点的子树。
- 结论：树是递归定义的
1.2 树的基本术语
- 结点的度：树中一个结点孩子的个数称为该结点的度。
- 树的度：树中结点最大的度数称为树的度。
- 树的高度（深度）：树中结点的最大层数称为树的高度 (深度)。
- 路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，路径长度为序列中边的个数（且为最短路）。
1.3 有序树和无序树
- 有序树：结点的子树按照从左往右的顺序排列，不能更改。
- 无序树：结点的子树之间没有顺序，随意更改。
1.4 有根树和无根树
- 有根树：树的根节点已知，是固定的。
- 无根树：树的根节点未知，谁都可以是根结点。
注：这个认知主要会影响我们对于树的存储。在存储树结构的时候，最重要的就是要存下逻辑关系。如果是无根树，父子关系不明确，此时我们需要把所有的情况都存下来。如 a 和 b 之间有一条边，我们不仅要存 a 有一个孩子 b，也要存 b 有一个孩子 a。（有时有根树也需要这样存储）
二、树的存储
树结构相对线性结构来说就比较复杂。存储时，既要保存值域，也要保存结点与结点之间的关系。实际中树有很多种存储方式：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。现阶段，只要掌握孩子表示法，学会用孩子表示法存储树，并且在此基础上遍历整棵树。后续会在并查集中学习双亲表示法。至于其它存储形式，在学习算法阶段不要求掌握。
2.1 孩子表示法
孩子表示法是将每个结点的孩子信息存储下来。 如果是在无根树中，父子关系不明确，我们会将与该结点相连的所有点都存储下来。
2.2 实现方式
2.2.1 vector 数组实现
2.2.1.1 方法解析
vector 是可变长数组，如果只涉及尾插，效率还是可以的。而树结构这种一对多的关系，正好可以利用尾插，把所有的关系全部存起来。
- 因此，可以创建一个大小为 n + 1 的 vector 数组 edges[n + 1]。
- 其中 edges[i] 里面就保存着 i 号结点所连接的结点。
2.2.1.2 代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector<int> edges[N];
int main {
n;
cin >> n;
( i = ; i < n; i++) {
a, b;
cin >> a >> b;
edges[a].(b);
edges[b].(a);
}
;
}
