树实现集合与运算

浅浅的花香味﹌ 2022-05-13 01:24 137阅读 0赞

![70][]

**如图，2棵树表示2个集合，用一个数组存储多棵树**

注意:（1）.用树表示集合，树的每一个节点代表集合中的一个元素，并且从上到下，从左到右放从小到大的元素

（2）如何表示这2棵树？用数组存储每一个元素的data和该元素parent的位置，无parent则用-1表示

![70 1][]

**集合元素的查找：**

int find(Set s[ ],int x){
    	int i;
    	for(i=0;i<s.size&&s[i].data!=x;i++);
    	if(i>=s.size) return -1;//查找元素的位置
    	
    	for(;s[i].parent>=0;i=s[i].parent);//查找根元素的位置
    }

注意:（1）.s是数组，里面是多个树放在里面的

**集合的合并：**

**![70 2][]**

void union(Set s,int x1,int x2){
    	//因为一个数组s，可以存放多棵树，所以只传入s和要查找的值即可
    	int root1,root2;
    	root1=find(s,x1);//大树的根
    	root2=find(s,x2);//小树的根
    	if(root1!=root2) s[root2].parent=root1;
    }

注意:（1）.首先要分别指导要合并的2个元素的根节点，如果根节点相同，则证明是同一课树

（2）.如果根节点不同，则把小树的根节点的parent指向大叔的根节点

（3）.那如何确定每一颗树的元素个数呢？我们需要让根节点记录树的元素个数，其他节点没必要记录，这样可以节省内存空间，因为根节点的parent是不存在的，我们之前用-1表示，现在可以用-（树中的元素个数）表示，比如有7个元素，根节点的parent就为-7

[70]: /images/20220513/1aedb36218844b089c0e9a68fcf6dd95.png
[70 1]: /images/20220513/68819a22a95c426aaa4dd1ad018003c6.png
[70 2]: /images/20220513/e62f41f598164ab08b5000cc71c68345.png

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 MySQL笔记-子查询与集合运算

一、子查询子查询指在一个查询中嵌套另一个查询，可以多层嵌套。常出现在两个位置： 1）、from子句后：此用法也被称为行内视图，因为该子查询的实质就是一个临时

男娘i/ 2022年07月19日 06:25/ 0 赞/ 140 阅读

相关 Problem B: STL——集合运算

Problem B: STL——集合运算 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 2547 Solved

浅浅的花香味﹌/ 2022年06月18日 05:15/ 0 赞/ 158 阅读

相关 oracle集合运算

集合运算 > 主要运用 : 数据统计 > 并集: union > 交集 :interset > 差集:minus 使用oracle提供的scott用户进行演

迈不过友情╰/ 2022年06月04日 03:37/ 0 赞/ 221 阅读

相关集合的交并运算

数据结构链表实现集合的交并运算 //consts.h include<string.h> include<malloc.h> include<std

喜欢ヅ旅行/ 2022年06月04日 02:11/ 0 赞/ 232 阅读

相关 Java 集合运算（并集、交集与差集）

1、用法 [List obj1].retainAll([List obj2]); //交集 [List obj1].addAll([List obj2]

快来打我*/ 2022年05月24日 12:47/ 0 赞/ 244 阅读

相关树实现集合与运算

![70][] 如图，2棵树表示2个集合，用一个数组存储多棵树注意:（1）.用树表示集合，树的每一个节点代表集合中的一个元素，并且从上到下，从左到右放从小到大的元素（

浅浅的花香味﹌/ 2022年05月13日 01:24/ 0 赞/ 138 阅读

相关 Java 集合运算

问题描述给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。输入格式第一行为一个整数n，表示集合A中的元素个数。　　第二行有n个互不相同的

╰半夏微凉°/ 2022年04月23日 04:10/ 0 赞/ 134 阅读

相关 set和集合运算

set集合概念：set是可变的、无序的、不重复的元素集合。set的元素及元素里面的元素不能出现不可哈希类型。（即set的元素要求必须可以hash）

柔光的暖阳◎/ 2022年02月24日 07:27/ 0 赞/ 184 阅读

相关 python 集合运算

![1722024-20190718124935781-446108933.png][] ![1722024-20190718124946911-1179296755.png

妖狐艹你老母/ 2021年11月23日 12:44/ 0 赞/ 226 阅读

相关实现整数集合的并、交、差运算

问题：编写一个程序，实现一个整数集合的基本运算要求：输入整数集合\{2,4,1,3,5\}和\{2,5,10\}，输出前者的元素个数以及它们进行集合的并、交、差运算

怼烎@/ 2021年11月16日 09:04/ 0 赞/ 254 阅读