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

C学习（数据结构）--＞ 实现顺序结构二叉树

news 来源：原创 2024/9/20 19:45:00

目录

一、堆的概念与结构

 性质

二叉树的性质

二、堆的实现

1、结构

2、初始化与销毁

3、入堆与出堆（小堆）

1）Swap

2）入堆

1 数据的向上调整

2 入堆

3）出堆

1 数据的向下调整

 2 出堆

三、其他

1、入堆与出堆（大堆）

2、堆排序

1）排降序

 2）排升序

3、Top-K问题

四、总代码

Heap.h

Heap.cpp

main.cpp

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树。具有二叉树的特性的同时，还具有其它的特性。

一、堆的概念与结构

如果有一个集合，把它所有的元素按完全二叉树的顺序存储方式存储，在一维数组中，并且每一个父节点小于它的孩子结点，则称这个完全二叉树为小堆，而称每一个父节点大于它的孩子结点的完全二叉树为大堆。

  • 小堆

  • 大堆 

 性质

根据以上可得，堆总是一棵完全二叉树，且堆中某个结点的值总是不大于或不小于父结点的值。

二叉树的性质

对于一个完全二叉树，按照从上至下从左至右的数组顺序对所有结点从0开始编号，那么对于序号为 i 的结点（i - 1）/ 2 对应的结点是它的父结点，2*i + 1 对应的结点是它的左孩子结点，2*i + 2 对应的结点是它的父结点

二、堆的实现

1、结构

typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}Heap;

2、初始化与销毁

//堆的初始化
void HPInit(Heap* php)
{assert(php);php->arr = NULL;php->capacity = php->size = NULL;
}//堆的销毁
void HPDestroy(Heap* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = NULL;
}

3、入堆与出堆（小堆）

1）Swap

通过Swap函数交换两个数据

//两个数据的交换
void Swap(HPDataType* x, HPDataType* y)
{assert(x || y);HPDataType cpy = *x;*x = *y;*y = cpy;
}

2）入堆

1 数据的向上调整

//数据的向上调整(小堆)
void AdjustUpSmall(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] < arr[parent])//当孩子结点小于父节点时，两个数据交换{Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
2 入堆
//入堆(小堆)
void HPPushSmall(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpSmall(php->arr, php->size++);
}

3）出堆

1 数据的向下调整

//数据的向下调整(小堆)
void AdjustDownSmall(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] > arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
 2 出堆
//出堆(小堆)
void HPPopSmall(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownSmall(php->arr, 0, php->size);
}

三、其他

1、入堆与出堆（大堆）

与小堆大同小异

//数据的向上调整(大堆)
void AdjustUpBig(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆(大堆)
void HPPushBig(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpBig(php->arr, php->size++);
}//数据的向下调整(大堆)
void AdjustDownBig(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] < arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆(大堆)
void HPPopBig(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownBig(php->arr, 0, php->size);
}

2、堆排序

1）排降序

 以排降序为例，通过建小堆来实现堆排序

void HeapSortSmall(int* arr, int n)
{建小堆，向上排序法建堆//for (int i = 0; i < n; i++)//{//	//向上建堆//	AdjustUpSmall(arr, i);//}//向下排序，建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownSmall(arr, i, n);}//排降序int end = n - 1;while (end > 0)//出堆{Swap(&arr[0], &arr[end]);AdjustDownSmall(arr, 0, end);end--;}
}

 2）排升序

同理，通过建立大堆排升序

void HeapSortBig(int* arr, int n)
{//向下排序，建大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownBig(arr, i, n);}//排升序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownBig(arr, 0, end);end--;}
}

3、Top-K问题

  • 问：有一个数据量特别大的集合，如何用一个最多包含 K 个元素的集合来求得最大或最小的前 K 个元素
  • 答：用前 K 个元素建大堆或小堆，在用剩余的N-K个元素依此与堆顶元素比较大小，如过该元素比堆顶元素大于或小于，则替换掉堆顶元素。
//造数据
void CreateNDate()
{int n = 100000;srand((unsigned int)time(NULL));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail!!!");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//Top-K 问题
void TopK()
{int k = 10;const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!!!");exit(1);}int minHeap[10] = { 0 };//从文件中读前K个数据for (int i = 0; i < k; i++){fscanf(fout, "&d\n", minHeap);}//建小堆for (int i = (k - 1 - 1) / 2; i > 0; i--){AdjustDownSmall(minHeap, 0, k);}//继续取文件的数据，将读取到的数据和堆顶进行比较int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDownSmall(minHeap, 0, k);}}//排升序printf("排升序：");HeapSortBig(minHeap, 10);for (int i = 0; i < 10; i++){printf("%d ", minHeap[i]);}printf("\n");fclose(fout);
}

四、总代码

Heap.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}Heap;
//堆的初始化
void HPInit(Heap* php);
//堆的销毁
void HPDestroy(Heap* php);
//两个数据的交换
void Swap(HPDataType* x, HPDataType* y);
//数据的向上调整(小堆)
void AdjustUpSmall(HPDataType* arr, int child);
//入堆(小堆)
void HPPushSmall(Heap* php, HPDataType x);
//数据的向下调整(小堆)
void AdjustDownSmall(HPDataType* arr, int parent, int n);
//出堆(小堆)
void HPPopSmall(Heap* php);
//判空
bool HPEmpty(Heap* php);
//取堆顶数据
HPDataType HPTop(Heap* php);
//数据的向上调整(大堆)
void AdjustUpBig(HPDataType* arr, int child);
//入堆(大堆)
void HPPushBig(Heap* php, HPDataType x);
//数据的向下调整(大堆)
void AdjustDownBig(HPDataType* arr, int parent, int n);
//出堆(大堆)
void HPPopBig(Heap* php);
//堆排序
//排升序，建大堆
//排降序，建小堆
void HeapSortSmall(int* arr, int n);
void HeapSortBig(int* arr, int n);

Heap.cpp

#include"Heap.h"//堆的初始化
void HPInit(Heap* php)
{assert(php);php->arr = NULL;php->capacity = php->size = NULL;
}//堆的销毁
void HPDestroy(Heap* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = NULL;
}//两个数据的交换
void Swap(HPDataType* x, HPDataType* y)
{assert(x || y);HPDataType cpy = *x;*x = *y;*y = cpy;
}//数据的向上调整(小堆)
void AdjustUpSmall(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆(小堆)
void HPPushSmall(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpSmall(php->arr, php->size++);
}//数据的向下调整(小堆)
void AdjustDownSmall(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] > arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆(小堆)
void HPPopSmall(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownSmall(php->arr, 0, php->size);
}//判空
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}//取堆顶数据
HPDataType HPTop(Heap* php)
{assert(php && php->size);return php->arr[0];
}//数据的向上调整(大堆)
void AdjustUpBig(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;//求该子节点的父结点while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆(大堆)
void HPPushBig(Heap* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fali!!!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//因为数据还没有向上调整，所以size不能++//向上调整AdjustUpBig(php->arr, php->size++);
}//数据的向下调整(大堆)
void AdjustDownBig(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//求该父节点的左孩子while (child < n)//该左孩子在数组内{if (child + 1 < n && arr[child] < arr[child + 1])//比较左右孩子大小{child++;}//父节点和孩子结点交换if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆(大堆)
void HPPopBig(Heap* php)
{assert(php && php->size);//有效数据不能为零//头尾数据交换Swap(&php->arr[0], &php->arr[php->size - 1]);//出堆php->size--;//数据的向下调整AdjustDownBig(php->arr, 0, php->size);
}//堆排序
//排升序，建大堆
//排降序，建小堆void HeapSortSmall(int* arr, int n)
{建小堆，向上排序法建堆//for (int i = 0; i < n; i++)//{//	//向上建堆//	AdjustUpSmall(arr, i);//}//向下排序for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownSmall(arr, i, n);}//排降序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownSmall(arr, 0, end);end--;}
}
void HeapSortBig(int* arr, int n)
{//向下排序for (int i = (n - 1 - 1) / 2; i >= 0; i--)//(n - 1 - 1) / 2 求的是最底下子结点的父结点{AdjustDownBig(arr, i, n);}//排升序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownBig(arr, 0, end);end--;}
}

main.cpp

#include"Heap.h"//造数据
void CreateNDate()
{int n = 100000;srand((unsigned int)time(NULL));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail!!!");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//Top-K 问题
void TopK()
{int k = 10;const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!!!");exit(1);}int minHeap[10] = { 0 };//从文件中读前K个数据for (int i = 0; i < k; i++){fscanf(fout, "&d\n", minHeap);}//建小堆for (int i = (k - 1 - 1) / 2; i > 0; i--){AdjustDownSmall(minHeap, 0, k);}//继续取文件的数据，将读取到的数据和堆顶进行比较int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDownSmall(minHeap, 0, k);}}//排升序printf("排升序：");HeapSortBig(minHeap, 10);for (int i = 0; i < 10; i++){printf("%d ", minHeap[i]);}printf("\n");fclose(fout);
}void test01()
{Heap hpsmall;//堆的初始化HPInit(&hpsmall);//入堆(小堆)HPDataType arr[10] = { 32,11,55,223,86,123,867,3423,75,13 };for (int i = 0; i < 10; i++){HPPushSmall(&hpsmall, arr[i]);}//取堆顶数据printf("Heap: ");while (!HPEmpty(&hpsmall)){printf("%d ", HPTop(&hpsmall));//出堆(小堆)HPPopSmall(&hpsmall);}printf("\n");//堆的销毁HPDestroy(&hpsmall);//排降序printf("排降序：");HeapSortSmall(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");//排升序printf("排升序：");HeapSortBig(arr, 10);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");//CreateNDate();TopK();
}int main()
{test01();return 0;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 使用maven快速生成打包文件2
  • EmguCV学习笔记 C# 5.2 仿射变换
  • 从CSS注入到渗透未知网页
  • Nuxt学习_基础知识（二）
  • 开源模型应用落地-qwen2-7b-instruct-LoRA微调模型合并-Axolotl-单机单卡-V100（十）
  • 短剧视频推广连续多日遭受大量DDOS攻击，如何应对
  • 单片机驱动彩屏最简方案：单片机_RA8889最小开发板驱动控制TFT彩屏介绍（一）方案架构
  • 如何优雅的在页面上嵌入AI-Agent人工智能
  • [godot] 采用状态机时，如何处理攻击时移动？如“冲撞”
  • 【R语言】基于多模型的变量重要性图 (Variable Importance Plots)
  • 开学季数码好物分享！推荐适合学生党好用又实惠的平替电容笔！
  • 叉车驾驶员状态监控系统，司机身份安全识别，强化监管能力建设！
  • pyqt 用lamada关联信号 传递参数 循环
  • 富格林金业：注意避免曝光交易黑幕
  • python深度学习框架——TensorFlow
  • 【140天】尚学堂高淇Java300集视频精华笔记（86-87）
  • 2017-08-04 前端日报
  • angular组件开发
  • bearychat的java client
  • javascript从右向左截取指定位数字符的3种方法
  • js中forEach回调同异步问题
  • Python学习笔记 字符串拼接
  • React-Native - 收藏集 - 掘金
  • Redis提升并发能力 | 从0开始构建SpringCloud微服务(2)
  • socket.io+express实现聊天室的思考（三）
  • SQLServer之创建显式事务
  • 从0实现一个tiny react（三）生命周期
  • 构建二叉树进行数值数组的去重及优化
  • 漫谈开发设计中的一些“原则”及“设计哲学”
  • 扫描识别控件Dynamic Web TWAIN v12.2发布，改进SSL证书
  • 算法-图和图算法
  • 腾讯优测优分享 | 你是否体验过Android手机插入耳机后仍外放的尴尬？
  • ‌移动管家手机智能控制汽车系统
  • ()、[]、{}、(())、[[]]等各种括号的使用
  • （8）STL算法之替换
  • (Bean工厂的后处理器入门)学习Spring的第七天
  • (cos^2 X）的定积分,求积分 ∫sin^2(x) dx
  • (delphi11最新学习资料) Object Pascal 学习笔记---第14章泛型第2节（泛型类的类构造函数）
  • (回溯) LeetCode 131. 分割回文串
  • （三）c52学习之旅-点亮LED灯
  • (一)、软硬件全开源智能手表，与手机互联，标配多表盘，功能丰富(ZSWatch-Zephyr)
  • （一）十分简易快速 自己训练样本 opencv级联haar分类器 车牌识别
  • （转）PlayerPrefs在Windows下存到哪里去了？
  • （转）一些感悟
  • .java 9 找不到符号_java找不到符号
  • .net core 3.0 linux,.NET Core 3.0 的新增功能
  • .NET 中创建支持集合初始化器的类型
  • .NET/C# 中设置当发生某个特定异常时进入断点（不借助 Visual Studio 的纯代码实现）
  • .net反编译的九款神器
  • .net企业级架构实战之7——Spring.net整合Asp.net mvc
  • ::before和::after 常见的用法
  • [ C++ ] STL_vector -- 迭代器失效问题
  • [ vulhub漏洞复现篇 ] ECShop 2.x / 3.x SQL注入/远程执行代码漏洞 xianzhi-2017-02-82239600
  • [ 手记 ] 关于tomcat开机启动设置问题
  • []sim300 GPRS数据收发程序