【数据结构】堆和二叉树详解——上

前言：上一篇文章我们介绍了栈和队列，这篇文章我们就来介绍一下堆和二叉树。

1，树

1.1树的概念与结构

在这里插入图片描述

树相信大家在日常生活都见过，它就是一种植物根在下叶子在上是向上生长的。而据结构里的树刚好相反。

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

数据结构里的树长这样：

每一个圈都代表一个结点，每一根线就是边数，可以把他们想象成树枝。

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

有一点要注意的是：树形结构中，子树之间不能有交集，否则就不是树形结构

下面我们来看一些非树形结构的图：

在这里插入图片描述

这些都是非树形结构： 图一的子树相交了，但树形结构要求子树不能相交。 图二的违反了一个儿子结点只能对应一个父亲的原则。 图三与图二一样，而且在树形结构中一棵N个结点的树有N-1条边。

以上什么父亲，儿子看不懂没关系接下来我们就来学习一些树相关的一些术语。

1.2树相关的术语

在这里插入图片描述

如何理解这一大串文字呢？方法其实很简单，只要你知道人们生活中的关系辈分就可以理解了，这些名词既然是人设计的那么人就会习惯采用日常生活中人人皆知的关系辈分。比如A是所有子树的祖先，DEFG分别为HIJ KL MN的父亲，IJ KL MN之间是亲兄弟关系，以此类推。

了解了树的一些术语之后我们怎么来表示它呢？

1.3树的表示方法

最常用的表示方法是孩子兄弟表示法： 树结构相对线性表就比较复杂了，要存储表示起来就比较⿇烦了，既然保存值域，也要保存结点和结 点之间的关系，实际中树有很多种表示⽅式如：双亲表示法，孩⼦表示法、孩⼦双亲表示法以及孩⼦ 兄弟表示法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表示法。

struct TreeNode 
{ 
	struct Node* child; // 左边开始的第⼀个孩⼦结点 
	struct Node* brother; // 指向其右边的下⼀个兄弟结点 
	int data; // 结点中的数据域 
};

在这里插入图片描述

1.4 树形结构的实际运用场景

文件系统是计算机存储和管理文件的⼀种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间 的关联。

在这里插入图片描述

2，二叉树

2.1概念和结构

在树形结构中，我们最常用的就是二叉树，一棵二叉树是结点的⼀个有限集合，该集合由⼀个根结点 加上两棵别称为左子树和右子树的二叉树组成或者为空

前面我们介绍了树，树是一种非线性的数据结构它的枝数没有规定，那二叉树顾名思义就是只有两个树枝的树，现实中存在这样的树吗？其实是存在的。

在这里插入图片描述

我们可以根据上面二叉树的真实的样子来画出数据结构中的二叉树的样子：

在这里插入图片描述

通过上图我们可以得到二叉树的几个特点：

1. ⼆叉树不存在度大于 2 的结点 即要么有一个孩子或两个孩子 要么没有。
2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树 。

注意：对于任意的⼆叉树都是由以下几种情况复合而成的：

在这里插入图片描述

2.2特殊的二叉树

既然二叉树是我们最常用的那我们肯定要学习一些特殊的二叉树：

2.2.1 满二叉树

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀ 个⼆叉树的层数为 K ，且结点总数是 2k − 1 ，则它就是满⼆叉树。

在这里插入图片描述

2.2.2完全二叉树

完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个 结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称 之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

在这里插入图片描述

二叉树的性质：

根据满⼆叉树的特点可知： 1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2i−1 个结点 2）若规定根结点的层数为 1则深度为 h 的⼆叉树的最⼤结点数是 2h − 1 比特就业课 3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 h = log2 (n + 1) ( log 以2为底， n+1 为对数)

2.3二叉树的存储结构

二叉树一般有两种存储方式一种是顺序存储，一种是链式存储。

1，顺序存储 先来看顺序存储：看到顺序就不禁联想到顺序表，而顺序结构的二叉树的底层就是顺序表：

在这里插入图片描述

顺序表里所存储的结点的值依次按照二叉树从左往右的顺序来存储，那如果是非完全二叉树的存储呢？

在这里插入图片描述

从图中可以看到非完全二叉树如果还是按照顺序存储那难免还会有空间剩余，造成空间浪费，所以存储完全二叉树我们使用顺序表，那存储非完全二叉树我们使用什么存储呢？

其实大家应该很快就会想到使用链表，因为顺序表和链表经常作为数据结构的底层，这个地方顺序表会造成空间的浪费那么用链表就能很好的解决这一问题。

2，链式存储 ⼆叉树的链式存储结构是指使用一个链表来表示一颗二叉树，链表包括三个部分一个数据和两个指针，分别指向左孩子和右孩子。这样每一个二叉树每一个结点都是独立的空间不会再有空间浪费。链式结构又分为二叉链和三叉链，但我们目前数据结构初阶一般都是二叉链。

在这里插入图片描述

在这里插入图片描述

了解完以上内容，紧接着我们就来模仿实现一些顺序结构的二叉树。在模仿之前我们还要介绍一个新概念——堆。

3，堆的概念和结构

如果有⼀个关键码的集合 ，把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储，在⼀个⼀维数组中，并满⾜： K = {k0 , k1 , k2 , …，kn−1 } K <= i K2∗i+1 Ki >= K2∗i+1 K <= i K2∗i+2 （ 且 ）， i = 0、1、2… ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。

上面的概念看不懂没关系你只要记住，这里的堆说的是一种二叉树，这里说的堆要与操作系统虚拟进程地址空间中的堆区分开。一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.1堆的分类

堆分成大根堆和小根堆：

在这里插入图片描述

⼆叉树性质 • 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有： 1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点 2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦ 3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

3.2堆的实现

首先要想实现堆就要先定义一个堆结构：

<在.h文件中>
//定义堆 底层使用数组
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	HPDataType size;//有效数据个数
	HPDataType capacity;//空间大小
}HP;

接着对堆进行初始化：

<在.c文件中>
//初始化
void HPInit(HP* php)
{
	php->arr = NULL;//初始时没有数据置为空
	php->size = php->capacity = 0;
}

有了堆的结构接下来我们就可以来实现增，删，查，改等操作了。

增(入堆)

入堆操作：

在这里插入图片描述

·上图以小根堆为例，插入数据是在数组size处的位置插入；这样做的原因是不打乱堆的结构。（size是专门计算有效数据个数的，插入一个数据有效数据个数加加） ·插入完成后，此时插入的数据可能会影响堆的结构也可能不会，上图插入一个5就影响了小根堆的结构所以需要向上调整,无论是大根堆还是小根堆插入的数据影响堆的结构都需要向上调整

向上调整算法

在这里插入图片描述

向上调整算法的具体过程： 小根堆

在这里插入图片描述

大根堆过程：

在这里插入图片描述

<.h文件中>
//向上调整
void AdjustUp(HPDataType* arr, int child);

//向上调整
void AdjustUp(HPDataType* arr, int child)
{
	//如果是大根堆 >
	
	//如果是小根堆 <
	int father = (child - 1) / 2;
	while (child>0)//father!=0
	{
		if (arr[child] < arr[father])
		{
			//交换封装成一个函数
			Swap(&arr[father], &arr[child]);//传过去的是对应下标的地址
			child = father;
			father = (child - 1) / 2;
		}
		else//
		{
			break;
		}
	}
}

//交换函数
void Swap(int* x, int* y)
{
	int tmp = 0;
	tmp = *x;
	*x = *y;
	*y = tmp;
}

入堆的完整代码：

<在.h文件中定义> 
//插入数据
void HPPush(HP* php, HPDataType x);

//插入数据
void HPPush(HP* php, HPDataType x)
{
	assert(php);//堆不能为空
	//判断空间是否足够

	//不够开辟空间
	if (php->size == php->capacity)
	{
		HPDataType newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("malloc fail!");
			exit(1);
		}
		//到这开辟成功 更新size和capacity
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	//足够直接插入
	php->arr[php->size] = x;//这里size不着急++ 因为还没判断说大堆 还是小堆
	//插入完数据要进行调整
	AdjustUp(php->arr,php->size );
	//调整结束后 size要加加 插入一个数据有效数据个数加一
	++php->size;
}

删(出堆)

入堆(插入数据时)是从数组的尾部去插入，那么删除数据也是从尾部去删除吗？因为数组头尾插入或删除的时间复杂度很低。

但万一有人想删除堆顶的数据呢？或者删除其他地方的数据呢？所以直接从尾部去删除是不好的，但我们可以换一个方式，将想删除的那个数据与最后一个数据交换然后再直接尾删这样就能达到时间复杂度为O(1)。下面我画图让各位读者更加清晰：

在这里插入图片描述

从上面可以看出当我们交换完了数据以后，堆的结构就被打乱了，此时我们需要重新调整，怎么调整呢？向下调整，因为我们是与堆顶的数据交换堆顶的数据不满足要求所以需要向下调整。

向下调整算法

在这里插入图片描述

向下调整算法的具体过程：

在这里插入图片描述

在这里插入图片描述

特殊情况：

在这里插入图片描述

<在.h文件中>
//向下调整
void AdjustDown(HPDataType* arr, int father, int n);

//交换完数据就向下调整
void AdjustDown(HPDataType* arr, int father, int n)
{
	//大堆 找大>
	//小堆 找小<

	//根据father找child
	int child=0;
	child = father * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])//child+1<n 保证右孩子也不能越界
		{
			child++;
		}
		if (arr[child] < arr[father])
		{
			Swap(&arr[child], &arr[father]);
			father = child;
			child = father * 2 + 1;
		}
		else//到这说明孩子结点大于父结点不需要调整
		{
			break;
		}
	}
	
}

出堆的完整代码：

<在.h文件中定义> 
//出数据 出堆
void HPPop(HP* php);

//出数据 出堆
void HPPop(HP* php)
{
	//判断堆是否为空
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size-1]);
	--php->size;
	//调整
	AdjustDown(php->arr,0,php->size);
	//                堆顶下标father结点   size有效数据个数
}

判空和取堆顶数据

<在.h文件中定义> 
//取堆顶数据
HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);

由于数据内部是由size计算有效数据个数的，那么直接返回size看size是否为零就知道堆是不是空的了。

//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;//有效数据个数为零就说明为空
}

取堆顶数据则直接返回第一个数据。

HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}

堆的销毁

由于堆是动态申请的，在前面的数据结构的销毁中也讲过，向内存申请的空间在不用的时候就要销毁避免空间的浪费。

//销毁
void HPDestroy(HP* php);

//销毁
void HPDestroy(HP* php)
{
	//判断数组是否为空
	if (php->arr)
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->capacity = php->size = 0;
}

至此就是堆的实现了。

3.3向上调整/向下调整算法的时间复杂度

向上调整算法的时间复杂度：

在这里插入图片描述

向下调整算法的时间复杂度：

在这里插入图片描述

4，堆的应用

到这就有人要问了，学了这么多堆的知识有什么用呢？紧接着我们就来讲用堆实现的一种功能——堆排序。 有两个版本:

<第一个版本是依靠数据结构堆来实现>

在这里插入图片描述

void HeapSort(int* a, int n)
{
	HP hp;
	HPInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, a[i]);
	} 
	int i = 0;
	while (!HPEmpty(&hp))
	{
		a[i++] = HPTop(&hp);
		HPPop(&hp);
	} 
	HPDestroy(&hp);
}

这个方法实现的前提是要实现数据结构堆来实现，换句话说就是要自己造轮胎才能使用的方法。

<第二个版本是不需要自己造轮胎，借助堆调整的思想来实现堆排序>

先来看看整体思路：

在这里插入图片描述

在这里插入图片描述

再来看看大堆取的情况：

在这里插入图片描述

说完了向下调整建堆排序我们再来看看向上调整建堆：

这里是引用

具体的调整过程:

在这里插入图片描述

//堆排序
//排升序--- 建大堆
//排降序--- 建小堆
void HeapSort(int* arr, int n)
{
	//建堆——向下调整算法建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	//堆排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

版本二只需要完成向下调整算法和向上调整算法的编写就可以完成堆排序，所以说是借助了堆调整的思想来进行排序。

5，TOPK问题

透过堆排序我们顺便来讲一讲TOPK问题，为什么说是透过堆排序来讲TOPK呢？是因为TOPK问题也运用了类似堆排序的思想。

那什么是TOPK问题呢？

TOPK问题就是给出你100000个数据或者更大的数据，让你在其中找出指定的前K个最大或最小的数据。

要解决这一问题我们还有解决一个问题，就是这些数据存在哪里？

如果存在数组里很明显是不合适的，因为数据量非常大存在数组里很消耗空间，但如果空间足够也是可以的。另一种方法就是存在文件中，在文件中读取数据。 既然要把数据放在文件中那我们肯定需要造数据：

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

造完数据后我们就要开始找出最大或最小的K个数据，思路如下：

在这里插入图片描述

void TopK()
{
	printf("请输入k：");
	int k = 0;
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE*fout= fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		exit(1);
	}

	//根据k动态开辟k个大小的空间
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		exit(2);
	}
	for (int i = 0;i < k;i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}

	//第一步向将前k个数据建堆
	for (int i = (k - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(minHeap, 0, k);
	}

	//第二步找最大的前k个数据 遍历后n-k个数据谁小谁与堆顶交换 找最小的前k个数据反之
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}

	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);
}

总结： TOPK问题最核心的就是利用了调整建堆算法，很巧妙的将最大或最小的K个数据控制在一个堆中。

最后再来看看堆排序的时间复杂度：O(N)=K+(N-K)logK。

以上就是本章的全部内容啦！ 最后感谢能够看到这里的读者，如果我的文章能够帮到你那我甚是荣幸，文章有任何问题都欢迎指出！制作不易还望给一个免费的三连，你们的支持就是我最大的动力！