当前位置: 首页 > news >正文

初识树(二叉树,堆,并查集)

   

  本篇博客将涉及到一些专业名词:结点、深度、根、二叉树、满二叉树、完全二叉树、堆、并查集等。


概要                                                                                                

        树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树,也就是说它常是根朝上,而叶朝下的。

        树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用,如在操作系统中,可用树来表示文件系统的结构。又如在数据库系统中,树形结构也是信息的重要组织形式之一 [1]。(来源《百度百科》)

         这是一棵树,我们把它倒过来,就是数据结构中的树了。

         树和图乍一看比较相似,但是图里面每个顶点之间是有回路的,但是在树中没有回路,树就是没有回路的连通无向图。如下图所示,左边是树,右边树图。

        Linux中的"tree"指令、家族谱,思维导图,树在生活中很常见,因为它一目了然。 

         我们对树进行一些定义,树是指任意两个结点有且仅有一条路径的无向图。没有回路的连通无向图就是树。

        数据结构中,树的形态可以是多变的,如上图所示,左右两边是同一棵树地不同形态。在树中的每一个点称为一个结点,我们为了更好地运用树和确定树的形态,我们在树中指定一个特殊的结点——根结点(也称祖先),根结点确定了,数的形态基本就确定了。

        树中的每个结点都有自己的深度,左边图中1的深度是1,2和3的深度是2,剩下的4、5、6、7深度为3;

        两个相邻深度中的相邻几个结点(如2、4、5)可以区分为父结点、子结点和兄弟结点。其中2为4、5的父结点,那么4、5就是2的子结点;4、5互为兄弟结点。

        没有父结点的就是根结点,没有子结点的就是叶结点,其余的叫做内部结点。

二叉树 

        顾名思义,二叉树就是每个结点最多只有两个子结点,左边为左儿子,右边为右儿子。二叉树有很多规律,帮助我们更好地解决问题。比如结点i,它的左儿子就是i*2,右儿子是i*2+1,它的父结点就是i/2。(均为整型,向下取整)

         

        二叉树可分为满二叉树和完全二叉树,满二叉树中每个内部结点都有两个儿子,所有叶结点地深度是一样的,严格定义:一个深度为h,且有2^h-1个结点的二叉树

        完全二叉树指除了最右边位置上有一个或者几个叶节点缺失外,其余都是满的。严格定义:若设二叉树的深度为h,除h层外,其它各层的结点数都达到最大,从h层从右向左连续缺若干个结点。这样就保证了如果一个结点有右结点,那么它一定有左结点。满二叉树可以理解为是一种完美的完全二叉树。

        

        满二叉树类似形状:

 

        因为二叉树是有规律的,所以我们通过一个一维数组便可以存储整个树。 如下图:

         如果一个完全二叉树有$N$个结点那么这个完全二叉树的深度为\log_2N+1,简写为log_2N,及最多有log_2N层结点。完全二叉树的最典型的应用就是——堆。

堆——优先队列

        堆是一种特殊的完全二叉树,利用$N$个结点深度为log_2N的特点,优化算法的时间复杂度。

如下图所示就是一个堆:

        

        特殊之处就是所有父结点都比子结点要小(本图中圆圈内为值,里面是编号)。 这个就是最小堆,相反如果所有父结点都比子结点要大那就是最大堆。

        现在我们要找出n个数中的最小值,直接遍历的话时间复杂度是O(N),除了n个这个操作的时间复杂度就是O(N^2),我们用堆就可以很好的优化。

        我们利用堆,就是在一次次构造堆,所以我认为会学会了构造堆就可以应用了。

最小堆

        我们现在有14个数:99、5、36、7、22、17、46、12、2、19、25、28、1、92。我们现在要构造一个最小堆。我们整个过程几乎只需要做一件事,那就是向下调整,保证每个子节点都小于父结点。(初始树如下)

        那么如何保证每个子节点都小于父结点呢?我们利用就像俄罗斯套娃的思路,从最后一个父结点开始,遍历每一个父节点,保证每一个父结点都小于它的子结点(兄弟结点之间的大小关系不用管)。也就是从N/2开始到第一个结点,这些都是父结点,通过这个这种方法我们便构造了一个最小堆,并且根结点一定是最小的这一点特别重要)。

        

        我们取出一部分来演示,我们从第N/2个结点开始(值为46结点),分别与其左右子结点比较(其只有一个结点,即左结点),方框内为每次形成的最小堆。注意红色和绿色箭头部分,如果我们按照红色箭头来走,那么值为1的结点的左儿子形成的堆就不是最小堆。

        因为在这个步骤中虽然保证了值为1的结点形成的是最小堆,但是由于交换的值36没有继续向下调整,不能保证下边还是最小堆,所以我们需要将每次交换的值继续向下调整,直到无法向下调整为止(绿色箭头所示)。

        这样我们就构成了一个最小堆,构成最小堆之后,我们可以交换根结点和第n个结点的值,然后输出n结点的值,再执行n--和将根节点向下调整;每次n--便是依次循环,直到所有结点全部输出,输出结点的顺序就是从小到大排列的顺序了。(这一点类似于队列出队)

        这样我们就通过一遍遍构建最小堆的方法,从小到大输出数值,这便是最小堆排序。

最大堆

        相比较最小堆,我认为更常用的是最大堆排序,因为最小堆是将原数组的数一个个全部取出来输出,如果想储存的话,还需要一个数组,而最大堆排序后直接从1到N输出原数组就是排序后的结果了。

        

        同一个数组构造最大堆,还是将根结点与n结点交换,还是n- -,还是向下调整,只不过每次是父结点都大于子结点,根节点为最大值,故每次交换后n结点都是最大值(n越来越小),这样的到的原数组就是从小到大排序了。 

        向下调整和向上调整 

        上边已经理清了堆排序的思路,现在还有一个重要的问题们就是如何向下调整(也可以向上调整)

        向下调整的话,因为叶节点没有子结点,所以我们只需要从N/2到1的每个结点进行向下调整就行了。每次的思路就是 $i$ 结点(1 \leq i \leq \frac{N}{2})、i*2结点、i*2+1结点,这三个结点选出最大的(最小堆就是选最小的),如果需要交换,就将新得到的子结点作为父结点继续向下交换,直到不能交换为止。 

/*最大堆*/
void siftdown(int i,int n,int *h)/*向下调整*/
{int t,flag=0;while (i*2<=n && flag==0){if (h[i] < h[i*2])/*与左儿子比较*/t=i*2;/*大的是左儿子*/else    t=i;/*大的是父亲*/if(i*2+1 <= n){if (h[t] < h[i*2+1])/*将t再与右儿子比较*/t=i*2+1;      }if (t!=i){swap(t,i,h);/*需要交换,将交换过的子节点作为父结点继续向下交换*/i=t;}else flag = 1;/*不需要再继续循环交换*/}   
}

        向上调整其实就是反过来,只不过它的范围要从N到2结点,故需要遍历N-1次,相比较向上调整时间多一点,因为只有根结点没有父结点。

void siftup(int i,int *h)/*向上调整*/
{int flag=0;if (i==1){return ;}while (i!=1 && flag == 0){//判断是否比父节点小if (h[i]<h[i/2]){swap(i,i/2,h);}else flag=1;i=i/2;}  
}

 最小堆排序完整代码

输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

输出:

1  2  5  7 12 17 19 22 25 28 36 46 92 99

#include<stdio.h>
#include<stdlib.h>
#include<string.h>void swap(int x,int y,int *num);
void siftdown(int i,int n,int *h)/*向下调整*/
{int t,flag=0;while (i*2<=n && flag==0){if (h[i] > h[i*2])t=i*2;else    t=i;if(i*2+1 <= n){if (h[t] > h[i*2+1])/*兄弟结点之间比较或者父子之间比较,保证与最小的交换*/t=i*2+1;      }if (t!=i){swap(t,i,h);i=t;}else flag = 1;}}void swap(int x,int y,int *num)
{int t;t=num[x];num[x]=num[y];num[y]=t;
}int main() 
{int n;scanf("%d",&n);int *num=(int *)malloc(sizeof(int)*(n+1));memset(num,0,sizeof(int)*n);for (int i = 1; i <= n; i++){scanf("%d",&num[i]);}for (int  i = n/2; i>=1; i--){for (int j = 1; j <= n; j++){printf("%8d",num[j]);}putchar('\n');siftdown(i,n,num);}for (int j = 1; j <= n; j++){printf("%8d",num[j]);}putchar('\n');for (int i = 1,n_falg=n; i <= n; i++){int t;t=num[1];num[1]=num[n_falg];n_falg--;siftdown(1,n_falg,num);printf("%3d",t);}return 0;
}

 最大堆排序完整代码

输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

输出:

1  2  5  7 12 17 19 22 25 28 36 46 92 99

#include<stdio.h>
#include<stdlib.h>
#include<string.h>void swap(int x,int y,int *num);
void siftdown(int i,int n,int *h)/*向下调整*/
{int t,flag=0;while (i*2<=n && flag==0){if (h[i] < h[i*2])/*与左儿子比较*/t=i*2;/*大的是左儿子*/else    t=i;/*大的是父亲*/if(i*2+1 <= n){if (h[t] < h[i*2+1])/*将t再与右儿子比较*/t=i*2+1;      }if (t!=i){swap(t,i,h);/*需要交换,将交换过的子节点作为父结点继续向下交换*/i=t;}else flag = 1;/*不需要再继续循环交换*/}   
}void swap(int x,int y,int *num)
{int t;t=num[x];num[x]=num[y];num[y]=t;
}int main() 
{int n;scanf("%d",&n);int *num=(int *)malloc(sizeof(int)*(n+1));memset(num,0,sizeof(int)*n);for (int i = 1; i <= n; i++){scanf("%d",&num[i]);}for (int  i = n/2; i>=1; i--){for (int j = 1; j <= n; j++){printf("%8d",num[j]);}putchar('\n');siftdown(i,n,num);}int n_flag=n;while (n_flag>1){for (int i = 1; i <= n; i++){printf("%5d",num[i]);}putchar('\n');swap(1,n_flag,num);n_flag--;siftdown(1,n_flag,num);}for (int i = 1; i <= n; i++){printf("%3d",num[i]);} return 0;
}

 并查集

        并查集(Disjoint Set Union,DSU)是一种森林结构,所谓森林结构,就是由多棵树组成的数据结构。

并查集支持两种操作:

  • 合并(Union):合并两个元素所属集合(合并对应的树)
  • 查询(Find):查询某个元素所属集合(查询对应的树的根节点),这可以用于判断两个元素是否属于同一集合

        我们直接看一道例题:

        擒贼先擒王

        快过年了,犯罪分子们也开始为年终奖“奋斗”了,小哼的家乡出现了多次抢劫事件。由于强盗人数过于庞大,作案频繁,警方想查清有几个犯罪团伙不太容易,不过警察收集到了一些线索,需要咱们帮忙分析一下:

        现在有10个强盗,关系如下:

1号强盗与2号强盗是同伙。

3号强盗与4号强盗是同伙。

5号强盗与2号强盗是同伙。

4号强盗与6号强盗是同伙。

2号强盗与6号强盗是同伙。

8号强盗与7号强盗是同伙。

9号强盗与7号强盗是同伙。

1号强盗与6号强盗是同伙。

2号强盗与4号强盗是同伙。

        有一点需要注意:强盗同伙的同伙也是同伙,你能帮助警方查出有多少个独立的犯罪团伙嘛?

        这十个强盗就可以看成是10颗树,如果两个强盗之间是同伙就把他们连线,形成一片森林,最后有几个森林就代表有几个犯罪团伙。思路很好理解,接下来就是通过代码实现。

        我们用一个数组num来表示这个树,数组大小为n,每个数的初始化为自己的下标,代表自己的父节点为自己,即自己构成一个树林,初始的时候有十个树林(每个森林都是以树这个数据结构储存)。

        这里我们就规定如果x号强盗与y号强盗是同伙。那么x就是y的父节点。(成为“靠左定则”)

num[y]=x;

        通过这一个操作,我们边=便已经形成了上边那张图,我们通过肉眼区分,直到这是三个森林,但怎么样让计算机知道呢?

        这里采用的方法是通过判断num[y]==y来做的,如果等于,那就代表有一个森林,因为一个森林中只有一个根结点,只有根结点才指向自己

        这个时候我们就需要对上边大代码进行修改了,我们将上边的图稍微整理一下就会发现问题:这更像是一个图,而不是树!        

         那么我们就需要把这个图转化为树,来解决这个问题,怎么转化呢?我们要保证每一个结点只有一个父节点

        这里我们重新模拟一下这个过程:

1号强盗与2号强盗是同伙。

3号强盗与4号强盗是同伙。

5号强盗与2号强盗是同伙。

        再执行第三个线索的时候,发现2结点已经有一个父结点了,不能再有第二个父结点了,这里2已经和别的结点构成一个森林,森林中只有根结点没有父结点,这里我们采用的方法是将2结点的根结点作为y,5结点为x,做 $num[y]=x$ (如果 x 也有父节点,那么也是找到这个森林的根节点作为 y) ,这样便完美解决了这个问题,如下图所示:

     

        通过这样的方法执行,便形成了树: 

        代码实现(引入了路径压缩): 

int getf(int v,int *num)
{if (num[v]==v)/*v结点就是根结点*/{return v;}else{/*这里是路径压缩,每次在函数返回的时候,顺带把路上遇到的v的父节点改为最后找到的祖宗编号,这样可以提高通过v找祖先的速度*/num[v]=getf(num[v],num);/*寻找v的父结点,路径压缩*/return num[v];}}void Union(int x,int y,int *num){int t1=getf(x,num);/*判断x是不是本森林的根节点*/int t2=getf(y,num);/*判断y是不是本森林的根节点*/if (t2!=t1)/*t1与t2不属于同一个森林*/{num[t2]=t1;}return ;}

        输入:m+1行,第一行输入n,m代表罪犯人数和显示,接下来m行输入x,y代表x号强盗与y号强盗是同伙

 11 10

1 2

3 4

5 2

4 6

2 6

7 11

8 7

9 7

9 11

1 6

输出:一个数字代表犯罪团伙 

3

完整代码:

 #include<stdio.h>#include<stdlib.h>#include<string.h>int getf(int v,int *num)
{if (num[v]==v)/*v结点就是根结点*/{return v;}else{num[v]=getf(num[v],num);/*寻找v的父结点*/return num[v];}}void Union(int x,int y,int *num){int t1=getf(x,num);/*判断x是不是本森林的根节点*/int t2=getf(y,num);/*判断y是不是本森林的根节点*/if (t2!=t1)/*t1与t2不属于同一个森林*/{num[t2]=t1;}return ;}int main(){int n,m;scanf("%d%d",&n,&m);int * dis=(int *)malloc(sizeof(int)*(n+1));for (int i = 0; i <= n; i++){dis[i]=i;}for (int i = 1,x,y; i <= m; i++){scanf("%d%d",&x,&y);Union(x,y,dis);/*靠左定则*/}int sum=0;for (int i = 1; i <= n; i++){if (dis[i]==i){// printf("dis=%d\n",dis[i]);/* 根结点 */sum++;}}printf("%d",sum);return 0;}

参考文献

《啊哈!算法》

算法导论之树形数据结构——并查集 - 知乎


http://www.mrgr.cn/news/79270.html

相关文章:

  • redis击穿,穿透,雪崩以及解决方案
  • Multimodal Few-Shot Learning with Frozen Language Models译文
  • 前端速通Blob、File、FileReader、ArrayBuffer、Base64...
  • Delphi-HTTP通讯及JSON解析
  • Yocto bitbake and codeSonar
  • 单链表---合并两个链表
  • Yagmail邮件发送库:如何用Python实现自动化邮件营销?
  • 【0356】Postgres内核 XLOG读取之 打开一个 logfile segment ( 3 - 1 )
  • MongoDB的简单使用
  • 深入浅出:SOME/IP-SD的工作原理与应用
  • axios笔记
  • HTML笔记()蜘蛛纸牌之卡牌拖拽
  • 基于STM32F4实现步进电机闭环控制实现(无PID)
  • python 装饰器学习与实践
  • javaScriptDOM获取
  • 源码分析之Openlayers图层篇概览
  • OpenBayes贝式计算创始人受邀参加第九届中国开源年会,分享 AI4S 前沿洞察
  • Elasticsearch 入门
  • 每日速记10道MySQL面试题15
  • UE4_材质节点_有关距离的_流体模拟