开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构——树和二叉树 -> 正文阅读

[数据结构与算法]数据结构——树和二叉树

1.树、森林?

1.1定义和基本术语

1.3.3孩子兄弟表示法（链式存储——二叉链表）

1.4树和森林的相互转换与遍历

1.4.1树和森林的相互转换

1.4.2树和森林的遍历

1.5哈夫曼树（Huffman Tree)

2.5.1概念、作用、存储结构（链式存储），手算?

2.5.2二叉树的线索化（建立线索）

2.5.3前/中/后序线索二叉树中找指定节点*p的前/中/后序前驱后继?

1.树、森林?

1.1定义和基本术语

1.1.1结点、树的关系和属性

关系描述：

祖先结点?子孙结点?

双亲结点(父节点）?孩子结点?

兄弟结点?堂兄弟结点?

两个结点之间的路径（只能从上往下）?路径长度（经过几条边）?

属性描述：

结点的层次（深度，默认从1开始）——从上往下数

结点的高度――从下往上数

结点的度――有几个孩子(分支)? ?（非叶子结点度>0；叶子结点度=0）

树的高度（深度）——总共多少层

树的度――各结点的度的最大值

1.1.2基本概念

?树的定义

树的数学描述：

树的递归定义：树是由根节点和若干互不相交的子树构成。?

m叉树：每个结点最多只能有m个孩子的树（任意结点的度≤m）

树这种数据结构的应用：家谱、文件系统、思维导图……

?空树 VS 非空树?

空树?的特性：结点数为0；

非空树的特性：
有且仅有一个根节点；没有后继的结点称为“叶子结点”（或终端结点），有后继的结点称为“分支结点”（或非终端结点）；除了根节点外，任何一个结点都有且仅有一个前驱，每个结点可以有0个或多个后继。

?有序树 VS 无序树

有序树――逻辑上看，树中结点的各子树从左至右是有次序的，不能互换；

无序树――逻辑上看，树中结点的各子树从左至右是无次序的，可以互换。

具体看你用树存什么，是否需要用结点的左右位置反映某些逻辑关系

?认识二叉树

二叉树的5种合法状态：

?树 VS 森林

森林是m (m≥0）棵互不相交的树的集合。

eg：全国所有人家的家谱。

考点：树和森林相互转化?

1.2树的性质

1.树的结点个数=各非根结点度数和 +1（1：root）

只有根节点没有分支。

2.度为m的树 VS m叉树

3. 度为m的树第 i 层至多有? $m^{i-1}(i\geq1)$ 个结点

?m叉树第 i 层至多有? $m^{i-1}(i\geq1)$ 个结点

4.高度为h的m叉树至多有 $\frac{m^{h}-1}{m-1}$ 个结点?

?这个就是等比数列求和，最多就是每一个结点的子结点数都为m，这个等比数列的公比为m，首项都是1，根据等比数列1-m为负数，1-q^n也为负数，这里公式就直接调换位置了，结果不变。

$m^{0}+m^{1}+m^{2}+...+m^{h-1}=\frac{m^{0}(1-m^{h})}{1-m}=\frac{m^{h}-1}{m-1}$

等比数列前n项和： $S_{n}=\frac{a_{1}(1-q^{n})}{1-q}=\frac{a_{1}-a_{n}q}{1-q}$

5.高度为h的m叉树至少有h个结点；高度为h、度为m的树至少有h+m-1个结点。

6.具有n个结点的m叉树的最小高度为? $\left \lceil log_{m}(n(m - 1)+1) \right \rceil$

高度最小，则就是尽量将结点安排在较小的层上面，也就是每一个结点的子结点数尽量都为m，设 $\frac{m^{h}-1}{m-1}=n$ ，求出m即可，至于结果向下取整，是因为这个结果计算的不一定为整数，因为我们这里的条件是最小高度，则就是每层结点个数，除了最后一层，都达到最大数，那么这个最后一层可能就不满足结点最大数，那么使用这个公式计算的结果就会出现小数，但是最后一层也是有结点的也算一层，所以向下取整。

1.3树的存储结构

1.3.1双亲表示法（顺序存储）

每个结点保存指向双亲的“指针”（数组下标）。

//双亲表示法
#define MAX_TREE_SIZE 100 //树中最多节点个数 
typedef struct {          //树节点的定义 
	ElemType data;        //数据元素 
	int parent;           //指向双亲的“指针”（数组下标） 
}PTNode;    //parent node
typedef struct{           //树的类型定义 
	PTNode nodes[MAX_TREE_SIZE]; //双亲表示法（静态分配的顺序存储） 
	int n;  //节点数 
}PTree; 

PTree T;    //开辟了 100*sizeof（PTNode）+ sizeof（int） 大小的空间

1.3.2孩子表示法（顺序+链式存储）

顺序存储各个节点，每个结点中保存孩子链表头“指针”（数组下标）

struct CTNode{//child next 
	int child; //孩子在节点数组中的位置
	struct CTNode *next；//指向下一个孩子 
}; 
typedef struct{
	ElemType data;            //数据元素
	struct CTNode *firstchild;//指向第一个孩子 
}CTBox; //child next box
 
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n,r; //结点数和根的位置 
}CTree;

1.3.3孩子兄弟表示法（链式存储——二叉链表）

typedef struct CSNode{ //Child sibling（兄弟姐妹） node 
	ElemType data;  //数据域
	struct CSNode *firstchild，*nextsibling; //第一个孩子和右兄弟指针 ——二叉链表
}CSNode, *CSTree;

1.4树和森林的相互转换与遍历

1.4.1树和森林的相互转换

孩子兄弟表示法的应用

二叉树和森林的相互转换——用二叉链表存储森林

1.4.2树和森林的遍历

1.树的遍历

树的先根遍历：

树的后根遍历：

树的层次遍历：

2.森林的遍历

森林的先序遍历：

对树依次进行先根遍历；或者把森林转化为二叉树（孩子兄弟表示法），进行先序遍历。

森林的中序遍历：

对树依次进行后根遍历；或者把森林转化为二叉树（孩子兄弟表示法），进行中序遍历。

1.5哈夫曼树（Huffman Tree)

结点的权：有某种现实含义的数值（如:表示结点的重要性等)

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数〉与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和(WPL, Weighted Path Length)

$WPL= \sum \omega _{i}l_{i}$
定义：在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树

哈夫曼树的构造：

哈夫曼编码：

固定长度编码――每个字符用相等长度的二进制位表示

可变长度编码――允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

由哈夫曼树得到哈夫曼编码――字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树。哈夫曼树不唯一，哈夫曼编码不唯一

哈夫曼编码用于数据压缩

例题：

2.二叉树???

2.1 4种特殊的二叉树

满二叉树：一棵高度为h，且含有? $2^{h}-1$ ?个结点的二叉树。?

①只有最后一层有叶子结点

②不存在度为1的结点（度只能是0或2）

③按层序从1开始编号，结点 i 的左孩子为 2i ，右孩子为 2i+1；结点i的父节点为 $\left \lfloor i/2 \right \rfloor$ （如果有的话)

完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时,称为完全二叉树

①只有最后两层可能有叶子结点

②最多只有一个度为1的结点

③同上面③
④? $i\leq \left \lfloor n/2 \right \rfloor$ ?为分支结点， $i> \left \lfloor n/2 \right \rfloor$ ?为叶子结点

完全二叉树的某个节点如果只有一个孩子，必然是左孩子

二叉排序树：或者是空二叉树，或者是具有如下性质的二叉树:

左子树上所有结点的关键字均小于根结点的关键字;

右子树上所有结点的关键字均大于根结点的关键字。

左子树和右子树又各是一棵二叉排序树。

二叉排序树可用于元素的排序、搜索。

平衡二叉树：?树上任一结点的左子树和右子树的深度之差不超过1。

追求平横以得到更高效的搜索效率。

2.2二叉树的性质

1.二叉树的叶子节点比二分支节点多一个

设非空二叉树中度为0、1、2的节点个数分别为 $n_{0}$ 、 $n_{1}$ 和 $n_{2}$ ，则 $n_{0}= n_{2}+1$ $n_{0}=n_{2}+1$

2.二叉树（m=2）第 i 层至多有? $2^{i-1}(i\geq1)$ 个结点（满二叉树）?

3.高度为h的二叉树（m=2）至多有 $\frac{m^{h}-1}{m-1}$ 个结点

4.高度为h的二叉树至少有h个结点

完全二叉树的常考性质：

2.3二叉树的存储结构

2.3.1顺序存储

完全二叉树的顺序存储

结点编号不仅反映了存储位置，也隐含了结点之间的逻辑关系

非完全二叉树的顺序存储

结点编号不仅反映了存储位置，也隐含了结点之间的逻辑关系

定义一个长度为MaxSize的数组tree，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点，或按照对应相同的编号存储非完全二叉树的各个节点。?

#define MAXSIZE 100
typedef struct TreeNode{
	ElemType value;  //数据域
	bool isEmpty;    //判断节点是否为空值 
};
TreeNode tree[MAXSIZE] ;

//初始化
void InitTree(TreeNode t[]){
	for(int i=1;i<MAXSIZE;i++){
		t[i].isEmpty = true;
	}
}

2.3.2链式存储

二叉链表

typedef struct BiTNode{ //binary tree node 
	ElemType value;  //数据域
	struct BiTNode *lchild，*rchild;    //左、右孩子指针 
}BiTNode，*BiTree;

n个节点的二叉链表

有2n个指针域，其中有n-1个非空指针（除了根节点，其他节点“头上”都有边），则有n+1给空指针。（可以用于构造线索二叉树）

//建立一个二叉树
struct ElemType{ //数据域也是一个结构体 
	int value1;
	//...
};  
typedef struct BiTNode{ //binary tree node 
	ElemType data;  //数据域
	struct BiTNode *lchild，*rchild;    //左、右孩子指针 
}BiTNode, *BiTree;

//定义一个二叉树 
BiTree root = NULL;
 
//插入根节点 
root = (BiTNode*)malloc(sizeof(BiTNode)); 
root.data = {1,...}; //依次赋值给数据域的结构体中
root.lchild = NULL;
root.rchild = NULL;
 
//插入新节点
p = (BiTNode*)malloc(sizeof(BiTNode));
root.data = {2,...}; //依次赋值给数据域的结构体中
p.lchild = NULL;
p.rchild = NULL;
root.lchild->p; //把新节点作为根节点的左孩子

三叉链表

//三叉链表方便找父节点 
typedef struct BiTNode{ //binary tree node 
	ElemType data;  //数据域
	struct BiTNode *lchild，*rchild;    //左、右孩子指针
	struct BiTNode *parent; //根据实际需要来增加父指针 
}BiTNode, *BiTree;

2.4二叉树的遍历

2.4.1先中/后/序遍历

?例子说明：（分支节点逐层展开)

二叉树的先中后序遍历与前中后缀表达式的关系举例：

二叉树的先中后序遍历代码实现：（递归函数的应用）

//先序遍历
void PreOrder(BiTree T){
	if(T != NULL) {
		visit(T); //访问根节点，例如打印根节点T->data 
		PreOrder(T->lchild);//递归遍历左子树 
		PreOrder(T->rchild);//递归遍历右子树 
	}
} 
//中序遍历
void InOrder(BiTree T){
	if(T != NULL) { 
		InOrder(T->lchild);//递归遍历左子树 
		visit(T); //访问根节点，例如打印根节点T->data
		InOrder(T->rchild);//递归遍历右子树 
	}
} 
//后序遍历
void PostOrder(BiTree T){
	if(T != NULL) { 
		PostOrder(T->lchild);//递归遍历左子树 
		PostOrder(T->rchild);//递归遍历右子树 
		visit(T); //访问根节点，例如打印根节点T->data
	}
}

例：求树的深度（后序遍历的应用）

int treeDepth(BiTree T){
	if(T == NULL) return 0;
	else{
		l = treeDepth(T->lchild);//访问左子树 
		r = treeDepth(T->rchild);//访问右子树 
		//树的深度即为子树深度的最大值+1（root） 
		l>r?l+1:r+1//三元运算符——条件表达式?表达式1:表达式2 
//		if(l>r) return l+1; 
//		else return r+1;
		
	}
}

对根节点而言：?

先序：第一次路过时访问

中序：第二次路过时访问

后序：第三次路过时访问

2.4.2层序遍历

一层一层访问各个节点

算法思想：

①初始化一个辅助队列(链式队列）

②根结点入队（存根节点的指针而不是节点）

③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子依次插入队尾（如果有的话)

④重复③直至队列为空

代码实现：

//层序遍历
void LevelOrder(BiTree T){
	LinkQueue Q; //step1：辅助队列 
	InitQueue(Q);
	BiTree p;
	EnQueue(Q,p);//step2：根节点入队（入队只存指针） 
	while(!isEmpty(Q)){ //step3：队列非空 
		//step3.1：队头结点出队；访问队头节点，例如打印队头节点T->data
		DeQueue(Q,p);
		visit(p); 
		//step3.2：将其左右孩子依次入队（ 入队只存指针）
		if(p->lchild != NULL) EnQueue(Q,p->lchild);
		if(p->rchild != NULL) EnQueue(Q,p->rchild);
	}
    //step4：重复③直至队列为空
} 

//其中一些数据结构的定义说明
//二叉树的结构定义
typedef struct BiTNode{ //binary tree node 
	ElemType data;  //数据域
	struct BiTNode *lchild，*rchild;    //左、右孩子指针 
}BiTNode, *BiTree;

//链式队列的结构定义
typedef struct LinkNode{
	BiTNode *data;//队列存的是根节点的指针而不是节点
	struct LinkNode *next; 
}LinkNode;
typedef struct{
	LinkNode *front,*rear;
}LinkQueue;

2.4.3由遍历序列构造二叉树

一棵二叉树对应的前/中/后/层序遍历序列是唯一的。

若只给出一棵二叉树的前/中/后/层序遍历的一种，不能唯一确定该二叉树。若给出前+中序遍历序列或中+后序遍历序列或层+中序遍历序列，则可以唯一确定。

若给出一棵二叉树的前/后/层序遍历的任意两种，也不能唯一确定该二叉树。

1.前+中序遍历序列

例子：

2.中+后序遍历序列

例子：

3.层+中序遍历序列?

例子：??

2.5线索二叉树???

2.5.1概念、作用、存储结构（链式存储），手算?

作用：方便从一个指定结点出发，找到其前驱、后继（这里指基于某种遍历序列德钱前驱和后继）；方便对树的遍历。

存储结构（链式存储）：在普通二叉树结点（二叉链表）的基础上，增加两个标志位ltag、rtag。

//线索链表（由二叉链表升级而来） 
typedef struct ThreadNode{ //binary tree node 
	ElemType data;  //数据域
	struct ThreadNode *lchild，*rchild;    //左、右孩子指针 
	int ltag,rtag;  //左右线索标志 0：孩子；1：线索 
}ThreadNode, *ThreadTree;

三种线索二叉树（手算?）：中/前/后序线索二叉树

2.5.2二叉树的线索化（建立线索）

1.中序线索化（建立中序线索二叉树的线索指针）

?土办法找中序前驱

思路:
从根节点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点（当前访问节点的前驱），指针final记录最终结果。

①当q==p时，pre为前驱
②当pre==p时，q为后继
缺点：找前驱、后继很不方便；遍历操作必须从根开始。

代码实现：（代码实现——实质是对visit(T)的具体化改造）

//土办法找中序前驱 
//辅助全局变量
BiTNode *q;//q记录当前访问节点
BiTNode *pre;//pre记录上一个被访问的节点
BiTNode *final;//记录最终结果
//中序遍历
void FindPre(BiTree T){ 
	if(T!=NULL){
		FindPre(T->lchild);
		visit(T);
		FindPre(T->rchild);
	}
} 
//改造visit(T)——找指定节点的前驱 
void visit(BiTNode *p){
	if(q==p) final = pre;//当前访问节点正好是p，找到p的前驱 
	else pre = q;//当前访问节点不是p，则pre指向当前结点，本次visit结束，根据中序遍历对比下一个 
}

??根据线索链表进行中序线索化（建立中序线索二叉树的线索指针）

（代码实现——实质是对visit(T)的具体化改造）

//中序线索化（建立中序线索二叉树的线索指针）
//辅助全局变量 
ThreadNode *pre=NULL;
//中序遍历（一边遍历一遍建立线索） 
void InThread(ThreadTree &T){
	if(T!=NULL){
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	} 
} 
//建立线索
void visit(ThreadNode *q){
	if(q->lchild==NULL){//当前结点无左孩子，
		q->lchild = pre;//则建立当前结点的前驱线索 
		q->ltag = 1;
	} 
	if(pre->rchild==NULL && pre!=NULL){//当前结点q有前驱pre,且前驱pre无右孩子 ， 
		pre->rchild = q;//则建立当前结点p的前驱结点的后继线索 
		pre->rtag = 1;
	} 
	pre = q;//pre指向当前结点，本次visit结束，根据中序遍历对比下一个
} 
//综上，中序线索化二叉树T（封装）
void CreateThread(ThreadTree T){
	pre=NULL;
	if(T!=NULL){
		InThread(T);//中序遍历，同时建立线索
		if(pre->rchild == NULL) pre->rtag = 1;//特殊处理遍历的最后一个节点
	}
}

2.先序线索化（建立先序线索二叉树的线索指针）?

//先序线索化（建立先序线索二叉树的线索指针）
//辅助全局变量 
ThreadNode *pre=NULL;
//先序遍历（一边遍历一遍建立线索） 
void PreThread(ThreadTree &T){
	if(T!=NULL){
		visit(T);
		//避免爱的魔力转圈圈 
		if(T->ltag==0) PreThread(T->lchild);//T->lchild不是前驱 
		PreThread(T->rchild);
	} 
} 
//建立线索（同上） 
void visit(ThreadNode *q){
	if(q->lchild==NULL){//当前结点无左孩子，
		q->lchild = pre;//则建立当前结点的前驱线索 
		q->ltag = 1;
	} 
	if(pre->rchild==NULL && pre!=NULL){//当前结点q有前驱pre,且前驱pre无右孩子 ， 
		pre->rchild = q;//则建立当前结点p的前驱结点的后继线索 
		pre->rtag = 1;
	} 
	pre = q;//pre指向当前结点，本次visit结束，根据先序遍历对比下一个
} 
//综上，先序线索化二叉树T（封装）
void CreatePreThread(ThreadTree T){
	pre=NULL;
	if(T!=NULL){
		PreThread(T);//先序遍历，同时建立线索
		if(pre->rchild == NULL) pre->rtag = 1;//特殊处理遍历的最后一个节点
	}
}

3.后序线索化（建立后序线索二叉树的线索指针）

//后序线索化（建立后序线索二叉树的线索指针）
//辅助全局变量 
ThreadNode *pre=NULL;
//后序遍历（一边遍历一遍建立线索） 
void PostThread(ThreadTree &T){
	if(T!=NULL){
		PostThread(T->lchild);
		PostThread(T->rchild);
		visit(T);
	} 
} 
//建立线索（同上） 
void visit(ThreadNode *q){
	if(q->lchild==NULL){//当前结点无左孩子，
		q->lchild = pre;//则建立当前结点的前驱线索 
		q->ltag = 1;
	} 
	if(pre->rchild==NULL && pre!=NULL){//当前结点q有前驱pre,且前驱pre无右孩子 ， 
		pre->rchild = q;//则建立当前结点p的前驱结点的后继线索 
		pre->rtag = 1;
	} 
	pre = q;//pre指向当前结点，本次visit结束，根据后序遍历对比下一个
} 
//综上，后序线索化二叉树T（封装）
void CreatePostThread(ThreadTree T){
	pre=NULL;
	if(T!=NULL){
		PostThread(T);//后序遍历，同时建立线索
		if(pre->rchild == NULL) pre->rtag = 1;//特殊处理遍历的最后一个节点
	}
}

2.5.3前/中/后序线索二叉树中找指定节点*p的前/中/后序前驱后继?

1.中序线索二叉树中找指定节点*p的中序前驱/中序后继

中序线索二叉树中找指定节点*p的中序后继思路：

代码实现：?

//中序线索二叉树找后继
ThreadNode* NextNode(ThreadNode* p){
	if(p->rtag==0) return FirstNode(p->rchild);//找到右子树中序遍历的第一个节点 
	else return p->rchild; //p->rtag==1时，p的后继即为p的右孩子 
} 
ThreadNode* FirstNode(ThreadNode* p){
	while(p->ltag==0) p = p->lchild ;//右子树中序遍历的第一个节点即为右子树最左边的节点 
	return p;//p->ltag==1，右子树中序遍历的第一个节点即为右孩子 
}

空间复杂度为O(1)的中序遍历（线索实现的非递归算法）：

//空间复杂度为O(1)的中序遍历（线索实现的非递归算法） 
void InOrder(ThreadNode* T){//或者 void InOrder(ThreadTree* T)
	for(ThreadNode* p=FirstNode(T);p!=NULL; p=NextNode(p))
        visit(T); 
}

中序线索二叉树中找指定节点*p的中序前驱思路：

代码实现：?

//中序线索二叉树找前驱 
ThreadNode* NextNode(ThreadNode* p){
	if(p->rtag==0) return LasttNode(p->lchild);//找到左子树中序遍历的最后一个节点 
	else return p->lchild; //p->rtag==1时，p的前驱即为p的左孩子 
} 
ThreadNode* LasttNode(ThreadNode* p){
	while(p->ltag==0) p = p->rchild ;//左子树中序遍历的最后一个节点即为左子树最右边的节点 
	return p;//p->ltag==1，左子树中序遍历的第一个节点即为左孩子 
}

2.先序线索二叉树中找指定节点*p的先序前驱/先序后继

先序线索二叉树中找指定节点*p的先序后继思路：

先序线索二叉树中找指定节点*p的先序前驱：用二叉链表找不到

考虑用三叉链表（含有双亲指针）：

3.后序线索二叉树中找指定节点*p的后序前驱/先序后继

后序线索二叉树中找指定节点*p的后序后继思路：二叉链表找不到

考虑用三叉链表（含双亲结点）：?

后序线索二叉树中找指定节点*p的后序前驱：

×号的可以考虑用土办法或三叉链表。?

3.并查集（2022新增考点）

3.1三要素（逻辑结构、运算、存储结构）

3.1.1逻辑结构——集合

如何表示这些子集？——森林中的树。森林是互不相交的树的集合。——同一子集中的元素连接成一棵树。

3.1.2运算——初始化、“并”与“查”

初始化（Initial）

查（Find）

如何“查”到一个元素到底属于哪一个集合?—―从指定元素出发，一路向北，找到根节点

如何判断两个元素是否属于同一个集合?—―分别查到两个元素的根，判断根节点是否相同即可

并（Union）

如何把两个集合“并”为一个集合?——让一棵树成为另一棵树的子树

为了能够实现这些基本操作，选择树的双亲表示法

3.1.3存储结构——顺序存储

基于双亲结点表示法，我对王道课程并查集的存储结构作了进一步修改，可能更便于理解。

//UFSets
//双亲表示法 
#define MAX_UFSets_SIZE 100 //并查集中最多节点个数 
typedef struct {          //并查集节点的定义 
	ElemType data;        //数据元素 
	int parent;           //指向双亲的“指针”（数组下标） 
}PTNode; 
typedef struct{           //并查集的类型定义 
	PTNode sets[MAX_UFSets_SIZE]; //双亲表示法（静态分配的顺序存储） 
	int n;  //节点数 
}UFSets; 

UFSets Sets; 

//初始化
void Initial(UFSets S,int x){
	for(int i=0;i<MAX_UFSets_SIZE;i++){
		S.sets[i]->parent = -1;
	}
} 
//“查” 找下标为x元素的所属集合，即返回x所属根节点 
int Find(UFSets S,int x){
	while(S.sets[x]->parent>=0) x = S.sets[x]->parent;//x的父节点不是根节点，则查x的父节点的父节点 
	return x;//直到找到父节点<0的结点，即找到了根结点（根的parent<0） 
}

//“并” 用Find()分别找到需合并节点的根节点，再用Union()进行合并
bool Union(UFSets S,int root1,int root2){
	if(root1 == root2) return false;//同一个根节点的两个节点不需要合并
	else{
		S.sets[root2]->parent = root1 ;//root2合并到root1上，只要把root2的父节点设为root1 
		return true; 
	}
}

Find：O(n) 与树高有关

Union：O(1)

3.2并查集的“并”与“查”的优化

优化的核心思想：尽量让树变矮

方案一：Union时，让小树合并到大树（结点少的视为小树，结点多的视为大树）

建立并查集时，令根节点的S.sets[ ]存的是该树结点数的相反数（绝对值是结点数）?

//“并” 用Find()分别找到需合并节点的根节点，再用Union()进行合并
bool Union(UFSets S,int root1,int root2){
	if(root1 == root2) return false;//同一个根节点的两个节点不需要合并
	else if(S.sets[root2]>S.sets[root1]){//root2是小树（根节点的S.sets[]存的是该树结点数的相反数（绝对值是结点数） 
		S.sets[root1] += S.sets[root2];//累加大树root1的节点个数 
		S.sets[root2]->parent = root1 ;//小树root2合并到大树root1上，只要把root2的父节点设为root1 
		return true; 
	}else{//root1是小树
		S.sets[root2] += S.sets[root1];//累加大树root2的节点个数 
		S.sets[root1]->parent = root2 ;//小树root1合并到大树root2上，只要把root1的父节点设为root2
		return true; 
	} 
}

方案二：Find时，压缩路径

先找到根节点，再将查找路径上所有结点都挂到该树的根结点下。

//“查” 找下标为x元素的所属集合，即返回x所属根节点 
int Find(UFSets S,int x){
	int root = x; 
	while(S.sets[root]->parent>=0) root = S.sets[root]->parent;//x的父节点不是根节点，则查x的父节点的父节点 
	//循环结束后找到父节点<0的结点root
	
	//开始把查找路径上的所有节点（不包括根）挂到根结点下
	while(x!=root){//排除了根 
		int t = S.sets[x]->parent;//t暂存x的父节点 
		S.sets[x]->parent = root ;//x直接挂到根下，即x的父节点指向根
		x = t;//接下来处理x的父节点 
	} 
	return root; 
}