数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用(上)

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

f361bb5928944da694a758c020693b8a.png


二叉树的顺序结构


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


堆的概念及结构


在这里我们先学习一下堆,堆是一种特殊的二叉树形式

如果有一个关键码的集合K = { N1,N2 ,N3 ,…, },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足: Ni<= N(2i+1)且 Ni<= N(2i+2)( Ni>= N(2i+1)且Ni >=N(2i+2) ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

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

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


4a76c99bda5c42ab872aca19a5ca283b.jpg


e69082429a3c4aefbee3d40208fd0607.jpg


堆的实现


1、堆向下调整算法


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


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

06873ee71a5e4ee59995c73d564d9191.jpg


42f36b3eaaf5421f9420903fa2435d81.png


7337a09893f644b6a2fa6f7d45a67bd5.png

7ee2c4decb7545d297dbb8a6a1aef787.png


后面在讲到堆的插入接口函数时,还会提到向上调整算法


2、堆的创建


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


int a[] = {1,5,3,8,7,6};

52277bcaf6274986aaf18b76d66a712c.png


f330f19539254c6590785ca2b570bc5e.jpg


8a0df10a368d41a6a08927142b8a82d1.png

262c54291f18467ba8afaa70f92199c9.png


此时调换1和8的位置时,8的左子树堆结构被破坏,所以在每一次发生元素交换的时候,都需要递归调用重新构造堆的结构


95cd096f7f964eb9a97e099e1363bb96.png


07a8369223614c4db4cc1a50e4e27ade.png


最后构造的大堆:8,7,6,5,1,3


3、堆的插入


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


225b9f9a4ffd49648cf6573ee88bca98.png


4881fb0bfd9b48b29faa4fe4441cafa1.png


a6d73e5876d0440b87b479a21eea4a69.png


★将堆顶元素和堆中最后一个元素进行交换

★删除最后一个元素

★将堆顶的元素向下调整,直到满足堆特性为止


4、堆的实现


这里堆的实现我们使用的是顺序表结构

堆的结构体及接口定义


// 大堆
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void AdjustUp(int* a, int child);//向上调整
void AdjustDown(int* a, int n, int parent);//向下调整
void Swap(HPDataType* px, HPDataType* py);//交换函数
void HeapInit(HP* hp);//堆的初始化
void HeapDestroy(HP* hp);// 堆的销毁
void HeapPush(HP* hp, HPDataType x);// 堆的插入
void HeapPop(HP* hp);// 堆的删除
HPDataType HeapTop(HP* hp);// 取堆顶的数据
void HeapPrint(HP* hp);//堆的打印
bool HeapEmpty(HP* hp);// 堆的判空
int HeapSize(HP* hp);// 堆的数据个数


堆的接口实现


交换函数(Swap)

代码如下:


void Swap(HPDataType* px, HPDataType* py)
{
  HPDataType tmp = *px;
  *px = *py;
  *py = tmp;
}


这里的交换函数不是接口函数,仅为了方便其他接口函数调用

相关文章
|
27天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
43 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
19天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
|
4天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
41 16
|
4天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
31 8
ly~
|
1月前
|
网络协议 算法 关系型数据库
C语言的应用
C 语言因其高效性和对硬件的直接访问能力,在多个领域有广泛应用。在系统软件领域,它被用于开发操作系统(如 Unix 和 Linux 的内核)和嵌入式系统(如汽车电子控制系统)。在游戏开发中,C 语言常用于构建游戏引擎的底层部分(如 Unity 和 Unreal Engine 的核心模块)及性能要求高的独立游戏。此外,C 语言也用于数据库管理系统(如 MySQL 和 PostgreSQL 的核心功能)和网络编程(如 TCP/IP 协议栈和网络服务器的核心模块)。
ly~
30 3
|
30天前
|
分布式计算 Hadoop Unix
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
39 1
|
26天前
|
编译器 C语言 Python
C语言结构
C语言结构
14 0
|
27天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
28天前
|
C语言
回溯入门题,数据所有排列方式(c语言)
回溯入门题,数据所有排列方式(c语言)
|
29天前
|
存储 分布式计算 算法
大数据-105 Spark GraphX 基本概述 与 架构基础 概念详解 核心数据结构
大数据-105 Spark GraphX 基本概述 与 架构基础 概念详解 核心数据结构
38 0