二叉树（二）

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【数据结构的学习】
📝📝本篇内容：使用数组实现二叉树堆的存储
⬆⬆⬆⬆上一篇：二叉树（一）
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

使用数组来存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。
大堆：树中所有的父亲都大于等于孩子
小堆：树中的所有父亲都小于等于孩子
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
任何一个数组，可以看做完全二叉树，但不一定是堆

1.堆的初始化

void HeapInit(Heap* hp)// 堆的初始化
{assert(hp);hp->arr = NULL;hp->capacity = 0;hp->size = 0;
}

2. 堆的销毁

void HeapDestory(Heap* hp)// 堆的销毁
{assert(hp);free(hp->arr);//先得把开辟的动态空间释放掉，不然会造成内存泄露hp->capacity = hp->size = 0;//重新设置为0
}

3.堆的插入

void HeapPush(Heap* hp, Type x)//堆的插入
{assert(hp);if (hp->size == hp->capacity)//如果大小相同则需要扩容{int new = hp->arr == NULL ? 4 : hp->capacity * 2;//如果是NULL就开辟4个空间，否则就翻倍Type* tmp =(Type*)realloc(hp->arr, sizeof(Type)*new);//当第一个参数是NULL时，realloc的作用相等于mallocif (tmp == NULL)//判断realloc是否开辟成功{perror("realloc fail");exit(-1);}hp->capacity = new;hp->arr = tmp;}hp->arr[hp->size] = x;hp->size++;AdjustUp(hp->arr, hp->size - 1);//向上调整}

4.堆的删除

void HeapPop(Heap* hp)// 堆的删除
{hp->arr[0] = hp->arr[hp->size - 1];//把最后一个结点(指的是数组里最后一个元素)赋给根节点，就能删除大根堆hp->size--;AdjustDown(hp->arr,hp->size,0);//向下调整（但必须要做一些调整，不然堆就会出现问题）
}

5.堆的打印

void HeapPrint(Heap* hp)//堆的打印
{   for (int i = 0; i < hp->size; i++){printf("%d ",hp->arr[i]);}printf("\n");
}

6.取堆顶的数据

Type HeapTop(Heap* hp)//取堆顶的数据
{assert(hp);assert(hp->size>0);return hp->arr[0];
}

7.堆的数据个数

int HeapSize(Heap* hp)// 堆的数据个数
{assert(hp);return hp->size;}

8.堆的判空

bool HeapEmpty(Heap* hp)//堆的判空
{assert(hp);return hp->size ==0;
}

9.堆的构建

void HeapCreate(Heap* hp, Type* a, int n)//堆的构建
{HeapInit(hp);hp->arr = malloc(sizeof(Type) * n);if (hp->arr == NULL){perror("malloc fail");exit(-1);}memcpy(hp->arr,a,sizeof(Type)*n);hp->size += n;hp->capacity += n;//向上调整/*for (int i = 0; i < n; i++){AdjustUp(hp->arr, i);}*///向下调整int i = (n - 1 - 1) / 2;for (; i >= 0; i--){AdjustDown(hp->arr,n,i);}
}

10.向上调整

void AdjustUp(Type* arr,int child)//向上调整
{while (child>0)//当child为0的时候。说明已经没有父节点了，到了根节点{int parent = (child - 1) / 2;//算出父节点if (arr[parent] > arr[child])//判断是否父节点小于孩子节点{swap(&arr[parent],&arr[child]);//交换child = parent;//把父节点的下标赋给孩子节点，继续判断}else{break;}}
}

11.向下调整

AdjustDown(Type* arr, int size, int parent)//向下调整
{
int child = parent * 2 + 1;//先求出孩子结点的下标，并假设左子树的值比右子树的大while (child<size){//要小心右子树可能没有，所以需要判断if (child+1<size&&arr[child] > arr[child + 1])//如果不是，调换，右子树正好是左子树的下标+1{child++;}if (arr[parent]>arr[child]){swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}}

12.使用堆进行排序

void HeapSort(Type* arr, int n)//使用堆进行排序
{//升序//大堆来实现//向下调整int end = n - 1;while (end > 0){swap(&arr[0], &arr[end]);//先交换AdjustDown(arr, end, 0);end--;}
}

13.交换

void swap(Type* s1,Type* s2)//交换
{Type tmp = *s1;//先保存一下s1*s1 = *s2;*s2 = tmp;
}

14.完整代码

//头文件
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef int Type;
typedef struct Heap//在现实使用中只有堆才会使用数组来存储
{Type* arr;int size;int capacity;
}Heap;
void HeapInit(Heap* hp);// 堆的初始化
void HeapDestory(Heap* hp);// 堆的销毁
void HeapPush(Heap* hp,Type x);//堆的插入
void HeapPop(Heap* hp);// 堆的删除
void HeapPrint(Heap* hp);//堆的打印
Type HeapTop(Heap* hp);//取堆顶的数据
int HeapSize(Heap* hp);// 堆的数据个数
bool HeapEmpty(Heap* hp);// 堆的判空
void HeapCreate(Heap* hp,Type* a, int n);//堆的构建
void AdjustUp(Type* arr, int child);//向上调整
AdjustDown(Type* arr, int size, int parent);//向下调整
void HeapSort(Type* arr, int n);//使用堆进行排序
void swap(Type* s1, Type* s2);//交换

//函数实现
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void HeapInit(Heap* hp)// 堆的初始化
{assert(hp);hp->arr = NULL;hp->capacity = 0;hp->size = 0;
}
void HeapDestory(Heap* hp)// 堆的销毁
{assert(hp);free(hp->arr);//先得把开辟的动态空间释放掉，不然会造成内存泄露hp->capacity = hp->size = 0;//重新设置为0
}void swap(Type* s1,Type* s2)//交换
{Type tmp = *s1;//先保存一下s1*s1 = *s2;*s2 = tmp;
}void AdjustUp(Type* arr,int child)//向上调整
{while (child>0)//当child为0的时候。说明已经没有父节点了，到了根节点{int parent = (child - 1) / 2;//算出父节点if (arr[parent] > arr[child])//判断是否父节点小于孩子节点{swap(&arr[parent],&arr[child]);//交换child = parent;//把父节点的下标赋给孩子节点，继续判断}else{break;}}
}
void HeapPush(Heap* hp, Type x)//堆的插入
{assert(hp);if (hp->size == hp->capacity)//如果大小相同则需要扩容{int new = hp->arr == NULL ? 4 : hp->capacity * 2;//如果是NULL就开辟4个空间，否则就翻倍Type* tmp =(Type*)realloc(hp->arr, sizeof(Type)*new);//当第一个参数是NULL时，realloc的作用相等于mallocif (tmp == NULL)//判断realloc是否开辟成功{perror("realloc fail");exit(-1);}hp->capacity = new;hp->arr = tmp;}hp->arr[hp->size] = x;hp->size++;AdjustUp(hp->arr, hp->size - 1);//向上调整}AdjustDown(Type* arr, int size, int parent)//向下调整
{
int child = parent * 2 + 1;//先求出孩子结点的下标，并假设左子树的值比右子树的大while (child<size){//要小心右子树可能没有，所以需要判断if (child+1<size&&arr[child] > arr[child + 1])//如果不是，调换，右子树正好是左子树的下标+1{child++;}if (arr[parent]>arr[child]){swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapPop(Heap* hp)// 堆的删除
{hp->arr[0] = hp->arr[hp->size - 1];//把最后一个结点(指的是数组里最后一个元素)赋给根节点，就能删除大根堆hp->size--;AdjustDown(hp->arr,hp->size,0);//向下调整（但必须要做一些调整，不然堆就会出现问题）
}void HeapPrint(Heap* hp)//堆的打印
{   for (int i = 0; i < hp->size; i++){printf("%d ",hp->arr[i]);}printf("\n");
}void HeapCreate(Heap* hp, Type* a, int n)//堆的构建
{HeapInit(hp);hp->arr = malloc(sizeof(Type) * n);if (hp->arr == NULL){perror("malloc fail");exit(-1);}memcpy(hp->arr,a,sizeof(Type)*n);hp->size += n;hp->capacity += n;//向上调整/*for (int i = 0; i < n; i++){AdjustUp(hp->arr, i);}*///向下调整int i = (n - 1 - 1) / 2;for (; i >= 0; i--){AdjustDown(hp->arr,n,i);}
}Type HeapTop(Heap* hp)//取堆顶的数据
{assert(hp);assert(hp->size>0);return hp->arr[0];
}int HeapSize(Heap* hp)// 堆的数据个数
{assert(hp);return hp->size;}bool HeapEmpty(Heap* hp)//堆的判空
{assert(hp);return hp->size ==0;
}void HeapSort(Type* arr, int n)//使用堆进行排序
{//升序//大堆来实现//向下调整int end = n - 1;while (end > 0){swap(&arr[0], &arr[end]);//先交换AdjustDown(arr, end, 0);end--;}
}

🌸🌸二叉树（二）的知识大概就讲到这里啦，博主后续会继续更新更多数据结构的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪