二叉树详解（堆）（一）

亦凉 2024-03-24 10:03 44阅读 0赞

#### 树 ####

*  一.树的基本概念
 *  二.二叉树
 *   *  1.基本概念
     *  2.二叉树（堆）的实现

## 一.树的基本概念 ##

![在这里插入图片描述][f7ee149292844a058b5a1983ad1d2ffe.png]

![在这里插入图片描述][07e2ae22f3c147469baddbc7fe363284.png]

\*![加粗样式][f6933b7c346844d796eaee3b7bf35d6f.png]

![在这里插入图片描述][30c38d01d03547ae95ebbaa84442cf48.png]

> **树的节点只需要存两个指针，一个指向孩子，一个指向兄弟。这样就能够完全遍历整棵树。**

> **单纯的树在实际应用中很少，其主要应用于目录结构上。**

![在这里插入图片描述][46f68782def0405c9d277ac55e318405.png]

## 二.二叉树 ##

### 1.基本概念 ###

![在这里插入图片描述][844f6bc05af144ba807843b01ba1e4fe.png]

![在这里插入图片描述][52f54d73ae21453081382ed04c099729.png]

### 2.二叉树（堆）的实现 ###

> **插一个小知识，向上（up）建堆的时间复杂度是nlogn,向下建堆的时间复杂度是n。但在堆排序时调整堆时的时间复杂度是nlogn，所以总的时间复杂度是nlogn。**

![在这里插入图片描述][e3897a5499f14c9a869a74e5fc60e037.png]

> \**向下建堆的倒数第二层最多移动2(h-2)\*1，倒数第三层最多移动2(h-3)2，同理往后加。*

*Heap.h*

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<stdbool.h>
    
    
    typedef int HPDataType;
    typedef struct Heap
    {
        
    	HPDataType* a;
    	int size;
    	int capacity;
    }HP;
    
    void HeapInit(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 HeapDestroy(HP*php);//销毁

*Heap.c*

#include"Heap.h"
    
    
    void HeapInit(HP* php)//初始化
    {
        
    	assert(php);
    	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
    	if (php->a == NULL)
    	{
        
    		perror("malloc fail");
    		return;
    	}
    	php->capacity = 4;
    	php->size = 0;
    }
    
    void Swap(HPDataType*a, HPDataType*b)
    {
        
    	HPDataType tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    void AdjustUp(HPDataType*a, int child)//向上调整
    {
        
    	int parent = (child - 1) / 2;
    	while (a[parent] < a[child]&&child)
    	{
        
    		Swap(&a[child], &a[parent]);
    		child = parent;
    		parent = (child - 1) / 2;
    	}
    }
    
    void AdjustDown(HPDataType* a,int n, int parent)//向下走
    {
        
    	HPDataType child = parent * 2 + 1;
    	while (child < n)
    	{
        
    		if (child+1<n&&a[child] < a[child + 1])
    		{
        
    			++child;
    		}
    		if (a[child] > a[parent])
    		{
        
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
        
    			break;
    		}
    	}
    }
    
    
    void HeapPush(HP* php, HPDataType x)//插入（只能尾插）
    {
        
    	assert(php);
    	if (php->capacity == php->size)
    	{
        
    		HPDataType* tmp = php->a;
    		tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity * 2);
    		if (tmp == NULL)
    		{
        
    			perror("realloc fail");
    			return;
    		}
    		php->a = tmp;
    		php->capacity *= 2;
    	}
    	php->a[php->size] = x;
    	php->size++;
    
    	AdjustUp(php->a, php->size-1);
    }
    
    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);
    }
    
    
    
    HPDataType HeapTop(HP* php)//查询顶部元素
    {
        
    	assert(php);
    	return php->a[0];
    }
    
    bool HeapEmpty(HP* php)//判断是否为空
    {
        
    	assert(php);
    	return php->size == 0;
    }
    
    int HeapSize(HP* php)//判断元素个数
    {
        
    	assert(php);
    	return php->size;
    }
    
    void HeapDestroy(HP*php)
    {
        
    	assert(php);
    	free(php->a);
    	php->a=NULL;
    	php->size=php->capacity=0;
    }

*main.c*

#include"Heap.h"
    
    void AdjustUp(HPDataType* a, int child);//向上调整
    void Swap(HPDataType* a, HPDataType* b);
    void AdjustDown(HPDataType* a, int n, int parent);//向下走
    int main()
    {
        
    	//HP tmp;
    	//HeapInit(&tmp);
    	//HeapPush(&tmp, 4);
    	//HeapPush(&tmp, 18);
    	//HeapPush(&tmp, 42);
    	//HeapPush(&tmp, 12);
    	//HeapPush(&tmp, 2);
    	//HeapPush(&tmp, 3);
    
    	//while (!HeapEmpty(&tmp))
    	//{
        
    	//	printf("%d ", HeapTop(&tmp));
    	//	HeapPop(&tmp);
    	//}//有序打印
    
    	int a[6] = {
         5,268,4,1235,572,2416 };//模拟建堆
    	for (int i = 1; i < 6; i++)
    	{
        
    		AdjustUp(a, i);
    	}//建好大根堆
    	//排升序建大根堆，排降序建小根堆
    	//堆排序
    	int n = 5;
    	while (n)
    	{
        
    		Swap(&a[0], &a[n]);
    		n--;
    		AdjustDown(a,n+1,0);
    	}
    	for (int i = 0; i < 6; i++)
    	{
        
    		printf("%d ", a[i]);
    		//HeapPop(a);
    	}
    
    	return 0;
    }

[f7ee149292844a058b5a1983ad1d2ffe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/fd231c4b89b8400ab96fbcc9742946c8.png
[07e2ae22f3c147469baddbc7fe363284.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2c5aaeb8f5f54f66950cb5d6359687d1.png
[f6933b7c346844d796eaee3b7bf35d6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e0376434fe3047d5ba88722ceaa52357.png
[30c38d01d03547ae95ebbaa84442cf48.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/470d1385f8a64d0b8d9a171ac212725f.png
[46f68782def0405c9d277ac55e318405.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/29cb01e46adf4f1cae87fd4594772473.png
[844f6bc05af144ba807843b01ba1e4fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3cefba82d70040eba98163bd17139999.png
[52f54d73ae21453081382ed04c099729.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a22b85e40577427f89f92e872a65b7c7.png
[e3897a5499f14c9a869a74e5fc60e037.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7a20fadce85047caaff862795e665d87.png