【数据结构】二叉树顺序结构及实现

客官°小女子只卖身不卖艺 2024-04-26 10:58 189阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：[初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一. 二叉树的顺序结构
 *  二.堆的概念及结构
 *   *  小根堆：
     *  大根堆：
     *  注意：
 *  三.堆的实现：
 *   *  1.堆的插入(向上调整算法）：
     *  2.堆的删除（向下调整算法）：
     *  3.堆的构建：
 *  三.堆的应用：
 *   *  1.堆排序：
     *   *  步骤1：建堆：
         *   *  向上调整建堆：
             *  向下调整建堆：
         *  步骤2：堆删除思想：
     *  2.TOP-K问题
 *  总结

## 前言 ##

在前面的学习中，我们实现了栈与队列的实现。今天我们就通过顺序表来实现二叉树！  
![在这里插入图片描述][1304f5049c4f4a408a4df6230bf1cde5.png]

## 一. 二叉树的顺序结构 ##

我们如何让顺序表和二叉树建立联系呢？

我们可以先对二叉树的每个结点进行编号，通过数组的连续排列建立以下联系：  
![在这里插入图片描述][be49312fb955419db247f7bc0fb63da4.png]  
这样我们就可以通过数组的下标来模拟实现二叉树了！  
![在这里插入图片描述][7b8762be37f9410bafa9ea33e7cd81d3.png]  
但是普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。  
![在这里插入图片描述][18b40ce79f1347b8b84630a6bb98756d.png]  
所以我们的**数组存储表示二叉树**只适合**完全二叉树**。

## 二.堆的概念及结构 ##

![在这里插入图片描述][d0fe48ae29b94f44a331bd4bc03821a7.png]  
简单的来说，**堆**就是**一颗完全二叉树**，并且有以下性质：

*  堆中**某个节点的值**总是**不大于**或**不小于**其**父节点**的值；
 *  堆总是**一棵完全二叉树**。

其中分为小根堆和大根堆：

### 小根堆： ###

树中所有父亲都小于等于孩子：  
![在这里插入图片描述][f89d367936324d10b7330b3fbc619dfb.png]

### 大根堆： ###

树中所有父亲都大于等于孩子  
![在这里插入图片描述][b2140a0239354853b310ba2312b19d0d.png]

### 注意： ###

在数据结构里面我们所学的栈，堆都是一种数据结构，他们与操作系统  
中的栈和堆是两回事，一个是数据结构，一个是操作系统相关的知识，一定不要搞混淆！

## 三.堆的实现： ##

typedef int HPDataType;
    typedef struct Heap
    {
        
    	HPDataType* a;
    	int size;
    	int capacity;
    }HP;
    
    void HeapInit(HP* php);
    void HeapDestroy(HP* php);
    
    void HeapPush(HP* php, HPDataType x);
    void HeapPop(HP* php);
    HPDataType HeapTop(HP* php);
    bool HeapEmpty(HP* php);
    int HeapSize(HP* php);
    
    void AdjustUp(HPDataType* a, int child);
    void AdjustDown(HPDataType* a, int n, int parent);

### 1.堆的插入(向上调整算法）： ###

先插入一个数到数组的尾上，再进行**向上调整算法**，**直到满足堆**。

向上调整算法的条件是：

**除了child结点，之前的结点都是堆**  
![在这里插入图片描述][ad740e4e1f904fb9ad8b531e1b8043e4.png]  
代码实现：

void AdjustUp(HPDataType* a, int child)
    {
        
    	int parent = (child - 1) / 2;
    	while (child>0)
    	{
        
    		if (a[child] > a[parent])
    		{
        
    			swap(&a[child],&a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
        
    			break;
    		}
    	}
    }
    void HeapPush(HP* php, HPDataType x)
    {
        
    	assert(php);
    	if (php->capacity == php->size)
    	{
        
    		HPDataType* ptr = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
    		if (ptr == NULL)
    		{
        
    			perror("realloc::fail");
    			return;
    		}
    		php->a = ptr;
    		php->capacity *= 2;
    	}
    	php->a[php->size] = x;
    	php->size++;
    
    	AdjustUp(php->a, php->size-1);
    }

### 2.堆的删除（向下调整算法）： ###

在这里删除堆是指删除堆顶的数据，因为删除堆尾元素没有什么实际的意义。将堆顶的数据与最后一个数据一换，然后**删除数组最后一个数据**，再**进行向下调整算法。**

向下调整算法的条件是：

**左右子树都为堆！**  
![在这里插入图片描述][0ae7df0eef554abdaece48964d9b6ad9.png]  
代码实现：

void HeapPop(HP* php)
    {
        
    	assert(php);
    	assert(!HeapEmpty(php));
    
    	// 删除数据
    	Swap(&php->a[0], &php->a[php->size - 1]);
    	php->size--;
    
    	AdjustDown(php->a, php->size, 0);
    }
    void AdjustDown(HPDataType* a, int n, int parent)
    {
        
    	int child = parent * 2 + 1;
    	while (child < n)
    	{
        
    		// 选出左右孩子中大的那一个
    		if (child + 1 < n && a[child+1] > a[child])
    		{
        
    			++child;
    		}
    
    		if (a[child] > a[parent])
    		{
        
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
        
    			break;
    		}
    	}
    }

### 3.堆的构建： ###

这里建议把后面的**堆排序**看了在来看这段代码：

void HeapInitArray(HP* php, int* a, int n)
    {
        
    	assert(php);
    
    	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    	if (php->a == NULL)
    	{
        
    		perror("malloc fail");
    		return;
    	}
    
    	php->size = n;
    	php->capacity = n;
    
    	// 建堆
    	for (int i = (n-2)/2; i >= 0; --i)
    	{
        
    		AdjustDown(php->a, php->size, i);
    	}
    }

这里的意思是给你一个属数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

## 三.堆的应用： ##

### 1.堆排序： ###

通过上面的学习我们发现，堆有排序的功能。但是如果我们要通过每次建堆的方式来排序，那还是挺浪费空间的。为什么不在**原有的数组里面进行堆排序呢**？  
堆排序即利用堆的思想来进行排序，总共分为**两个步骤**：

1.  **建堆**  
    升序：**建大堆**  
    降序：**建小堆**
2.  利用**堆删除思想**来进行排序

在这里会有同学问道，根据堆的性质，大堆不就是降序，小堆不就是升序吗？**为什么升序要建大堆，降序要建小堆呢？**

其实啊，我们的堆在数组中的排序并不是完全的。对于**升序**，如果我们非要通过建小堆来排序，只能通过**拿走堆顶**，然后将**剩下的元素进行重新建立大堆的方式**来寻找**第二小的元素**，这样的时间效率会非常低，而且过程非常的麻烦。  
![在这里插入图片描述][1f3af13a506043a186a329fc4563d4fa.png]  
那么我们应该怎么做呢？

#### 步骤1：建堆： ####

##### 向上调整建堆： #####

向上调整建堆就相当于堆的插入，在原数组的空间里，每插入一个数，就向上调整一遍，代码如下：

void Heapsort(HPDataType* a, int n)
    {
        
    	for (int i = 0; i < n; i++)
    	{
        
    		AdjustUp(a, i);
    	}
    }

当然我们可以来看看这种方法的时间复杂度：  
![在这里插入图片描述][f8c639b0c4594855845a6ef553d69057.png]  
通过**求和：**  
![在这里插入图片描述][c8fd4c37c0da41eda10af7c0743fce6e.png]  
通过**错位相减法**可以得到：  
![在这里插入图片描述][2ec4ac8cff93441cb555d5e7b941dd7f.png]  
由此可见，向上调整建堆的**时间复杂度为O(N\*logN)**

##### 向下调整建堆： #####

既然我们可以向上调整建堆，能不能向下调整建堆呢？答案是肯定的，只要我们找到**最后一个叶子结点的父结点**，把**该结点及该结点以前的结点向下调整**，这样就可以很好的建堆了。代码如下：

//向下调整建堆
    	for (int i = (n - 2) / 2; i > 0; i--)
    	{
        
    		AdjustDown(a, n,i);
    	}

时间复杂度：  
![在这里插入图片描述][5c727befd8aa4e3bb059f07ce843699d.png]  
同样的我们通过**求和**可以得到以下结果：  
![在这里插入图片描述][10bd1e280f12426bb6d57c11c24f0035.png]  
通过**错位相减**得到：  
![在这里插入图片描述][a52f9d91a9e34632b88bb7c99fb689e1.png]  
所以向下调整算法的时间复杂度为O（N)。

#### 步骤2：堆删除思想： ####

以升序为例，在我们建完大堆之后，将**大堆的第一个元素**和**最后一个元素交换位置**，让size- -，随后将**堆进行向下调整**（这里就是堆删除的思想）即可。在向下调整的过程中就会将第二大的元素调整到第一个元素，随后在将第一个元素和倒数第二个元素交换……以此循环即可实现排序：

void Heapsort(HPDataType* a, int n)
    {
        
    	//向上调整建堆
    	for (int i = 0; i < n; i++)
    	{
        
    		AdjustUp(a, i);
    	}
    	//向下调整建堆
    	for (int i = (n - 2) / 2; i > 0; i--)
    	{
        
    		AdjustDown(a, n,i);
    	}
    	//堆删除
    
    	int end = n - 1;
    	for (int i = end; i > 0; i--)
    	{
        
    		swap(&a[i], &a[0]);
    		end--;
    		AdjustDown(a, end, i);
    	}
    
    }

**建堆**和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

其实上面的时间复杂度可以很明显的看出**向下调整算法的O(N)更小**，因为**向上调整算法是更多的结点调整更多次**，**向下调整算法是更少的结点调整更多次**，所以向下调整算法的时间复杂度更小。

### 2.TOP-K问题 ###

**TOP-K问题**：即求数据结合中前K个最大的元素或者最小的元素，一般情况下**数据量都比较大**。  
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。  
对于Top-K问题，能想到的**最简单直接的方式就是排序**，但是：如果**数据量非常大**，**排序就不太可取了**(可能**数据都不能全部加载到内存中**)。

![在这里插入图片描述][9c3b026e4a86434cad142c80f8c7de3d.png]  
顺便来复习一下单位的换算：  
![在这里插入图片描述][154f43e7752c415789b39694a9fdce64.png]  
最佳的方式就是用**堆**来解决，**基本思路**如下：

假设我们要从N个元素取最大/最小的K个元素

1.  用数据集合中**前K个元素来建堆**  
    前k个**最大的元素**，则**建小堆**  
    前k个**最小的元素**，则**建大堆**
2.  用**剩余的N-K个元素**依次与**堆顶元素来比较**，**不满足则替换堆顶元素**

将剩余N-K个元素依次与堆顶元素**比完之后**，**堆中剩余的K个元素就是所求的前K个最小或者最大的元素**

我们以寻找最大的前k个数为例：

我们先通过文件操作进行造数据：  
忘记文件操作的朋友们可以看看这篇博客 [文件操作（上）][Link 3]

void CreateNdata()
    {
        
    	const char* file = "data.txt";
    	FILE* fq = fopen(file, "w");
    	if (fq == NULL)
    	{
        
    		perror("malloc::fail");
    		return;
    	}
    	srand(time(NULL));
    
    	int n = 10000000;
    	for (int i = 0; i < n; i++)
    	{
        
    		int ret = rand() % 10000;
    		fprintf(fq, "%d\n", ret);
    	}
    
    	fclose(fq);
    	free(fq);
    
    }

大家会发现我们造的数据非常多，没错，就是要这种效果，现实生活中**数据过多我们就不能用内存来存储，用文件来储存**。

接下来我们将这些数据的前k个进行建堆，并将**剩余的N-K个元素**依次与**堆顶元素来比较**，不满足则替换堆顶元素。**一定要记得建的是小堆！**

void PrintTopK(const char* file, int k)
    {
        
    	// 1. 建堆--用a中前k个元素建小堆
    	int* topk = (int*)malloc(sizeof(int) * k);
    	assert(topk);
    	FILE* fq = fopen(file, "r");
    	if (fq == NULL)
    	{
        
    		perror("malloc:fail");
    		return;
    	}
    
    	for (int i = 0; i < k; i++)
    	{
        
    		fscanf(fq, "%d", &topk[i]);
    	}
    	//建小堆
    	for (int i = (k - 2) / 2; i >= 0; i--)
    	{
        
    		AdjustDown(topk, k, i);
    	}
    	int val = 0;
    	//ret是fscanf的返回值，fscanf返回eof，则结束
    	int ret = fscanf(fq, "%d", &val);
    	while (ret != EOF)
    	{
        
    		if (val > topk[0])
    		{
        
    			swap(&val ,&topk[0]);
    			AdjustDown(topk, k, 0);
    		}
    		ret = fscanf(fq, "%d", &val);
    	}
    
    	for (int i = 0; i < k; ++i)
    	{
        
    		printf("%d ", topk[i]);
    	}
    	printf("\n");
    
    	fclose(fq);
    	free(fq);
    }

随后我们看看结果：  
先创建数据：

int main()
    {
        
    	CreateNdata();
    	//PrintTopK("data.txt", 10);
    }

然后在取前k个数据：

int main()
    {
        
    	//CreateNdata();
    	PrintTopK("data.txt", 10);
    }

![在这里插入图片描述][5b5b25feff064f56a23a7f1fe2a3e992.png]  
产生这个结果的原因是数据太多了，导致产生随机数9999的数据太多了。现在我们直接改改文件里的数据：  
![在这里插入图片描述][490e007119184ab38e81ddc8f631f396.png]  
在改了以后最大的几个数一定会有最后几个，现在我们来看看结果：  
![在这里插入图片描述][b57e55a06c784ea58daa1b93397afba2.png]  
这样最大的前k个数就以小堆的形式打印出来了。

## 总结 ##

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 4]  
> [c语言学习][c]  
> [算法][Link 5]  
> [智力题][Link 6]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/04d9278c5f42444393068881bc98d5f5.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/538b779c346e4870995334d17c3d8aee.gif
[1304f5049c4f4a408a4df6230bf1cde5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3d9c134399c54771b858660172aa1eeb.png
[be49312fb955419db247f7bc0fb63da4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/75debffb56144e338683bf64fb5e5566.png
[7b8762be37f9410bafa9ea33e7cd81d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/4cec0f28577c4a43be153635e13c31fd.png
[18b40ce79f1347b8b84630a6bb98756d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/9cafecfbd8d24ed0a178671023ec1eb8.png
[d0fe48ae29b94f44a331bd4bc03821a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/89eacad7a2a746d08392c8346d7e12b2.png
[f89d367936324d10b7330b3fbc619dfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f94125adb42b4d76ac66f0e7aba2084d.png
[b2140a0239354853b310ba2312b19d0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8bdbb49378ef4a06a956597b45ee044a.png
[ad740e4e1f904fb9ad8b531e1b8043e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/51b90601712b45bbae906ab288437ac9.png
[0ae7df0eef554abdaece48964d9b6ad9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/732790e1e94d40769784e9e8fd07ab2a.png
[1f3af13a506043a186a329fc4563d4fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/d5f418edc6eb4284986d794ad0abd973.png
[f8c639b0c4594855845a6ef553d69057.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/4a133e8959b44d27b1dcd379d2c4a929.png
[c8fd4c37c0da41eda10af7c0743fce6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f2b4615dcd67482e92830132893e57c3.png
[2ec4ac8cff93441cb555d5e7b941dd7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8e18ba126b12472e85df9e1df1ecd8c3.png
[5c727befd8aa4e3bb059f07ce843699d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0a5dfc53afd84d91b9a940327b8dd299.png
[10bd1e280f12426bb6d57c11c24f0035.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3b87b58fb45140b3ad90711dfa1bef75.png
[a52f9d91a9e34632b88bb7c99fb689e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f881fa974d684e0b850c67cc1c1c21fa.png
[9c3b026e4a86434cad142c80f8c7de3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2c3928c6de3f4cea9827fc1cb42c8a48.png
[154f43e7752c415789b39694a9fdce64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/93eb38e4037847cabed375848ade114f.png
[Link 3]: https://blog.csdn.net/qq_74310471/article/details/128776548?spm=1001.2014.3001.5501
[5b5b25feff064f56a23a7f1fe2a3e992.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5b871e61b53440b88f1af06a52158bdd.png
[490e007119184ab38e81ddc8f631f396.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/bfce7b013cac40e29ed6462c7bbe0a9f.png
[b57e55a06c784ea58daa1b93397afba2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/1655fd690a23472ea68923529859d0c2.png
[Link 4]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 6]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/1ff0e6391b884e29b2aadc57cc2cb094.gif