// General tree node ADT
template <typename E> class GTNode {
public:-  
E value(); // Return node’s value
bool isLeaf(); // True if node is a leaf
GTNode* parent(); // Return parent
GTNode* leftmostChild(); // Return first child
GTNode* rightSibling(); // Return right sibling
void setValue(E&); // Set node’s value
void insertFirst(GTNode<E>*); // Insert first child
void insertNext(GTNode<E>*); // Insert next sibling
void removeFirst(); // Remove first child
void removeNext(); // Remove right sibling
};
// General tree ADT
template <typename E> class GenTree {
public:
void clear(); // Send all nodes to free store
GTNode<E>* root(); // Return the root of the tree
// Combine two subtrees
void newroot(E&, GTNode<E>*, GTNode<E>*);
void print(); // Print a tree
};

// General tree representation for UNION/FIND
class ParPtrTree {
private:
int* array; // Node array
int size; // Size of node array
int FIND(int) const; // Find root 找到结点的根
public:
ParPtrTree(int); // Constructor
˜ParPtrTree() { delete [] array; } // Destructor
void UNION(int, int); // Merge equivalences 后者的根作为孩子连过去联合成一棵树
bool differ(int, int); // True if not in same tree
};
int ParPtrTree::FIND(int curr) const { // Find root
while (array[curr] != ROOT) curr = array[curr];
return curr; // At root
}

// FIND with path compression
int ParPtrTree::FIND(int curr) const {
if (array[curr] == ROOT) return curr; // At root
array[curr] = FIND(array[curr]);
return array[curr];
}