//類ParTreeNode描述了樹的結(jié)點(diǎn)定義
template<class T>
class ParTreeNode  { 					    //樹結(jié)點(diǎn)定義
private:
	T				value;					//結(jié)點(diǎn)的值
	ParTreeNode<T>* parent;					//父結(jié)點(diǎn)指針
	int		nCount;							//以此結(jié)點(diǎn)為根的子樹的總結(jié)點(diǎn)個(gè)數(shù)
public:
	ParTreeNode();							//構(gòu)造函數(shù)
	virtual ~ParTreeNode(){};				//析構(gòu)函數(shù)
	T	getValue();							//返回結(jié)點(diǎn)的值
	void  setValue(const T& val);			//設(shè)置結(jié)點(diǎn)的值
	ParTreeNode<T>*  getParent();			//返回父結(jié)點(diǎn)指針
	void  setParent(ParTreeNode<T>* par);	//設(shè)置父結(jié)點(diǎn)指針
	int   getCount();						//返回結(jié)點(diǎn)數(shù)目
	void  setCount(const int count);		//設(shè)置結(jié)點(diǎn)數(shù)目
};

//ParTreeNode抽象數(shù)據(jù)類型成員函數(shù)的實(shí)現(xiàn)
template<class T>
ParTreeNode<T>::ParTreeNode()  {            //構(gòu)造函數(shù)
	parent = NULL;
	nCount = 1;
}
template<class T>
T ParTreeNode<T>::getValue()  {				//返回結(jié)點(diǎn)的值
	return value;
}
template<class T>
void ParTreeNode<T>::setValue(const T& val)  {			//設(shè)置結(jié)點(diǎn)的值
	value = val;
}
template<class T>
ParTreeNode<T>* ParTreeNode<T>::getParent()  {			//返回父結(jié)點(diǎn)指針
	return parent;
}
template<class T>
void ParTreeNode<T>::setParent(ParTreeNode<T>* par)  {   //設(shè)置父結(jié)點(diǎn)指針
	parent = par;
}
template<class T>
int ParTreeNode<T>::getCount()  {						//返回結(jié)點(diǎn)數(shù)目
	return nCount;
}
template<class T>
void ParTreeNode<T>::setCount(const int count)  {		//設(shè)置結(jié)點(diǎn)數(shù)目
	nCount = count;
}

//類ParTree描述了樹的定義
template<class T>
class ParTree  {								//樹定義
public:
	ParTreeNode<T>* array;						//存儲(chǔ)樹結(jié)點(diǎn)的數(shù)組
	int	Size;									//數(shù)組大小
	ParTree(const int size);					//構(gòu)造函數(shù)
	virtual ~ParTree();							//析構(gòu)函數(shù)
	ParTreeNode<T>*	Find(ParTreeNode<T>* node)const;//查找node結(jié)點(diǎn)的根結(jié)點(diǎn)
	ParTreeNode<T> *FindPC(ParTreeNode<T> *node) const; // 帶壓縮
	
	void Union(int i,int j);					//把下標(biāo)為i，j的結(jié)點(diǎn)合并成一棵子樹
	void UnionPC(int i, int j);                 //帶壓縮
	bool Different(int i,int j);				//判定下標(biāo)為i，j的結(jié)點(diǎn)是否在一棵樹中
};

//樹的成員函數(shù)的實(shí)現(xiàn)
template <class T>
ParTree<T>::ParTree(const int size)  {			//構(gòu)造函數(shù)
	Size = size;
	array = new ParTreeNode<T>[size];
}

template <class T>											
ParTree<T>::~ParTree()  {						//構(gòu)造函數(shù)
	delete []array;
}

// 函數(shù)功能：找到目標(biāo)結(jié)點(diǎn)的根結(jié)點(diǎn)
template <class T>
ParTreeNode<T>*	ParTree<T>::Find(ParTreeNode<T>* node) const  {
	ParTreeNode<T>* pointer = node;
	while(pointer->getParent() != NULL)
		pointer = pointer->getParent();
	return pointer;
}

//函數(shù)功能：帶路徑壓縮的Find算法
template <class T>
ParTreeNode<T> *ParTree<T>::FindPC(ParTreeNode<T> *node) const  {
	if (node->getParent() == NULL)
		return node;
	
	node->setParent(FindPC(node->getParent()));
	return node->getParent();
}

//函數(shù)功能：判定下標(biāo)為i，j的結(jié)點(diǎn)是否在一棵樹中
template<class T>
bool ParTree<T>::Different(int i,int j)  {
	ParTreeNode<T>* pointeri = Find(&array[i]);		//找到結(jié)點(diǎn)i的根
	ParTreeNode<T>* pointerj = Find(&array[j]);		//找到結(jié)點(diǎn)j的根
	return pointeri != pointerj;
}

//把下標(biāo)為i，j的結(jié)點(diǎn)合并成一棵子樹
template<class T>
void ParTree<T>::Union(int i,int j)  {
	ParTreeNode<T>* pointeri = Find(&array[i]);		//找到結(jié)點(diǎn)i的根
	ParTreeNode<T>* pointerj = Find(&array[j]);		//找到結(jié)點(diǎn)j的根
	if(pointeri != pointerj) {
		if(pointeri->getCount()>=pointerj->getCount()) {
			pointerj->setParent(pointeri);
			pointeri->setCount(pointeri->getCount()+pointerj->getCount());
		}
		else {
			pointeri->setParent(pointerj);
			pointerj->setCount(pointeri->getCount()+pointerj->getCount());
		}
	}
}

// 函數(shù)功能：歸并兩個(gè)集合， 帶壓縮
template <class T>
void ParTree<T>::UnionPC(int i, int j)  {
	ParTreeNode<T> *pointeri = FindPC(&array[i]);
	ParTreeNode<T> *pointerj = FindPC(&array[j]);
	
	if (pointeri != pointerj)  {
		if (pointeri->getCount() >= pointerj->getCount())  {
			pointerj->setParent(pointeri);
			pointeri->setCount(pointeri->getCount() + pointerj->getCount());
		}
		else  {
			pointeri->setParent(pointerj);
			pointerj->setCount(pointeri->getCount() + pointerj->getCount());
		}
	}
}