我正在尝试实现不相交集并查集，用于Kruskal算法，但是我不太明白应该如何实现，特别是如何管理森林中的树。在阅读了维基百科上对于不相交集描述以及《算法导论》（Cormen等人）中的描述后，我得出了以下代码：
class DisjointSet
{
public:
class Node
{
public:
int data;
int rank;
Node* parent;
Node() : data(0),
rank(0),
parent(this) { } // the constructor does MakeSet
};
Node* find(Node*);
Node* merge(Node*, Node*); // Union
};
DisjointSet::Node* DisjointSet::find(DisjointSet::Node* n)
{
if (n != n->parent) {
n->parent = find(n->parent);
}
return n->parent;
}
DisjointSet::Node* DisjointSet::merge(DisjointSet::Node* x,
DisjointSet::Node* y)
{
x = find(x);
y = find(y);
if (x->rank > y->rank) {
y->parent = x;
} else {
x->parent = y;
if (x->rank == y->rank) {
++(y->rank);
}
}
}
我相信这还不完整，我可能遗漏了一些东西。
《算法导论》提到应该有一片树林，但没有给出实现这个森林的实际解释。我观看了CS 61B讲座31: 不相交集合 (http://www.youtube.com/watch?v=wSPAjGfDl7Q)，在这里，讲师仅使用一个数组来存储森林以及所有的树和值。与我所提到的‘节点’类型或类不同。我还发现了许多其他来源(我不能发更多链接)，它们也使用了这种技术。我很乐意这样做，但这依赖于数组的索引进行查找，而由于我想存储除int类型之外的其他类型的值，所以我需要使用其他东西 (比如std::map)。
我还不确定的另一个问题是内存分配，因为我正在使用C++。我正在存储指针的树，我的MakeSet操作将是：new DisjointSet::Node;。现在，这些节点只有指向其父节点的指针，所以我不知道如何找到一棵树的底部。我将如何能够遍历我的树以释放它们所有的空间？
我理解这个数据结构的基本概念，但对实现还有一些困惑。任何建议和建议都将不胜感激，谢谢。