程序员社区

初阶数据结构——初识二叉树及其应用——堆——及其向下向上调整算法

🎉🎉想快速入门数据结构,推荐订阅作者的初阶数据结构专栏!此专栏预计更新:顺序表,链表,栈,队列,二叉树,排序算法等等

🎉🎉初阶数据结构我们通过c语言实现,所以此专栏也可以帮助大家巩固大家的c语言知识

🎉🎉源代码已上传至我的码云

前言

二叉树算是初阶数据结构的一个新坑吧,不仅仅是因为难度比前面的数据结构提升了一个档次,而且这也是我们学的第一种非线性结构

我们在前面学的数据结构,无论是顺序表还是链表,不管它们在物理中的存储方式如何,它们的逻辑一定是串在一起的。

但是树形结构却不一样,它是一种有层次的结构,其元素具有一对多的特性

在这里插入图片描述
所以,相对于以前几期,它是一种全新的数据结构

目录

  • 树的概念
    • 树的定义
    • 树的相关名词
  • 二叉树的概念
    • 一些特殊的二叉树
  • 二叉树的顺序存储结构——堆
  • 堆的实现
    • 插入和向上调整算法
  • 堆的删除与向下调整算法

树的概念

树的定义

要了解二叉树,首先我们要对普通的树有一定的认知

在前言提到过,树是一种非线性数据结构,数据的组织具有层次性

它的定义:始终由根结点(没有前驱结点的结点)和子树构成

在这里插入图片描述
所以我们可以知道:树是递归定义的

树的相关名词

节点的度:一个节点含有的子树的个数称为该节点的度;

叶节点或终端节点:度为0的节点称为叶节点;

非终端节点或分支节点:度不为0的节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

兄弟节点:具有相同父节点的节点互称为兄弟节点;

树的度:一棵树中,最大的节点的度称为树的度;

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次;

堂兄弟节点:双亲在同一层的节点互为堂兄弟;

节点的祖先:从根到该节点所经分支上的所有节点;

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

森林:由m(m>0)棵互不相交的树的集合

二叉树的概念

定义:二叉树就是度不会大于2的树(即分支数不会大于2的树)

一些特殊的二叉树

满二叉树:每一层的结点达到最大值

完全二叉树:前n-1层是一颗满二叉树,最后一棵树的结点由左到右连续存放

在这里插入图片描述

二叉树的顺序存储结构——堆

现在来到了本章的重点,堆

堆是一种在物理上连续存储,但在逻辑上却是一颗二叉树的数据结构

怎么把逻辑结构与物理结构联系起来呢?

这里有几个公式:

通过父亲结点找到孩子结点,设数组开始下标为0:

leftchild=parent2+1
leftchild=parent
2+1
这里的child和parent是它们对应的数组下标

通过孩子结点找到父亲结点

parent=(child-1)/2

注意:由于数组元素是连续存放的,所以为了保证数组的空间利用率,堆对应的逻辑结构应该是一棵完全二叉树,(即中间没有空白结点空间)

在这里插入图片描述

但是,不是一个普通的数组就是堆的,它需要满足一个特性

根结点的值始终比它的孩子结点的值小(大)

前者叫小堆,后者叫大堆

比如上图,就是一个典型的小堆

在这里插入图片描述

堆的实现

由于初始化和销毁等其它函数与线性表的定义一样,因为堆的逻辑结构是个数组,所以这篇文章中不再阐述

重点讲插入和删除

插入和删除我们要遵循一个原则:那就是堆的性质永远不会改变

为了遵循以上原则,我们需要引入向上和向下调整算法

这里我们以小堆为例来创建堆

插入和向上调整算法

我们以这个小堆来举例
在这里插入图片描述

首先,插入操作前面与顺序表差不多,需要检查容量

if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;//这里是防止堆为空
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (!tmp)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}

插入我们可以直接先在数组的后面插入

	hp->a[hp->size] = x;
	hp->size++;

比如我们要插入一个数据9,然后逻辑结构就变成了这样

在这里插入图片描述
这样,9比34小了,显然不满足小端的特征,所以我们需要向上调整算法,把它调整到满足堆的特征的所在位置

向上调整,只会影响这个结点的祖先结点

思路:与它的父亲结点不断比较,若不满足要求则交换,满足要求就停止算法

图示:

在这里插入图片描述

代码:

void AdjustUp(HPDataType* a, int size, 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;
		}
	}
}

完整的插入代码

void AdjustUp(HPDataType* a, int size, 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;
		}
	}
}


void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (!tmp)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size, hp->size - 1);
}

堆的删除与向下调整算法

注意:这里的删除是直接删除堆顶元素

我们最开始的思路是,能不能像顺序表的头删一样,直接挪动数据来删除呢?

显然是不行的,因为这样会把堆的结构完全打乱,大家可以脑补一下,这里就不图示了

所以我们需要这么删除

先把第一个元素与最后一个元素交换,再进行顺序表尾删,这样保证了前面堆的结构不会被打乱

在这里插入图片描述

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
}

但我们的77被换上去了,不满足堆的特性了,所以为了满足堆的特性,使用向下调整算法

思路:

先选出左右孩子中较小的孩子(先默认为左孩子,再与右孩子进行比较,若默认结果不成立,就更新孩子结点)

与向上调整算法异曲同工

在这里插入图片描述
代码实现

void AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//默认与左孩子交换
	while (child < size)
	{
		if (child + 1 < size && 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 AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && 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* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 初阶数据结构——初识二叉树及其应用——堆——及其向下向上调整算法

一个分享Java & Python知识的社区