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

这篇具有很好参考价值的文章主要介绍了数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

二叉树的顺序结构

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

堆的概念及结构

在这里我们先学习一下堆,堆是一种特殊的二叉树形式
如果有一个关键码的集合K = { N1,N2 ,N3 ,…, },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足: Ni<= N(2i+1)且 Ni<= N(2i+2)( Ni>= N(2i+1)且Ni >=N(2i+2) ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
★堆中某个节点的值总是不大于或不小于其父节点的值;
★堆总是一棵完全二叉树。
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

堆的实现

1、堆向下调整算法

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

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

数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
后面在讲到堆的插入接口函数时,还会提到向上调整算法

2、堆的创建

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

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

数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
此时调换1和8的位置时,8的左子树堆结构被破坏,所以在每一次发生元素交换的时候,都需要递归调用重新构造堆的结构
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
最后构造的大堆:8,7,6,5,1,3

3、堆的插入

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用
★将堆顶元素和堆中最后一个元素进行交换
★删除最后一个元素
★将堆顶的元素向下调整,直到满足堆特性为止

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;
}

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

向上调整(AdjustUp)

代码如下:

void AdjustUp(int* a, int child)
{
	assert(a);

	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
		{
			break;
		}
	}
}

这里的向上调整函数就是指定一个元素与其父亲比较,如果孩子小于父亲,就交换
常用于小堆的插入与堆排序。

向下调整(AdjustDown)

代码如下:

void AdjustDown(int* 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;
		}
	}
}

这里的向下调整函数就是指定一个元素与其父亲比较,如果孩子小于父亲,就交换
同样常用于小堆的插入与堆排序,和向上调整的不同的就是方向。

堆的初始化(HeapInit)

代码如下:

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

堆的销毁(HeapDestroy)

代码如下:

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}

堆的插入(HeapPush)

代码如下:

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		hp->a = tmp;
		hp->capacity = newCapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

堆的插入,首先创建内存空间,然后插入元素,size++就不说了;
重点讲一下这里的向上调整,因为是小数往上调,所以这里的调用是用于小堆的建立;
如果要改成大堆,那么就要将向上调整函数的判断改为大于;
修改后代码如下:

if (a[child] >  a[parent])

堆的删除(HeapPop)

代码如下:

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	AdjustDown(hp->a, hp->size, 0);
}

堆的删除是删除堆顶的元素,但是需要注意的是并不是直接将堆顶元素直接删除
而是将堆顶元素和最后一个元素交换,再进行size–
再将换上去的最后的元素重新向下调整到相应位置
这样做的目的是为了保持堆的基本结构,否则可能堆结构可能不成立。

取堆顶的数据(HeapTop)

代码如下:

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

直接返回第一个元素即可

堆的打印(HeapPrint)

代码如下:

void HeapPrint(HP* hp)
{
	for (int i = 0; i < hp->size; ++i)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

常用的for循环对顺序表进行元素遍历逐个打印

堆的判空(HeapEmpty)

代码如下:

bool HeapEmpty(HP* hp)
{
	assert(hp);

	return hp->size == 0;
}

这里使用的是bool值,当然你也可以使用int类型

堆的数据个数(HeapSize)

代码如下:

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

堆排序的简易例子

代码如下:

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	for (int end = n - 1; end > 0; --end)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
	}
}
int main()
{
	int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

这里我们主要使用向下调整的方法来实现,因为上面对堆的删除是用于小堆
所以这里调用向下调整后,该数组为降序,排序后打印如下:

75 70 69 56 50 33 30 25 15 10

如果要进行升序排序,我们只需将向下调整函数的部分符号修改即可
修改如下:

void AdjustDown(int* 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;
		}
	}
}

排序后打印如下:

10 15 25 30 33 50 56 69 70 75

结语

有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!
制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!文章来源地址https://www.toymoban.com/news/detail-418078.html

到了这里,关于数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构入门】二叉树的遍历(前序、中序、后序、层序)

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 什么是二叉树遍历: 二叉树遍历就是按照某种特定的规则,依次堆二叉树中的结点进行相应的操作,并且 每个结点只操作一次 。访问结点

    2023年04月09日
    浏览(39)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(48)
  • C语言数据结构初阶(10)----二叉树的实现

    · CSDN的uu们,大家好。这里是C语言数据结构的第十讲。 · 目标:前路坎坷,披荆斩棘,扶摇直上。 · 博客主页: @姬如祎 · 收录专栏: 数据结构与算法     目录 1. 函数接口一览 2. 函数接口的实现 2.1 BTNode* BuyNode(BTDataType x) 的实现 2.2 BTNode* CreateTree() 的实现  2.3 void

    2023年04月08日
    浏览(43)
  • 数据结构实验报告,二叉树的基本操作(C语言)

    作者:命运之光 专栏:数据结构 实验六 二叉树的基本操作 实验环境:Visual C++或Dev C++ 实验目的: 1、掌握二叉树创建; 2、掌握二叉树的遍历及常用算法。 实验内容: 通过完全前序序列创建一棵二叉树,完成如下功能: 1)输出二叉树的前序遍历序列; 2)输出二叉树的中序遍

    2024年02月09日
    浏览(36)
  • 二叉树的基本操作-C语言实现-数据结构作业

    目录  (1)二叉树的创建; (2)二叉树的先序、中序和后序遍历输出; (3)输出二叉树的叶子节点和度为2的节点的数量; (4)输出二叉树的深度; (5)将二叉树所有节点的左右子树互换(左子树变右子树,右子树变左子树); (6)参考书上,二叉树按层次输出(一行输出一层); (7)删除二

    2024年02月04日
    浏览(46)
  • 【数据结构】二叉树的前中后序遍历(C语言)

    [二叉树] 顾名思义就是有 两个分支节点的树,不仅如此,除了叶子外的所有节点都具有两个分支节点; 由于结构像一棵倒立的树,顾名思义为二叉树 ; 如下图所示,该图即为一棵 野生的二叉树 ; 既然二叉树为树,固然有着和树一样的部分( 叶子、根、分支… ) 这些也成为

    2024年02月17日
    浏览(42)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(43)
  • 《数据结构C语言版》——树、森林与二叉树的转换(超详图解)

    哈喽!这里是一只派大鑫,不是派大星。本着基础不牢,地动山摇的学习态度,从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试 狗头.jpg)的大家能够在学习阶段找到好的方法、路线,让天下没有难学的程序(只有秃头的程

    2024年02月10日
    浏览(38)
  • 数据结构入门(C语言版)二叉树概念及结构(入门)

    1.1 树的概念 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 ☆有一个特殊的结点,称为根结点,根节点没有前驱结点 ☆除根节点外,其余结点被分成M

    2023年04月14日
    浏览(40)
  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

    概述:         二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对

    2024年02月11日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包