1、存储方式双亲表示法 一维数组只用一个 parent[] 数组就能实现不用链表、不用二叉树2、数组含义parent[i]表示下标为 i 的结点双亲结点下标规则普通结点parent[i] 父节点编号根结点集合代表parent[i] -13、结构特点一棵树 一个互不相交的集合父结点指向祖先最终汇聚到根结点数组顺序存储实现简单、查找极快天然树形结构父子关系清晰4、举例数组下标 0 1 2 3 4parent-1 0 0 2 2含义0 是根1、2 父是 03、4 父是 25、两大优化存储配套路径压缩查找时修改数组内容让结点直接指向根树变扁平按秩合并高度 / 大小数组额外开一个 rank[] 数组记录树高度 / 结点个数合并时小树挂大树不让树长高6、总结并查集 一维双亲数组根节点标记parent[i] -1不相交集合森林每棵树独立空间复杂度O(n)