AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

IT公司的吉祥“树” 二叉树-（堆）C语言创建（二）

2023-08-07 64
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： IT公司的吉祥“树” 二叉树-（堆）C语言创建

三、堆（堆的概念及结构）


🍁概念


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


🍔小堆：

image.png


🍔大堆：

image.png


🍁堆的性质：


⭕堆中某个节点的值总是不大于或不小于其父节点的值。


⭕堆总是一棵完全二叉树。

1a90ec0b9d3366c3393e795d923768a2_3571dd45e79b4545aa590bd3fb321f3c.png


🍁堆的实现


💧 堆向下调整算法


        🥝现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。


int array[] = {27,15,19,18,28,34,65,49,25,37};


5f3b25b7b10561b31369ffc3159d5a30_b1e64267be54486bbf2a4246db615e65.png


⭕代码实现：


void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;   // 通过父亲节点找到孩子
  while (child < n)   //  当孩子节点超过了数组的大小那么就跳出循环
  {
  if (child < n - 1 && a[child] < a[child + 1])  //找到孩子中最大的那个
  {
    child++;
  }
  if (a[child] > a[parent])  // 最大的跟父亲比较，大于（小于）父亲了就交换位置
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
  }
  else
  {
    return;
  }
  }
}


💧堆的创建


🥝 下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。


💧 堆的插入


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


915dad489e42ce0834394b50beba6c32_78a5d624a49c467c9f5d44ccc021704a.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
  {
    return;
  }
  }
}
void HeapPush(HP* php, HPDataType x)
{
  assert(php);  //防止传入的是空指针
  if (php->capacity == php->size)   //当空间不够用了，扩展空间
  {
  int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
  HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
  if (tmp == NULL)  //判断是否扩展成功
  {
    perror("realloc fail");  // 失败返回错误信息
    return;
  }
  php->a = tmp;    //初始化扩展好的空间
  php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1);  // 向上调整数据
}


💧 堆的删除


🥝删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。


🔴将堆顶元素与堆中最后一个元素进行交换


🔴除堆中最后一个元素


🔴将堆顶元素向下调整到满足堆特性为止


⭕代码实现：


void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;   // 通过父亲节点找到孩子
  while (child < n)   //  当孩子节点超过了数组的大小那么就跳出循环
  {
  if (child < n - 1 && a[child] < a[child + 1])  //找到孩子中最大的那个
  {
    child++;
  }
  if (a[child] > a[parent])  // 最大的跟父亲比较，大于（小于）父亲了就交换位置
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
  }
  else
  {
    return;
  }
  }
}
void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  swap(&php->a[php->size-1], &php->a[0]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}


堆的全部代码


✅Heap.h 文件（头文件）


#pragma once
#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 AdjustUp(HPDataType* a, int child); 
//向下调整数据
void AdjustDown(int* a, int n, int parent);
//初始化堆
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);


✅Heap.c 文件


#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//交换堆中指定的两个数据
void swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//向上调整数据
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
  {
    return;
  }
  }
}
//向下调整数据
void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
  if (child < n - 1 && a[child] < a[child + 1])
  {
    child++;
  }
  if (a[child] > a[parent])
  {
    swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
  }
  else
  {
    return;
  }
  }
}
//初始化堆
void HeapInit(HP* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = 0;
  php->size = 0;
}
//堆的销毁
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->capacity = 0;
  php->size = 0;
}
//向堆中插入数据
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->capacity == php->size)
  {
  int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
  HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  php->a = tmp;
  php->capacity = newcapacity;
  }
  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[php->size - 1], &php->a[0]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}
//弹出堆顶的数据
HPDataType HeapTop(HP* php)
{
  assert(php);
  return php->a[0];
}
//判断是否为空堆
bool HeapEmpty(HP* php)
{
  return php->size == 0;
}
//计算堆的大小
int HeapSize(HP* php)
{
  return php->size;
}


✅Test.c文件


#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
int main()
{
  HP hp;
  HeapInit(&hp);
  int a[] = { 65,100,70,32,50,60 };
  for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
  {
  HeapPush(&hp, a[i]);
  }
  while (!HeapEmpty(&hp))
  {
  int top = HeapTop(&hp);
  printf("%d\n", top);
  HeapPop(&hp);
  }
  return 0;
}


🥰 运行结果如下产生了一个大堆

b4486ce5bf0669066d5624e14da40918_c70a1d5fe79141be98988903fe484802.png

文章标签：
C语言
算法
存储
关键词：
C语言二叉树
树C语言
二叉树C语言
二叉树堆C语言
it吉祥二叉树C语言
Yawesh_best
目录
相关文章
小徐在进步
|
9天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念，包括图的定义、无向图与有向图、简单图与多重图等，并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图，如完全图和树等。通过这些概念，读者可以更好地理解图论的基础知识。
小徐在进步
22 8
小徐在进步
|
11天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
25 6
小徐在进步
|
11天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
14 3
小徐在进步
|
11天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现，帮助读者理解和掌握二叉树的基本操作与应用。
小徐在进步
12 2
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
17 2
小徐在进步
|
8天前
|
存储 Serverless C语言
【C语言基础考研向】11 gets函数与puts函数及str系列字符串操作函数
本文介绍了C语言中的`gets`和`puts`函数，`gets`用于从标准输入读取字符串直至换行符，并自动添加字符串结束标志`\0`。`puts`则用于向标准输出打印字符串并自动换行。此外，文章还详细讲解了`str`系列字符串操作函数，包括统计字符串长度的`strlen`、复制字符串的`strcpy`、比较字符串的`strcmp`以及拼接字符串的`strcat`。通过示例代码展示了这些函数的具体应用及注意事项。
小徐在进步
31 7
小徐在进步
|
11天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符，每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容，提供了丰富的示例帮助理解。通过对本文的学习，读者可以全面掌握C语言中的位运算和文件处理技术。
小徐在进步
17 5
小徐在进步
|
11天前
|
存储 C语言
C语言程序设计核心详解 第七章 函数和预编译命令
本章介绍C语言中的函数定义与使用，以及预编译命令。主要内容包括函数的定义格式、调用方式和示例分析。C程序结构分为`main()`单框架或多子函数框架。函数不能嵌套定义但可互相调用。变量具有类型、作用范围和存储类别三种属性，其中作用范围分为局部和全局。预编译命令包括文件包含和宏定义，宏定义分为无参和带参两种形式。此外，还介绍了变量的存储类别及其特点。通过实例详细解析了函数调用过程及宏定义的应用。
小徐在进步
19 5
可能只会写BUG
|
16天前
|
Linux C语言
C语言 多进程编程(三)信号处理方式和自定义处理函数
本文详细介绍了Linux系统中进程间通信的关键机制——信号。首先解释了信号作为一种异步通知机制的特点及其主要来源，接着列举了常见的信号类型及其定义。文章进一步探讨了信号的处理流程和Linux中处理信号的方式，包括忽略信号、捕捉信号以及执行默认操作。此外，通过具体示例演示了如何创建子进程并通过信号进行控制。最后，讲解了如何通过`signal`函数自定义信号处理函数，并提供了完整的示例代码，展示了父子进程之间通过信号进行通信的过程。
可能只会写BUG
48 8
可能只会写BUG
|
16天前
|
C语言
C语言 字符串操作函数
本文档详细介绍了多个常用的字符串操作函数，包括 `strlen`、`strcpy`、`strncpy`、`strcat`、`strncat`、`strcmp`、`strncpy`、`sprintf`、`itoa`、`strchr`、`strspn`、`strcspn`、`strstr` 和 `strtok`。每个函数均提供了语法说明、参数解释、返回值描述及示例代码。此外，还给出了部分函数的自实现版本，帮助读者深入理解其工作原理。通过这些函数，可以轻松地进行字符串长度计算、复制、连接、比较等操作。
可能只会写BUG
21 2