堆和二叉树（1）

🕗 发布于 2024-10-12 11:05 算法 c语言 数据结构

文章目录

前言
一、树的概念与结构
二、二叉树
总结

前言

今天呢小编要跟大家分享一下数据结构里面的一个新的板块——二叉树小编呢将会与大家分享关于二叉树的相关知识与其运用领域。那接下来我们一起来看看什么是二叉树吧！
在这里插入图片描述

一、树的概念与结构

想要了解二叉树的话，那我们就要先了解数的概念与结构：

1.树的概念：树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的

在这里插入图片描述

1.有一个特殊的结点，称为根结点（上图中A），根结点没有前驱结点
2.除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
3.因此，树是递归定义的。

但是这里要注意一个点就是：树形结构中，子树之间不能有交集，否则就不是树形结构
在这里插入图片描述
2.树的相关概念：

结点的度：一个结点含有的子树的个数称为该结点的度；如上图：A的为6
叶结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I…等结点为叶结点
非终端结点或分支结点：度不为0的结点；如上图：D、E、F、G…等结点为分支结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点
树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为6
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
树的高度或深度：树中结点的最大层次；如上图：树的高度为4，同时这里也可以是3，但是如果是空树的话那树的高度就是-1了，所以这里就感觉感觉怪怪的。所以一般情况我们都是从1开始数的。
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

树在实际中的运用（表示文件系统的目录树结构）
在这里插入图片描述

二、二叉树

在我们了解完树的相关知识之后呢，那我们现在就来来认识一下二叉树吧！

1.二叉树的概念与结构

概念：一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成
在这里插入图片描述
注意 !：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
3.对于任意的二叉树都是由以下几种情况复合而成的：

在这里插入图片描述
了解到二叉树概念及结构之后，我们在来了解一下两个特殊的二叉树：满二叉树，完全二叉树
满二叉树：
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。
在这里插入图片描述

完全二叉树：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

2.二叉树的储存

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的会分享。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

在这里插入图片描述

我们看看第二张图，可以看到这是一个非完全二叉树的储存图。那我们这里可不可以在数组哪里依次储存呢?答案是肯定不行滴，为什么呢？如果我们这里依次储存的话，那我这里在逻辑上是不是就不满足二叉树的概念啦。这里呢是可以储存的，但是会存在空间浪费的情况哦。
2. 链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

3.二叉树储存的实现

这里如果我们想把二叉树储存到数组之中，那么我们这里就要引入堆的概念了。那什么是堆呢？其实堆他就是一棵完全二叉树，而且堆中某个结点的值总是不大于或不小于其父结点的值
然而堆我们又分为大堆和小堆
那他们有啥不一样呢？
在这里插入图片描述

1.堆的向上调整（堆的插入）

我们现在来实现一个二叉树的插入，其实就是堆的插入。这里呢就要用到顺序表了。我们先来看看堆是这样插入数据的，
在这里插入图片描述
我们可以看出如果我们想插入一个数据的话，那么我们每个插入一个数据都要和他的祖先进行比较，看看是否满足大堆或者小堆的概念。如果满足，那就不用交换，如果不满足那就需要交换一下了。
先看代码是咋样实现的：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SListNode
{
SLDataType* arr;
SLDataType szie;
SLDataType capacity;
}SLTNode;
void SLInit(SLTNode* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->szie = 0;
}
void SLDestorty(SLTNode* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->szie = 0;
}
void Swap(SLDataType* p1, SLDataType* p2)
{
SLDataType* tmp = * p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(SLDataType* arr, int chiled)
{
int parent = (chiled - 1) / 2;
while (chiled >= 0)
{
if (arr[chiled] < arr[parent])
{
Swap(&arr[chiled], &arr[parent]);
chiled = parent;
parent = (chiled - 1) / 2;
}
else
{
break;
}
}
}
void SLPush(SLTNode* ps, SLDataType x)
{
assert(ps);
if (ps->capacity == ps->szie)
{
SLDataType newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail\n");
exit(1);
}
ps->arr = tmp;
ps->capacity =newcapacity;
}
ps->arr[ps->szie] = x;
ps->szie++;
AdjustUp(ps->arr, ps->szie - 1);
}
int main()
{
int arr[] = { 4,2,8,1,5,6,9,7 };
SLTNode ph;
    SLInit(&ph);
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
SLPush(&ph, arr[i]);
}
return 0;
}

这上面都是相关的顺序表，然而这段代码才是堆插入的主要代码：

void AdjustUp(SLDataType* arr, int chiled)向上调整
{
int parent = (chiled - 1) / 2;
while (chiled >= 0)
{
if (arr[chiled] < arr[parent])
{
Swap(&arr[chiled], &arr[parent]);
chiled = parent;
parent = (chiled - 1) / 2;
}
else
{
break;
}
}
}

这里的chiled就是孩子节点，也就是我们插入的那个节点。parent就是父亲节点。这里需要注意的就是循环哪里的结束条件，其实这里填parent>=0代码也是可以跑起来的，而且刚好跑过。严格来讲的话这里是不能这样写的，但是这里是属于歪打正着刚好跑过了。
在这里插入图片描述

2.堆的向下调整（堆的删除）

堆的删除其实就是删除堆顶的数据。那这里我们可不可以直接把arr[0]位置的数据删除就行了呀？从物理结构上来说是可以的。那我们再来先想想如果真的这样操作的话，那是不是就不满足二叉树的概念了呀?那我们要怎么样操作呢？其实这里我们只需要将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述
解决思路：
这里可以看见当我们堆顶和最后一个数据交换之后呢，然后size–就直接删除堆顶的数据了，但是这个时候这个逻辑结构就不构成一个堆呀？那想要他变成堆呢？所以这里需要我们把他调整成堆，这里我们可以看见图中我们是调整的是小堆。也就是向下调整。那该这样调整呢？我们先让28和他的左右孩子其中最小的一个进行比较，如果他的左右最小的一个孩子比他小，那就交换一下，反之就直接跳出程序。
先来看代码实现：

void AdjustDown(HPDataType* arr, int n, int parent)//向下调整
{
//假设法
HPDataType chiled = parent * 2 + 1;
while (chiled < n)
{
if (chiled+1<n&&arr[chiled + 1] < arr[chiled])
{
++chiled; 
}
if (arr[chiled] < arr[parent]) 
{
Swap(&arr[chiled], &arr[parent]); 
parent = chiled; 
chiled = parent * 2 + 1; 
}
else
{
break;
}
}
}
void PHPop(HP* ps)
{
assert(ps);
assert(ps->size > 0);
Swap(&ps->arr[0], &ps->arr[ps->size - 1]);
ps->size--;
AdjustDown(ps->arr, ps->size , 0);
}

代码分析：
这里呢有一个难点，那就是如何找左右孩子中最小的一个孩子呢？这里就需要一个假设法了。这里我们直接假设左孩子是最小的。这里需要注意循环的结束条件和假设法的判断条件。因为这里chiled>n,那如果chiled+1>n的话那是不是就以及越界了。所以这里才会对一个判断chiled+1<n条件。

3.取出堆顶数据和判断是否为空堆

HPDataType HPTop(HP* ps)//取堆顶数据
{
assert(ps);
assert(ps->size > 0);
return ps->arr[0];
}
bool HPEmpty(HP* ps)
{
assert(ps);
return ps->size == 0;
}

4.堆的运用

那么堆在生活中运用是怎样实现的呢？这里我们可以运用堆来在一大堆数据中找出前几个最大和最小的数据。比如我们这里给一串数据，想的到最小的前K位数。

int main()
{
int arr[] = { 4,2,8,1,5,6,9,7,15,4,8,9,48,79,99,66,33,55,21 };
HP pq;
HPInit(&pq);
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
HPPush(&pq, arr[i]);
}
int k = 0;
printf("请输入想获取几位数 ：\n");
scanf_s("%d", &k);
while (k--)
{
printf("%d ", HPTop(&pq));
PHPop(&pq);
}
/*while (!HPEmpty(&pq))
{
printf("%d ",HPTop(&pq));
PHPop(&pq);
}*/
printf("\n");
printf("\n");
return 0;
}

在这里插入图片描述
之后呢我们还会了解到Top-K问题。那个将会涉及到堆的排序，我们下一章会跟大家分享的。还有建堆，算堆的复杂度以及相关知识。

总结

好啦。今天就到这里吧，之后还会分享相关知识，希望大家观摩讨论。虽然生活很枯燥，但是依然有你觉得值得东西，朝着梦的方向加油吧！
在这里插入图片描述

原文地址：https://blog.csdn.net/jhj9201633/article/details/142728291

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：k3s安装指定版本以及离线安装（docker)
下一篇：Linux线程