树、森林——树与二叉树的应用（并查集的存储结构）

1、存储方式
双亲表示法 + 一维数组只用一个 parent[] 数组就能实现，不用链表、不用二叉树

2、数组含义
parent[i]：表示下标为 i 的结点双亲结点下标
规则
普通结点：parent[i] = 父节点编号
根结点（集合代表）：parent[i] = -1

3、结构特点
一棵树 = 一个互不相交的集合
父结点指向祖先，最终汇聚到根结点
数组顺序存储，实现简单、查找极快
天然树形结构，父子关系清晰

4、举例数组
下标： 0 1 2 3 4parent：-1 0 0 2 2
含义：
0 是根
1、2 父是 0
3、4 父是 2

5、两大优化存储配套
路径压缩
查找时修改数组内容，让结点直接指向根，树变扁平
按秩合并（高度 / 大小数组）
额外开一个 rank[] 数组，记录树高度 / 结点个数
合并时小树挂大树，不让树长高

6、总结
并查集 = 一维双亲数组
根节点标记：parent[i] = -1
不相交集合森林，每棵树独立
空间复杂度：O(n)