树的等价问题

在离散数学中，对等价关系和对价类的定义是： 如果集合S中的关系R是自反的，对称的和传递的，则称它为一个等价关系。 设R是集合S的等价关系。对任何x∈S，由[x]R={y|y∈S∩xRy}给出的集合[x]R⊆S称为由x∈S生成的一个R等价类。 若R是集合S的等价关系。则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S1，S2，...，它们的并即为S，则这些子集Si便称为S的R等价类。 应该如何划分等价类呢？假设集合S有n个元素，m个形如（x,y）（x，y∈S）的等价偶对确定了等价关系R，需求S的划分。 确定等价类的算法可如下进行：

1. 令S中每个元素各自形成一个单个成员的子集，记做S1，S2，...，Sn。
2. 重复读入m个偶对，对每个读入的偶对（x，y），判读x和y所属子集。不失一般性，假设x∈Si，y∈Sj，若Si！=Sj，则将Si并入Sj，并置Si为空（或将Sj并入Si并置Sj为空）。则当m个偶对都被处理之后，S1，S2，...，Sn中所有非空子集即为S的R等价类。

因此，可见划分等价类需对集合进行的操作有3个：其一是构造只含单个成员的集合；其二是判定某个单元素所在子集；其三是归并两个互不相交的集合为一个集合。 以集合为基础的抽象数据类型可用多种实现方法，如用位向量表示集合或用有序表表示集合。 如何高效的实现以集合为基础操作的抽象数据类型，则取决于该集合打大小以及对此集合所进行的操作。 数据结构中引入一个叫MFSet 的ADT，其实他就是并查集（见CSDN博客当时的并查集总结）的完善版 结构存储父结点，当两个结点的祖宗结点相同时便可以认为这是属于同一个集合的结点。 找祖宗操作：

int find_mfset(MFSet S, int i) {
   // 找集合S中i所在子集的根
   int j;
   if (i<0 || i>S.n) return -1;   // i不是S中任一子集的成员
   if (i==0)
      printf("t%d(%d%3d)n",i,S.nodes[0].data,S.nodes[0].parent);
   for (j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent)
      printf("t%d(%d%3d)n",j,S.nodes[j].data,S.nodes[j].parent);
   return 1;
}// find_mfset

两个结点判断是否一个集合：

Status merge_mfset(MFSet &S, int i, int j) {
   // S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点。
   // 求并集Si∪Sj。
   if (i<0 || i>S.n || j<0 || j>S.n) return ERROR;
   S.nodes[i].parent = j;
   return OK;
} // merge_mfset

在使用并查集的时候有个需要注意的地方，就是整个算法的时间复杂度是和树的深度有关的。 如果建的树除了叶子外只有出度为1的结点，这种极端的例子时间复杂度高达O(n^2)。 那么解决个弊端有两个方式，一是选择结点较少的一枝添加结点，顶一个是就是“路径压缩” 路径压缩是在学并查集就学的东西，在集训的时候就已经没有问题，但书中提出了选择建树是一个我没有想到过的优化方式，

Status mix_mfset(MFSet &S, int i, int j) {
   // S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点
   // 求并集Si∪Sj。
   if (i<0 || i>S.n || j<0 || j>S.n)  return ERROR;
   if (S.nodes[i].parent>S.nodes[j].parent) {   // Si所含成员数比Sj少
      S.nodes[j].parent+=S.nodes[i].parent;
      S.nodes[i].parent=j;
   } else {                                     // Sj的元素比Si少
      S.nodes[i].parent+=S.nodes[j].parent;
      S.nodes[j].parent=i;
   }
   return OK;
} // mix_mfset

这种方式使建的树深度不会超过[log2n]+1。 但是我还是更喜欢路径压缩，一是简单，压缩在查询的过程中完成了，而是压缩完，路经长度不会大于4 只需要修改find查找函数即可以实现：

int fix_mfset(MFSet &S, int i) {
   // 确定i所在子集，并将从i至根路径上所有结点都变成根的孩子结点。
   int j,k,t;
   if (i<1 || i>S.n) return -1;       // i 不是S中任一子集的成员
   for (j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent)
      printf("t%d(%d%3d)n", j, S.nodes[j].data, S.nodes[j].parent);
   for (k=i; k!=j; k=t) {
      t=S.nodes[k].parent;  S.nodes[k].parent=j;
   }
   return 1;
} // fix_mfset

树的计数

树的计数放在了最后一节，其实到现在证明我也没有看明白，先把结论总结下来吧。

这一节主要讨论的是具有n个结点的不同形态树有多少棵。

二叉树相似是指：二者都为空树或二者均不为空树而且他们的左右子树分别相似

二叉树等价是指：二者不仅相似，而且所有对应结点上的数据元素均相同。

二叉树的计数问题就是讨论二叉具有n个结点、互不相似的二叉树的数目bn。

在n很小的时候，可直观的得到b0=1为空树；b1=1是只有一个根结点树，b2=2，b3=5。

一般情况下，一棵具有n（n>1）个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的左右子树组成，其中0<=i<=n-1由此可得地推公式

b0=1

bn=Σ(n-1,i=0)bi bn-i-1 （n>=1）

最后，前序或后序加上中序遍历就可以确定一棵唯一的树，这也是判断两个树是否相同最好的方式。