【澳门新濠城唯一网址】如何将一棵树转化为对应的二叉树,中并查集实现

发布时间:2019-10-09  栏目:编程  评论:0 Comments

github地址:

何谓并查集

并查集实际上就是并集和查集的过程。那么什么是集呢?你可以把他近似地理解为一棵树。即一个根结点连着无数个子节点。

如何将一棵树转化为对应的二叉树?

包含如下内容:1.该书的高清PDF2.chapter2~5为第二章到第五章的例题3.structure为链表节点与树节点的实现,在某些例题中多次使用,因此作为工具类单独放置。4.类文件的命名形式为[原书页号_题目名称],每道题目都包含相应的测试代码,保证可运行,绝非到处复制粘贴而来。5.有误之处,欢迎指正。

并查集的实现

给出例题:例题源网站澳门新濠城唯一网址,(洛谷)
这里附:
题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入输出格式

输入格式:
第一行包含两个整数N、M,表示共有N个元素和M个操作。

接下来M行,每行包含三个整数Zi、Xi、Yi

当Zi=1时,将Xi与Yi所在的集合合并

当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N

输出格式:
如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N

输入输出样例

输入样例#1:
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例#1:
N
Y
N
Y
这就是最最基础的并查集模版了

解答:

附:原书第二版已买,还没刷完,持续更新中剑指offerjava实现导航帖

初始化

我们会用到一个father数组,记录每一个节点的根结点
最初要把每一个节点都当作一个集,即

    father[i]=i;

这里我们需要用一个循环来实现,完整代码如下

    for(int i=1;i<=n;/*n即n个元素*/i++)
        father[i]=i;

然后初始化就完成啦。。

  1. 将 节点的孩子 放在左子树;

  2. 将 节点的兄弟 放在右子树。

函数

并查集一定会用到一个getfather函数(其实名字你随便起)
这个函数就是去找根节点

int getfather(int x)//找x的根结点
{//这其实是一个递归函数
    if(father[x]==x)//边界条件,如果x的根结点就是x(也就是说它没有更上边的祖宗了)
        return x;//就会返回x的值
    else
    {
        father[x]=getfather(father[x]); //不然的话就会一级一级找上去(先找到它爸爸,在找到它爸爸的爸爸,再找到它爸爸的爸爸的爸爸。。。。。)
    }
    return father[x];
}

例题:

读入

先上代码吧。。毕竟没什么难度

for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);//z1数组用于存储每一个x[i]的根结点
        z2[i]=getfather(y[i]);//z2数组用于存储每一个y[i]的根结点
    }

澳门新濠城唯一网址 1

留下评论

网站地图xml地图