当前位置： 首页 > news >正文

数据结构7——二叉树的顺序结构以及堆的实现

news 2024/10/22 9:31:29

在上篇文章数据结构6——树与二叉树中，我们了解了树和二叉树的概念，接着上篇文章，在本篇文章中我们学习二叉树顺序结构的实现。

目录

1. 二叉树的顺序存储结构

2. 堆的概念及结构

1. 堆的概念

2. 堆的结构

3. 堆的实现

1. 堆节点

2. 交换节点

3. 打印

4. 堆的插入

向上调整：

插入：

5. 堆的删除

向下调整：

删除：

6. 初始化

7. 销毁

验证：

源代码：

Heap.h:

Heap.c:

test.c:

1. 二叉树的顺序存储结构

二叉树一般可以使用两种结构存储，一种是顺序结构，一种是链式结构。本篇文章我们先来研究二叉树的顺序存储，下篇文章详解二叉树的链式存储。

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

如图： 完全二叉树顺序存储：

非完全二叉树顺序存储：

2. 堆的概念及结构

1. 堆的概念

简单来说，堆除了是一棵完全二叉树之外，还要满足堆序性。

堆中每个节点的值都大于等于其子节点的值，根节点是堆中最大的元素，这样的堆称为最大堆或大根堆；

相反的，堆中每个节点的值都小于等于其子节点的值，根节点是堆中最小的元素，这样的堆称为最小堆或小根堆；

2. 堆的结构

3. 堆的实现

（本篇文章只实现最小堆，最大堆与最小堆是相同的道理）

1. 堆节点

typedef int HPDataType;
//堆的物理结构与顺序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2. 交换节点

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

3. 打印

//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

4. 堆的插入

可是现在堆属性并不满足，因为30在5的上面，这是一个最小堆，我们需要将小的数字在上面。

为了恢复堆属性，我们需要交换30和5：

可是现在仍旧没有满足最小堆的堆属性，所以还需要交换10和5：

此时才得到了最小堆。

因此在插入数据后每次都要进行向上调整，于是向上调整的实现为：

向上调整：

//向上调整
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 = (parent - 1) / 2;}else{break;}}
}

插入：

//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL)//检查是否扩容成功{perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUP(php->a, php->size - 1);//传数组的最后一个数据
}

5. 堆的删除

由于堆顶是最大或最小元素，为了满足堆属性，所以堆中每次只能删除堆顶元素，一般的做法是先将堆顶元素与数组末尾元素先交换，再删除末尾元素。

可是现在40在了堆顶，反而成了最大的元素，并不满足最小堆，这时就需要向下调整：

每次删除都要调整，所以向下调整的具体实现为：

向下调整：

//向下调整
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;}}
}

删除：

//删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}

6. 初始化

//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

7. 销毁

//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

验证：

int main()
{int a[] = { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestroy(&hp);return 0;
}

源代码：

Heap.h:

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;
//堆的物理结构与顺序表相似
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交换
void Swap(HPDataType* p1, HPDataType* p2);//打印
void HeapPrint(HP* php);//初始化
void HeapInit(HP* php);//向上调整
void AdjustUP(HPDataType* a, int child);
//插入
void HeapPush(HP* php, HPDataType x);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//删除
void HeapPop(HP* php);//销毁
void HeapDestroy(HP* php);

Heap.c:

#include "Heap.h"//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}//向上调整
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 = (parent - 1) / 2;}else{break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//判断是否需要扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL)//检查是否扩容成功{perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUP(php->a, php->size - 1);//传数组的最后一个数据
}//向下调整
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;}}
}//删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

test.c:

int main()
{int a[] = { 9,3,7,10,24,14,28,72,21,5 };HP hp;HeapInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);HeapDestroy(&hp);return 0;
}

http://www.mrgr.cn/news/54968.html

相关文章：

  • ant design vue TimePicker时间选择器不点击确认也可以设置值
  • Ubuntu下解决python程序首次连接mysql拒绝访问之总结
  • MongoDB的基本操作
  • 程序员如何精进
  • React综合指南(二)
  • 二叉搜索树与AVL树(java数据结构)
  • jupyter notebook中执行过程中更新模块代码，再执行没有更新执行
  • 机器学习与神经网络：诺贝尔物理学奖的新纪元
  • Vue中使用路由
  • 数据结构：二叉树、堆
  • python+Mosh网课笔记04
  • 计算机毕业设计 基于java个性化智能学习系统的设计与实现 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试
  • 关于SSD1306的OLED的显示的研究
  • 一图秒懂色彩空间和色彩模型
  • 云计算-----单机LNMP结构WordPress网站
  • 从DexMV、VideoDex、MimicPlay到SeeDo：从人类视频中学习：机器人的主流训练方法之一
  • 网盘直链下载神器NDM
  • Springboot指定扫描路径
  • NTA-IoU指标提升超42%，北京大学提出首个使用世界模型提升自动驾驶场景重建质量DriveDreamer4D
  • ESP32-C3 入门笔记04：gpio_key 按键 (ESP-IDF + VSCode)
  • 深入拆解TomcatJetty（二）
  • 深入理解Android WebView的加载流程与事件回调
  • 【Flutter】页面布局：弹性布局（Flex）
  • MySQL【知识改变命运】10
  • 【实习分享】三无选手实习投递经验简贴
  • 数据结构单向链表的插入和删除(一)