3.6 树、森林和并查集[图文详解]

树的定义与术语

树的定义：一棵树T是由一个或一个以上结点组成的有限集，其中有一个特定的结点R称为T的根结点。集合(T-{R}）中的其余结点可被划分为n>=0个不相交的子集T、T2、…、Tn，其中每个子集都是树，并且其相应的根结点R1、R2、 … 、Rn是R的子结点。

子集T(1≤ i ≤n）称为树T的子树(subtree)

结点的出度(out degree）定义为该结点的子结点的数目

森林的定义：零个或多个树的一个有序集合

树结点ADT

public interface GTNode {//树结点ADTObject value();boolean isLeaf();GTNode getParent();GTNode getLeftMostChild();GTNode getRightSibling();void setValue(Object value);void setParent(GTNode parent);void insertFirst(GTNode first);void insertNext(GTNode next);void removeFirst();void removeNext();
}

树的遍历

跟二叉树的遍历类似

前序周游：先访问结点，后访问其子结点。上图前序周游的结果为ABCFGDEH

/*** 从根结点开始先序遍历* @param rt 根结点*/
private static void preOrder(GTNode rt){if (rt==null)return;visit(rt);GTNode temp = rt.getLeftMostChild();while (temp!=null){preOrder(temp);temp = temp.getRightSibling();}
}

后序周游：先访问结点的子结点（包括他们的子树），然后再访问该结点。上图二叉树经过后序周游枚举出来的结果为：BFGCDHEA

/*** 从根结点开始后序遍历* @param rt 根结点*/
private static void postOrder(GTNode rt){if (rt==null)return;GTNode temp = rt.getLeftMostChild();while (temp!=null){postOrder(temp);temp = temp.getRightSibling();}visit(rt);
}

树的实现

父指针表示法

每个结点只保存一个指针域指向其父结点

适用的应用：等价类问题的处理（并查集）

缺点：对找到一个结点的最左子结点或右侧兄弟结点这样的重要操作是不够的

数组实现形式

链表实现方式

子结点表表示法

每个结点存储一个线性表的指针，该线性表用来存储该结点的所有子结点

优势：寻找某个结点的子结点非常方便

缺点：寻找某个结点的兄弟结点比较困难

数组实现形式

链表实现方法1

链表实现方式2

左子结点/右兄弟结点表示法

每个结点都存储结点的值、最左子结点的位置和右侧兄弟结点的位置

优点：ADT中规定的基本操作都可以较为容易的实现

数组实现方式

链表实现方式

这种表示方式和二叉树的链表表示方式在物理结构上是一致的

森林和二叉树的转换关系

将森林中的根节点连接起来，并且将每个结点的子结点之间连接起来，最后去掉除每个结点与最左子结点之间的连接线之外的其余连线

结论：任何二叉树都对应一个唯一的森林

根结点加左子树对应第一棵树，右子树对应新的森林构成的树，以次递归定义

设F=(T1，T2，T3，…Tn,)是树的一个森林，对应于F的二叉树B(F)的严格定义如下：

如果n=0，则B(F)为空

如果n#0，则B(F)的根是$root(T_1)$; B(F)的左子树是$B(T_{11}，T_{12}....T_{1m})$，其中$T_{11}，T_{12}....T_{1m}$是$T_1$树的子树:B(F)的右子树是$B(T_2,T_3.....T_n)$

森林的遍历

将树的根去掉之后，就成为了森林，所以树和森杯的遍历本质是和同的

深度优先后根遍历

1️⃣ 若森林$F=\varnothing$，返回

2️⃣ 否则后根遍历森林F第一棵树的根结点的子树森林$T_{11}，T_{12}....T_{1m}$

3️⃣ 访问森林F第一棵树的根结点r1

4️⃣ 后根遍历森林中除第一棵树外其他树组成的森林$T_2,T_3.....T_n$

广度优先遍历

1️⃣ 若森林F为空，返回
2️⃣ 否则依次遍历各棵树的根结点
3️⃣ 依次遍历各棵树根结点的所有子女
4️⃣ 依次遍历这些子女结点的子女结点

不相交集ADT（并查集）

不相交集合：是由一组互不相交的集合组成的一个集合结构，并在此集合上定义了运算Union和Find

每一个要处理的元素都仅仅属于一个集合

集合之间是不相交的

一开始，每个集合包含一个元素

每一个集合都有一个名称,这个名称可以用该集合中的任何一个元素名称

用途：主要用来解决等价问题

若对于每一对元素(a，b) , a和b之间满足如下三种关系，则称a和b之间是等价关系

1️⃣ 自反性: aRa

2️⃣ 对称性: aRb当且仅当bRa

3️⃣ 传递性:若aRb且bRc则aRc

生活中的等价关系：电器连通性、城市之间的连通性等

需要支持的两个操作

Find(elementname)

返回包含给定元素的集合名字

不同于查找方式中的返回结果

Union(elementname1,elementname2)

生成一个新的集合，该集合是elementname1所属的集合set1和lelementname2所属的集合set2的并集

实现方式

使用数组

由一个具有n个元素组成的数组储存各个不相交的集合

初始状态:每个元素都隶属于一个集合，该集合的名字就是该元素在数组中的下标：set[i]=i

Union(i,j): 对每一个k，如果set[k]==下标为j的元素所属的集合名称，则设置set[k]=下标为i的元素所属的集合名称
Find(i): 返回set[i]即可

每个find操作的时间复杂性为O(1)，每个union操作的时间复杂性为O(N)，那么做N次union操作的时间复杂性就是O(N^2)

public class UnionFindArray {//用数组实现并查集public int[] set;/*** 初始化并查集，每个集合一个元素，其名称即元素值** @param N 元素总个数*/public void init(int N) {set = new int[N];for (int i = 0; i < N; i++) {set[i] = i;}}/*** 返回包含给定元素的集合名字** @param i 给定元素* @return 集合名字*/public int find(int i) {return set[i];}/*** 生成一个新的集合，该集合是i所属的集合set1和j所属的集合set2的并集** @param i* @param j*/public void union(int i, int j) {int setName1 = find(i);int setName2 = find(j);for (int k = 0; k < set.length; k++) {if (set[k] == setName2) {set[k] = setName1;}}}public void print() {for (int i = 0; i < set.length; i++) {System.out.print(set[i]+" ");}}public static void main(String[] args) {UnionFindArray test = new UnionFindArray();test.init(10);System.out.println("find(1): " + test.find(1));test.union(2,5);System.out.print("union(2,5): ");test.print();System.out.println();test.union(3,6);System.out.print("union(3,6): ");test.print();System.out.println();test.union(2,6);System.out.print("union(2,6): ");test.print();}
}

find(1): 1
union(2,5): 0 1 2 3 4 2 6 7 8 9 
union(3,6): 0 1 2 3 4 2 3 7 8 9 
union(2,6): 0 1 2 2 4 2 2 7 8 9 

使用树

不相交集合可以表示一个森林

森林中的每棵树表示为一个集合

树中每个结点的存放顺序没有任何约束，所以可以采用树的父指针表示法来描述树

🏷 树的实现还是采用数组这种物理形式

数组中的每个元素存储树中的每个结点，结点应该包含父指针信息和所存储的元素内容

public class GTNodeA {private int parent;//父结点private Object element;//存储元素内容public GTNodeA() {this(null, -1);}public GTNodeA(Object element) {this(element, -1);}public GTNodeA(Object element, int parent) {this.element = element;this.parent = parent;}public int getParent() {return parent;}public int setParent(int parent) {return this.parent = parent;}public Object getElement() {return element;}public void setElement(Object element) {this.element = element;}
}

代码实现

public class UnionFindTree {//用树实现并查集public GTNodeA[] set;public UnionFindTree(GTNodeA[] set) {this.set = set;}/*** 返回包含给定元素的集合名字** @param i 元素下标* @return 以根结点下标作为集合名字*/public int find(int i) {GTNodeA current = set[i];while (current.getParent() >= 0) {i = current.getParent();//将下标变为父结点的下标current = set[i];}//所需时间依赖于第i个元素在树中的层次return i;}/*** 生成一个新的集合，该集合是i所属的集合set1和j所属的集合set2的并集** @param i* @param j*/public void union(int i, int j) {int root1 = find(i);int root2 = find(j);if (root1 != root2) {set[root2].setParent(root1);//将其中一棵树的根结点的父结点设置为//另一棵树的根结点}}public void print() {for (int i = 0; i < set.length; i++) {System.out.print(set[i].getElement() + " ");}}public static void main(String[] args) {GTNodeA node_A = new GTNodeA("A");GTNodeA node_C = new GTNodeA("C");GTNodeA node_H = new GTNodeA("H");GTNodeA node_K = new GTNodeA("K");GTNodeA node_E = new GTNodeA("E", 0);GTNodeA node_B = new GTNodeA("B", 0);GTNodeA node_D = new GTNodeA("D", 0);GTNodeA node_F = new GTNodeA("F", 2);GTNodeA node_J = new GTNodeA("J", 10);GTNodeA node_L = new GTNodeA("L", 10);GTNodeA node_N = new GTNodeA("N", 10);GTNodeA node_M = new GTNodeA("M", 4);GTNodeA node_I = new GTNodeA("I", 3);GTNodeA node_G = new GTNodeA("G", 3);GTNodeA[] test = {node_A, node_B, node_C, node_D,node_E, node_F, node_G, node_H,node_I, node_J, node_K, node_L,node_M, node_N};UnionFindTree testTree = new UnionFindTree(test);System.out.print("initialized forest: ");testTree.print();System.out.println();System.out.println("find(4): "+testTree.find(4));System.out.println("find(5): "+testTree.find(5));testTree.union(0,2);System.out.print("union(0,2),find(5): "+testTree.find(5));}
}

initialized forest: A B C D E F G H I J K L M N 
find(4): 0
find(5): 2
union(0,2),find(5): 0

重量平衡原则

为了使union N个元素的时间复杂性降低到O(NlogN)，可以使用重量平衡原则

当两个集合合并的时候(也就是两棵树合并为棵树)，可以将结点数小的那棵树合并到结点数较多的那棵树上

统计结点数的巧妙方法

初始化时，每个结点的父结点下标都是-1，如A,B,C都是-1，合并AB以后，设A的父结点下标为-2，其绝对值则为以A为根结点的树的结点数

    /*** 生成一个新的集合，该集合是i所属的集合set1和j所属的集合set2的并集** @param i* @param j*/public void union(int i, int j) {int root1 = find(i);int num1 = set[root1].getParent();int root2 = find(j);int num2 = set[root2].getParent();if (num1 <= num2) {set[root1].setParent(num1+num2);set[root2].setParent(root1);//将其中结点数少的一棵树的根结点的父结点设置为//结点数多的一棵树的根结点} else {set[root2].setParent(num1+num2);set[root1].setParent(root2);//将其中结点数少的一棵树的根结点的父结点设置为//结点数多的一棵树的根结点}}

    public static void main(String[] args) {GTNodeA node_A = new GTNodeA("A");GTNodeA node_C = new GTNodeA("C");GTNodeA node_H = new GTNodeA("H");GTNodeA node_K = new GTNodeA("K");GTNodeA node_E = new GTNodeA("E");GTNodeA node_B = new GTNodeA("B");GTNodeA node_D = new GTNodeA("D");GTNodeA node_F = new GTNodeA("F");GTNodeA node_J = new GTNodeA("J");GTNodeA node_L = new GTNodeA("L");GTNodeA node_N = new GTNodeA("N");GTNodeA node_M = new GTNodeA("M");GTNodeA node_I = new GTNodeA("I");GTNodeA node_G = new GTNodeA("G");GTNodeA[] test = {node_A, node_B, node_C, node_D,node_E, node_F, node_G, node_H,node_I, node_J, node_K, node_L,node_M, node_N};UnionFindTree testTree = new UnionFindTree(test);System.out.print("initialized forest: ");testTree.print();System.out.println();System.out.println("find(1): " + testTree.find(1));System.out.println("find(3): " + testTree.find(3));System.out.println("find(4): " + testTree.find(4));testTree.union(0, 4);testTree.union(0, 1);testTree.union(0, 3);System.out.println("union(0,4), union(0,1), union(0,3)");System.out.println("find(1): " + testTree.find(1));System.out.println("find(3): " + testTree.find(3));System.out.println("find(4): " + testTree.find(4));}

initialized forest: A B C D E F G H I J K L M N 
find(1): 1
find(3): 3
find(4): 4
union(0,4), union(0,1), union(0,3)
find(1): 0
find(3): 0
find(4): 0

路径压缩

在查找某个元素是否属于某个集合时，将该结点到根结点路径上所有结点的父指针全部改为指向根结点，这种方式可以产生极浅的树

/*** 返回包含给定元素的集合名字** @param i 元素下标* @return 以根结点下标作为集合名字*/
public int find(int i) {GTNodeA current = set[i];if (current.getParent()<0) return i;return current.setParent(find(current.getParent()));
}//使用路劲压缩法：在查找某个元素是否属于某个集合时，将该结点到根结点路径上
// 所有结点的父指针全部改为指向根结点，这种方式可以产生极浅的树

结合重量权衡原则来归并集合的话，对n个结点进行n次find操作的路径压缩开销为O(NlogN）