uniontree.cpp

常用算法代码

#include<iostream>
using namespace std;

#define Type int
#define N 100

typedef struct Tree_node {
	struct Tree_node*  parent;
	int rank;
	Type value;
}NODE;

NODE* find(NODE *xp){
	NODE *wp, *yp = xp, *zp = xp;
	while(yp->parent){
		yp = yp->parent;
	}
	while(zp->parent){
		wp = zp->parent;
		zp->parent = yp;
		zp = wp;
	}
	return yp;
}

NODE* unionTree(NODE *xp, NODE *yp){
	NODE *up, *vp;
	up = find(xp);
	vp = find(yp);
	if(up->rank<=vp->rank){
		up->parent = vp;
		if(up->rank == vp->rank){
			vp->rank ++;
		}
		up = vp;
	}else{
		vp->parent = up;
	}
	return up;
}

NODE* createNode(Type value, NODE* parent = NULL){
	NODE* p = new NODE;
	if(parent){
		p->rank = parent->rank + 1;
	}else{
		p->rank = 1;
	}
	p->parent = parent;
	p->value = value;
	return p;
}

int main(){
	NODE* A[N];

	/* 建立集合{1,2,3,4} */
	A[4] = createNode(4);	
	A[3] = createNode(3,A[4]);	
	A[2] = createNode(2,A[4]);
	A[1] = createNode(1,A[2]);
	
	

	/* 建立集合{5,6,7,8} */
	A[8] = createNode(8);	
	A[7] = createNode(7,A[8]);	
	A[6] = createNode(6,A[8]);
	A[5] = createNode(5,A[6]);

	/*	合并两集合 */
	unionTree(A[1],A[5]);

	/* 遍历集合 */
	for(int i = 1; i<=8; i++){
		cout<<"结点"<<(A[i]->value)<<" ";
		if(A[i]->parent)cout<<"父结点"<<(A[i]->parent->value);
		else cout<<"该结点为根结点";
		cout<<endl;
	}

	return 0;
}