union-find树结构代码

union-find树结构代码，考虑路径压缩和秩启发式规则。

直接上源代码：

#include <stdio.h>
#include <malloc.h>
typedef struct Node
{
	int name;//节点名
	//int count;//以此节点为根的子节点数量
	int father;//父亲节点
	int rank;//秩
}TreeNode, *BiTree;
BiTree initializeNode(int num)
{
	BiTree tn=(BiTree)malloc(num*sizeof(TreeNode));
	for (int i=0;i<num;i++)
	{
		tn[i].name=i;
		//tn[i].count=1;
		tn[i].father=i;//父节点为自己
		tn[i].rank=0;
	}
	return tn;
}

/************************************************************************
找到某个节点的根节点
输入参数：
	root 根据节点名找到节点编号
	tn：根据节点编号查询其父节点
	name：节点名
输出参数：
	index：根结点节点编号
************************************************************************/
int find(int *root,BiTree tn,int name){
	int index=root[name];
	BiTree t=&tn[index];
	if (t->father!=index)
	{
		t->father=find(root,tn,tn[t->father].name);
	}
	return t->father;
}
//两个根结点合并
void f_union(int *root,BiTree  bt,int name1,int name2,int re_name){
	int index1=find(root,bt,name1);
	int index2=find(root,bt,name2);
	BiTree t1=&bt[index1];
	BiTree t2=&bt[index2];
	if (t1->rank>=t2->rank){
		//如果T1的秩大，即T1的树高度高
		t2->father=index1;
		if (t1->rank==t2->rank){
			t1->rank++;
		}
		if (re_name>=0)
		{
			t1->name=re_name;
			root[re_name]=index1;
		}
	}
	else{
		t1->father=index2;
		if (re_name>=0)
		{
			t2->name=re_name;
			root[re_name]=index2;
		}
	}
}
void n_union(int *root,BiTree  bt,int name1,int name2){
	f_union(root,bt,name1,name2,-1);
}
void main()
{
	int num=6;
	BiTree tn=initializeNode(num); 
	int root[11]={-1};
	for (int i=0;i<num;i++)
	{
		root[i]=i;
	}
	n_union(root,tn,1,2);
	n_union(root,tn,3,4);
	n_union(root,tn,4,5);
	n_union(root,tn,4,2);
	n_union(root,tn,2,0);


	for (int i=0;i<num;i++)
	{
		printf("index:%d, ",i);
		printf("name:%d, ",tn[i].name);
		printf("rank:%d, ",tn[i].rank);
		printf("father:%d\n",tn[i].father);
	}
	printf("root[name]:index\n");
	for (int i=0;i<12;i++)
	{
		printf("root[%d]:%d\n",i,root[i]);
	}
	printf("\nprint end");
	char ch = getchar();
}