admin 管理员组

文章数量: 887021

森林

森林是n>=0个互不相交的树的集合，如：二叉树删除一个根，就可以转换为森林。
如果T1,….Tn是一个森林，则对应于该森林的二叉树记为B(T1,…..,Tn)，那么就有以下定义：
若n=0，森林就为空。
根为森林中第一颗树T1的根，左子树是B（T11，T12,…..,T1n),其中T11，T12,…..,T1n是T1根的所有子树，右子树是B(T2,…..,Tn)。
如：


因此森林的遍历操作跟二叉树的遍历操作一一对应。
假设有编号为0到9，要化为三个互不相交的集合，s1={0,6,7,8},s2={1,4,9},s3={2,3,5},那么可以将其转换森林方式存储，如图：

为了实现通过其根结点来判断一个元素在那个集合中以及实现两两互不相交的集合合并操作，对于每一个集合，都需保留一个指向代表这个集合的树的根结点的指针，这样就可以通过指向根结点的父链来找到元素所在的集合，并返回指向集合名字的指针，表示S1,S2,S3这种存储方式如图：

为了简化上面两种操作，将不适用集合的名字，而是用索引来表示集合名字，如：假设表name[]存放集合的名字，如果i是一个元素它在以j为根结点的树中，而且有一个指针，指向在集合名字表中的第k项，那么，集合的名字就是name[k]。
由于树中结点被编号为0到n-1,所以，可以用数组把结点的编号作为下标，这就意味着每一个结点只需要一个链接到其父结点域，即父结点的下标，而集合根结点的父亲为-1，S1,S2，S3数组存储方式表示如图：

为了防止产生退化树，在合并集合时，可以应用一个加权规则：如果树 i的结点树少于树j的结点数，则令树j是树i的父亲，否则，令树i是树j的父亲.
为了实现加权规则，需要知道每棵树的结点树，为此，在每棵树的根结点保留一个技术域，如果i是根结点，那么count[i]的值等于树中结点的个数，因为树中的所有结点(根结点除外)在父亲域都有一个非负数，所以，可以把结点的计数值作为负数保存在根结点的父亲域中。
查找元素i的根结点来判断在那个集合中的代码实现：

//返回该元素的根结点的索引
int find(int i)
{for(;parent[i]>=0;i=parent[i]);return i;
}

合并集合的代码实现：

//合并集合操作
// i，j为不同集合树的根结点的索引void union2(int i,int j){//注意：初始化时parent[i]=-count[i],parent[j]=-count[j]//故parent[i],parent[j]是用结点个数的负数表示if(i!=j){int temp=parent[i]+parent[j];// i的结点数比j小时if(parent[i]>parent[j]){parent[i]=j;parent[j]=temp;}// j的结点数比i小时else{parent[j]=i;parent[i]=temp;}}
}

本文标签： 森林

版权声明：本文标题：森林 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687516741h111199.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。