【数据结构初阶】二叉树（2）

二叉树顺序结构

    • 1.二叉树的顺序结构及实现
      • 1.1二叉树的顺序结构
    • 1.2 堆的概念及结构
      • 1.3 堆的实现
      • 1.3.1向上调整
      • 1.3.2向下调整
      • 1.3.3交换函数
      • 1.3.4打印
      • 1.3.5初始化
      • 1.3.6销毁
      • 1.3.7插入
      • 1.3.8删除
      • 1.3.9获得堆顶元素
      • 1.3.10判断是否为空
      • 1.3.6 堆的代码实现
    • 1.3.2堆的创建
    • 1.3.3 建堆时间复杂度
    • 1.4 堆的应用
      • 1.4.1 堆排序

1.二叉树的顺序结构及实现

1.1二叉树的顺序结构

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

在这里插入图片描述

1.2 堆的概念及结构

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

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。
    在这里插入图片描述
    练习题：
    1.下列关键字序列为堆的是：（）
    A 100,60,70,50,32,65
    B 60,70,65,50,32,100
    C 65,100,70,32,50,60
    D 70,65,100,32,50,60
    E 32,50,100,70,65,60
    F 50,100,70,65,60,32
    2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次
    数是（）。
    A 1
    B 2
    C 3
    D 4
    3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
    A(11 5 7 2 3 17)
    B(11 5 7 2 17 3)
    C(17 11 7 2 3 5)
    D(17 11 7 5 3 2)
    E(17 7 11 3 5 2)
    F(17 7 11 3 2 5)
    4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
    A[3，2，5，7，4，6，8]
    B[2，3，5，7，4，6，8]
    C[2，3，4，5，7，8，6]
    D[2，3，4，5，6，7，8]

练习题答案
1.A 2.C 3.C 4.C

1.3 堆的实现

1.3.1向上调整

在这里插入图片描述

向上调整前提：前面数据是堆

void AdjustUp(HPDateType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

1.3.2向下调整

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

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

在这里插入图片描述

void AdjustDown(HPDateType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child > 0)
	{
		if ((child + 1 > n) && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

1.3.3交换函数

void swap(HPDateType* p1, HPDateType* p2)
{
	HPDateType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

1.3.4打印

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

1.3.5初始化

void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

1.3.6销毁

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

1.3.7插入

先插入一个10到数组的尾上，再进行向上调整算法直到满足堆。
在这里插入图片描述

void HeapPush(HP* php, HPDateType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDateType* tmp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * newCapacity);
		php->capacity = newCapacity;
		php->a = tmp;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

1.3.8删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	swap(&php->a[0], &php->a[php->size]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

1.3.9获得堆顶元素

HPDateType HeadTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

1.3.10判断是否为空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

1.3.6 堆的代码实现

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int HPDateType;
typedef struct Heap
{
	HPDateType* a;
	int size;
	int capacity;
}HP;

//向上调整
void AdjustUp(HPDateType* a, int child);
//向下调整
void AdjustDown(HPDateType* a, int n, int parent);
//交换函数
void swap(HPDateType* p1, HPDateType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDateType x);
//删除
void HeapPop(HP* php);
//获得堆顶元素
HPDateType HeapTop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);

Heap.c

#include"Heap.h"

void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = 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 = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	// 扩容
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

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

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

	AdjustUp(php->a, php->size - 1);
}

void HeapPrint(HP* php)
{
	assert(php);

	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

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

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

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

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

	return php->size == 0;
}

test.c

int main()
{
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	for(int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);
	
	return 0;
}

利用堆的代码，我们可以将数组排成有序,如下：

int main()
{
	int a[] = { 2,3,5,7,4,6,8,65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a)/sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);
	int k = 5;
	while (!HeapEmpty(&hp) && k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}

	HeapDestroy(&hp);

	return 0;
}

1.3.2堆的创建

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

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

在这里插入图片描述

1.3.3 建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
在这里插入图片描述
因此：建堆的时间复杂度为O(N)。

1.4 堆的应用

1.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆
    升序：建大堆
    降序：建小堆

建堆有两种方法：
（1）使用向上调整，插入数据的思想建堆。插入数据到新的数组，就是在不断插入的过程中向上调整实现排序

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void AdjustUp(HPDataType* a, size_t child)
{
	size_t 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 HeapSort(int* a, int n)
{
	//升序，建大堆，向上
	size_t i = 0;
	for (i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}
}

int main()
{
	int a[] = { 4, 3, 10 , 2, 5, 9 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

（2）使用向下调整,从倒数第一个非叶子节点开始，即最后一个节点的父亲，即[（size-1-1）/ 2 ]【找到这个父亲的节点，向下排序，然后这个父亲节点依次减一【就找到各个小堆，依次向下排序，就成为了一个堆。

void HeapSort(int* a, int n)
{
	//升序，建堆，向上
	/*int i = 0;
	for (i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}*/
    //向下
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, i, n);
	}
}

💘不知不觉，【数据结构初阶】二叉树（2）以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/271874.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

CV 语义分割的基础和应用 | 附源码步骤

CV 语义分割的基础和应用 | 附源码步骤

引言 计算机视觉中的语义分割是一个引人入胜且迅速发展的领域。它涉及将图像分割为有意义的部分&#xff0c;并将每个部分分类为预定义的类别之一。本文将探讨在计算机视觉领域中语义分割的重要性、技术、应用、挑战以及未来前景。 每个像素都讲述一个故事&#xff1a;透过语义…
阅读更多...
关于解决微服务A调用微服务B的接口获取不到数据

关于解决微服务A调用微服务B的接口获取不到数据

前提&#xff1a; 1、首先&#xff0c;你得确保写的不同微服务之间调用接口时没有任何问题的&#xff0c;可以参考我上一篇文章&#xff1b; 2、其次&#xff0c;你需要具备怎么去调试&#xff0c;怎么去定位问题。 具备以上两点其实问题就迎刃而解了。先来看看我的问题吧 问题…
阅读更多...
Doraemon-接口自动化测试工具

Doraemon-接口自动化测试工具

这是一个自动生成接口测试测试用例的项目, 您可以通过如下方式使用他 run in python3 当你git clone 该项目后,可以通过如下命令配置你的环境 如果你习惯使用venv环境, 那么你可以进行如下操作 >>> cd doraemon >>> . venv/bin/activate >>> pip3 i…
阅读更多...
华为防火墙双机热备

华为防火墙双机热备

实验需求&#xff1a; 如图所示&#xff0c;PC1为公司内部网络设备&#xff0c;AR1为出口设备&#xff0c;在FW1和FW2上配置双机热备&#xff0c;当网络正常时PC1访问AR1路径为FW1-AR1&#xff0c;当FW1出现故障后&#xff0c;切换路径为FW2-AR1。 实现目的&#xff1a; 了解…
阅读更多...
Matlab：解非线性方程组

Matlab：解非线性方程组

1、基于问题求解非线性方程组 例&#xff1a; xoptimvar(x,2); %将x定义为一个二元素优化变量 eq1exp(-exp(-(x(1)x(2))))x(2)*(1x(1)^2); %创建第一个方程作为优化等式表达式 eq2x(1)*cos(x(2))x(2)*sin(x(1))1/2; %创建第二个方程作为优化等式表达式 probe…
阅读更多...
nextTick的使用

nextTick的使用

场景&#xff1a; 左边的树有被选中项&#xff0c;则显示右边的内容&#xff0c;且清除右边表格的被选中项 代码大概就是 选中左边的树然后执行 this.$refs.treeRef.setCurrentRow(); // 取消表格高亮行 然后报错&#xff1a; 解决&#xff1a; 在外面包一层this.$nextTi…
阅读更多...
AI可以一键生成的年终工作总结思维导图了！（内附10张年终总结模版）

AI可以一键生成的年终工作总结思维导图了！（内附10张年终总结模版）

月交替&#xff0c;斗转星移。不知不觉&#xff0c;2023年的进度条已经所剩无几了&#xff01; 又到了一年一度写年终总结的时候了&#xff0c;很多小伙伴是不是又开始发愁了&#xff0c;ProcessOn 告诉你不用担心&#xff0c; 我们今年上线了&#xff0c;AI一键生成各行各业年…
阅读更多...
挑战与应对：迅软科技探讨IT企业应对数据泄密危机的智慧之路

挑战与应对：迅软科技探讨IT企业应对数据泄密危机的智慧之路

随着信息技术的快速发展&#xff0c;软件IT行业面临着前所未有的数据安全挑战。黑客攻击、病毒传播、内部泄密等安全威胁层出不穷&#xff0c;给企业的核心资产和运营带来严重威胁。同时&#xff0c;国家对于数据安全的法律法规也日益严格&#xff0c;要求企业必须采取更加有效…
阅读更多...
亚马逊云科技创业加速器，帮助企业重塑业务并加速生成式AI之旅

亚马逊云科技创业加速器，帮助企业重塑业务并加速生成式AI之旅

经济蓬勃发展的时代&#xff0c;每一个初创企业都可能成为未来独角兽。随着创新科技快速发展、层出不穷&#xff0c;生成式AI席卷全球&#xff0c;各行各业游戏规则面临重构&#xff0c;也为初创企业带来巨大机遇。 初创公司值得信赖的云计算厂商 全球排名前1000的独角兽&#…
阅读更多...
Java多线程技术五——单例模式与多线程-备份

Java多线程技术五——单例模式与多线程-备份

1 概述 本章的知识点非常重要。在单例模式与多线程技术相结合的过程中&#xff0c;我们能发现很多以前从未考虑过的问题。这些不良的程序设计如果应用在商业项目中将会带来非常大的麻烦。本章的案例也充分说明&#xff0c;线程与某些技术相结合中&#xff0c;我们要考虑的事情会…
阅读更多...
ComfyUI如何中文汉化

ComfyUI如何中文汉化

comfyui中文地址如下&#xff1a; https://github.com/AIGODLIKE/AIGODLIKE-ComfyUI-Translationhttps://github.com/AIGODLIKE/AIGODLIKE-ComfyUI-Translation如何安装&#xff1f; 1. git安装 进入项目目录下的custom_nodes目录下&#xff0c;然后进入控制台&#xff0c;运…
阅读更多...
ppt美化的的几个小技巧

ppt美化的的几个小技巧

最简单的提升方式&#xff1a;加一层相对透明的矩形底色。 1、图标设置为透明的 方法&#xff1a;双击图片-》格式-》颜色-》设置透明色 2、使用渐变填充透明度配合作为文本底色。 1&#xff09;如透明度为90%&#xff0c;颜色会变浅&#xff0c;然后作为文本的底色。 2&…
阅读更多...
iPad绘画之旅：从小白到文创手账设计的萌系简笔画探索

iPad绘画之旅：从小白到文创手账设计的萌系简笔画探索

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 iPad的出现&#xff0c;不仅改变了我们对电子设…
阅读更多...
HarmonyOS共享包HAR

HarmonyOS共享包HAR

共享包概述 OpenHarmony提供了两种共享包&#xff0c;HAR&#xff08;Harmony Archive&#xff09;静态共享包&#xff0c;和HSP&#xff08;Harmony Shared Package&#xff09;动态共享包。 HAR与HSP都是为了实现代码和资源的共享&#xff0c;都可以包含代码、C库、资源和配…
阅读更多...
【Java基础】Java中异常分类，他们之间的区别？

【Java基础】Java中异常分类，他们之间的区别？

&#x1f341;Java中异常分哪两类 &#x1f341;Java中异常类&#x1f341;受检异常&#x1f341;非受检异常 &#x1f341;拓展知识仓&#x1f341;什么是Throwable&#x1f341;Error和Exception的区别和联系&#x1f341; 列举几个常用的RuntimeException&#x1f341;Java异…
阅读更多...
索引是如何提高查询性能的？

索引是如何提高查询性能的？

引言问&#xff1a;如何提高一条查询SQL的性能&#xff1f;答&#xff1a;最常用的方式就是加「索引」。问&#xff1a;索引为什么就能提高查询性能&#xff1f;答&#xff1a;索引就像一本书的目录&#xff0c;用目录查当然很快。问&#xff1a;为什么通过目录就能提高查询速度…
阅读更多...
restTemplate支持https忽略证书

restTemplate支持https忽略证书

由于公司的某个服务器由http转为https&#xff0c;导致原先的接口不可用&#xff0c;不过网上一堆忽略ssl都可以用就不多写了&#xff0c;写几个奇葩的问题 首先报错都是 sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.cert…
阅读更多...
前端开发之通过vue-office组件实现文件预览

前端开发之通过vue-office组件实现文件预览

前端开发之通过vue-office组件实现文件预览 前言效果图docx文件xlsx文件pdf文件 vue中简单案例1、安装组件2、vue中代码 前言 在实现文件预览的时候我们可以通过vue-office组件来实现文件的预览效果 效果图 docx文件 xlsx文件 pdf文件 vue中简单案例 1、安装组件 整体安装…
阅读更多...
Intel® SGX Instruction References（五）

Intel® SGX Instruction References（五）

文章目录 前言一、Intel SGX Instruction Syntax and Operation1.1 ENCLS Register Usage Summary1.2 ENCLU Register Usage Summary1.3 ENCLV Register Usage Summary1.4 Information and Error Codes1.5 Internal CREGs1.6 Concurrent Operation Restrictions 二、Intel SGX …
阅读更多...
腾讯云4核8G服务器三年优惠价格表

腾讯云4核8G服务器三年优惠价格表

腾讯云轻量服务器4核8G12M有三年优惠价吗&#xff1f;有&#xff0c;但是不怎么优势&#xff0c;相对于云轻量2核2G4M带宽三年价格是540元、2核4G5M带宽3年优惠价756元&#xff0c;4核8G12M轻量应用服务器三年价格是5292元&#xff0c;怎么样&#xff1f;还想买吗&#xff1f;阿…
阅读更多...
最新文章

Copyright @ 2022~2023