【数据结构与算法】第8课—数据结构之二叉树(堆)

文章目录

  • 1. 树
    • 1. 什么是树?
    • 1.2 树的相关概念
    • 1.3 树的表示法
  • 2. 二叉树
    • 2.1 特殊的二叉树
    • 2.2 二叉树的性质
    • 2.3 二叉树的存储结构
  • 3. 实现顺序结构二叉树
    • 3.1 堆的概念
    • 3.2 堆的实现
      • 3.2.1 堆的数据结构
      • 3.2.2 堆的初始化
      • 3.2.3 堆插入数据
      • 3.2.4 删除堆顶数据
      • 3.2.5 堆的判空和求有效数据个数
    • 3.3 堆排序
    • 3.4 Top K问题

1. 树

1. 什么是树?

  • 树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成一个具有层次关系的集合,一般是树根朝上,树叶朝下
  • 树有一个特殊的节点,叫做根节点,根节点没有前驱节点
  • 树的根节点下面又有很多子节点,但是这些子节点是不相交的
  • 除根节点外,每棵子树的根节点有且只有一个前驱,但是可以有0个或多个后继,因此,树是递归定义的

在这里插入图片描述


1.2 树的相关概念

  • 父节点/双亲节点:若一个节点有子节点,那么这个节点就是它子节点的父节点
  • 子节点/孩子节点:通俗点讲,就是一个节点它有父节点,那么它就是它父节点的子节点
  • 节点的度:就是该节点有几个子节点,那么它就是几度
  • 树的度:一棵树最大的节点的度
  • 叶子节点/终端节点:度为0的节点
  • 分支节点/非终端节点:除根节点外度不为0的节点
  • 兄弟节点:共同享有同一个父节点的节点
  • 节点的层次:从树的根开始,根为第1层,根的子节点为第2层,以此类推
  • 树的高度或深度:树中节点的最大层次
  • 节点的祖先:从根到该节点所经分支上的所有节点
  • 森林:由m(m>0)棵互不相交的树的集合
  • 路径:一条从书中任意节点出发,沿父节点到子节点的路径

在这里插入图片描述


1.3 树的表示法

  • 这里主要介绍常用的孩子兄弟表示法
  • 树有N个节点,有N-1条边

在这里插入图片描述


2. 二叉树

  • 二叉树:是树中比较常用的一种树形结构
  • 二叉树的子树有左右之分,且次序不能颠倒
  • 二叉树之所以叫二叉树,是因为它每个节点的度最大为2,也就是每个节点最多有2个子节点

在这里插入图片描述


2.1 特殊的二叉树

  • 满二叉树
  • 一个二叉树,如果每一层的节点数都达到最大值,则该二叉树就是满二叉树
  • 通俗点讲,就是一个二叉树的每一层的节点(除根节点外)都有它的兄弟节点,那么它就是满二叉树
  • 满二叉树满足:第N层的节点数是2^(N-1)个,树一共有2^N-1个节点

在这里插入图片描述


  • 完全二叉树
  • 完全二叉树就是有N个节点的二叉树,除最后一层外,其余层都是填满的状态,而且最后一层的节点都是从左到右依次排列,中间不允许有空隙
  • 满二叉树是一种特殊的完全二叉树

在这里插入图片描述


在这里插入图片描述


2.2 二叉树的性质

  • 若规定二叉树的根节点的层数为1,那么该树第k层共有2^(k-1)个节点
  • 若二叉树的根节点的层数为1,那么深度为k的树的最大节点数为2^k-1
  • 若二叉树的根节点的层数为1,那么具有n个节点的满二叉树的深度h=log2(n+1)(2为底,n+1为对数)

在这里插入图片描述


2.3 二叉树的存储结构

  • 对于二叉树的存储结构一共有两种,一种是顺序结构,另一种是链式结构
  • 顺序结构存储

在这里插入图片描述


  • 链式结构存储
  • 链式结构中,链表的每个节点都有3个域组成,数据域和左右指针域,左右指针分别指向左孩子节点和右孩子节点
  • 链式结构又分为二叉链和三叉链,三叉链比二叉链多了一个指向父节点的指针

在这里插入图片描述


3. 实现顺序结构二叉树

3.1 堆的概念

  • 堆是一种特殊的二叉树,也是完全二叉树,一般是把堆使用顺序结构来存储
  • 堆的底层结构是数组
  • 堆也有大堆和小堆之分,根节点最大的堆叫最大堆/大根堆,根节点最小的堆叫最小堆/小根堆

在这里插入图片描述


  • 堆的性质
  • 堆的某个节点值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树
  • 二叉树的性质
  • 对于有N个节点的完全二叉树,对于在下标0~k的数组中有:

在这里插入图片描述


3.2 堆的实现

3.2.1 堆的数据结构

typedef int HeapDataType;
//堆的数据结构
typedef struct Heap
{
	HeapDataType* arr; //动态数组
	int size;          //数组有效数据个数
	int capacity;      //数组容量大小
}Heap;

3.2.2 堆的初始化

//堆初始化
void HeapInit(Heap* pheap)
{
	assert(pheap);
	pheap->arr = NULL;
	pheap->size = pheap->capacity = 0;
}

3.2.3 堆插入数据

在这里插入图片描述


//交换值
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整算法
void AdjustUp(HeapDataType* arr, HeapDataType child)
{
	int parent = (child - 1) / 2;  //定义父节点
	while (child > 0)
	{
		//小堆
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]); //交换值
			child = parent;  //child走到父节点
			parent = (child - 1) / 2;  //parent走到更新后的child的父节点
		}
		else
			break;
	}
}

//堆插入数据
void HeapPush(Heap* pheap, HeapDataType x)
{
	assert(pheap);
	//如果数组满了/为空
	if (pheap->size == pheap->capacity)
	{
		//定义数组容量
		int newCapacity = pheap->capacity == 0 ? 4 : 2 * pheap->capacity;
		//为数组申请空间
		HeapDataType* tmp = (HeapDataType*)realloc(pheap->arr, sizeof(HeapDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		pheap->arr = tmp;  //申请的空间赋给数组
		pheap->capacity = newCapacity;  //新容量大小赋给capacity
	}
	//插入数据
	pheap->arr[pheap->size] = x;
	//向上调整
	AdjustUp(pheap->arr, pheap->size);
	pheap->size++;
}

3.2.4 删除堆顶数据

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


//交换值
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整算法
void AdjustDown(HeapDataType* arr, HeapDataType parent, int n)
{
	HeapDataType child = parent * 2 + 1;//孩子节点
	while (child < n)
	{
		//找最大的孩子节点
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//如果子节点大于父节点(大堆)
		if (arr[child] > arr[parent])
		{
			//交换父节点和子节点
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//删除堆顶数据
void HeapPop(Heap* pheap)
{
	assert(!HeapEmpty(pheap));
	//交换堆顶元素和最后一个元素
	Swap(&pheap->arr[0], &pheap->arr[pheap->size - 1]);
	pheap->size--;
	//向下调整
	AdjustDown(pheap->arr, 0, pheap->size);
}

//取堆顶数据
HeapDataType HeapTop(Heap* pheap)
{
	assert(pheap);
	return pheap->arr[0];
}

3.2.5 堆的判空和求有效数据个数

//判空
bool HeapEmpty(Heap* pheap)
{
	assert(pheap);
	return pheap->size == 0;
}

//求有效数据个数
int HeapSize(Heap* pheap)
{
	assert(pheap);
	return pheap->size;
}

3.3 堆排序

  • 先建堆

在这里插入图片描述


在这里插入图片描述

  • 之所以升序要建大堆,是因为最后还需要将堆顶元素与最后元素交换,然后向下调整,具体操作如下:

  • 排序(升序)
  • 向下调整算法

在这里插入图片描述
在这里插入图片描述


  • 堆排序时,每次首尾交换元素后,最后一个元素就是数的最大元素,因此在向下调整的过程中,child的限制条件为child<end,也就说明child移动的过程中是不会到划定范围内的最后一个元素,因为那样child已经越界了,这样也就保证了首尾每次交换的都是划定范围内的最大元素,同理child的兄弟节点child+1<end,也要保证不能越界,end每次向下调整过后要-1

在这里插入图片描述


//堆排序
void HeapSort(HeapDataType* arr, int sz)
{
	//根据给定的arr建大堆
	//child--sz-1  parent--(sz-1-1)/2
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, sz);
	}
	
	//排升序:建大堆
	//排降序:建小堆
	//堆排序
	int end = sz - 1;
	while (end)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}

}

int main()
{
	int arr[] = { 34,18,88,23,67,45 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr,sz);//堆排序
	return 0;
}
  • 向下调整算法的时间复杂度:O(logn),n为元素个数
  • 堆排序的时间复杂度:n*O(logn),n为元素个数,因为堆排序在建堆时要执行(sz-2)次向下调整算法
  • 向上调整(升序)
//向上调整算法
void AdjustUp(HeapDataType* arr, HeapDataType child)
{
	int parent = (child - 1) / 2;  //定义父节点
	while (child > 0)
	{
		//大堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]); //交换值
			child = parent;  //child走到父节点
			parent = (child - 1) / 2;  //parent走到更新后的child的父节点
		}
		else
			break;
	}
}
//堆排序
void HeapSort(HeapDataType* arr, int sz)
{
	//根据给定的arr建大堆
	//child--sz-1  parent--(sz-1-1)/2
	//for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	//{
	//	AdjustDown(arr, i, sz); //向下调整算法
	//}

	//向上调整算法
	for (int i = 0; i < sz; i++)
	{
		AdjustUp(arr, i);
	}
	
	//排升序:建大堆
	//排降序:建小堆
	//堆排序
	int end = sz - 1;
	while (end)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
	for (int j = 0; j < sz; j++)
	{
		printf("%d ", arr[j]);
	}
}
  • 总结
  • 向上调整算法建堆的时间复杂度为O(n*logn)
  • 向下调整算法建堆的时间复杂度为O(n)
  • 堆排序的时间复杂度为O(nlogn)

3.4 Top K问题

在这里插入图片描述


  • 代码实现
//造数据
void CreateNdata()
{
	int n = 100000;
	srand((unsigned int)time(NULL));
	FILE* fin = fopen("data.txt", 'w');
	if (fin == NULL)
	{
		perror("fopen fail!\n");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

//求前k个数据
void TopK()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, 'r');
	if (fout == NULL)
	{
		perror("fout");
		exit(2);
	}
	//找最大的前K个数,建小堆
	int* minHeap = (int*)malloc(k * sizeof(int));
	if (minHeap == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//读取文件中的前k个数据建堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历剩下的n-k个数据,跟堆顶数据比较,谁大谁入堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);
	free(minHeap);
	minHeap = NULL;
}

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

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

相关文章

Spring的高效开发思维(三)

时间&#xff1a;2024年 11月 02日 作者&#xff1a;小蒋聊技术 邮箱&#xff1a;wei_wei10163.com 微信&#xff1a;wei_wei10 音频&#xff1a;喜马拉雅 大家好&#xff0c;欢迎来到“小蒋聊技术” 我是小蒋&#xff01;。小蒋今天想和大家聊聊Spring Cloud微服务架构&am…

TEC半导体致冷工作原理:【图文详讲】

目录 1&#xff1a;什么是TEC 2&#xff1a;TEC工作原理 3&#xff1a;TEC结构 4&#xff1a;TEC技术参数 5&#xff1a;TEC选型 6&#xff1a;实物TEC 7&#xff1a;手机散热器 1&#xff1a;什么是TEC TEC半导体致冷器&#xff08;Thermo Electric Cooler&#xff09…

Linux开发讲课47--- 详解 Linux 中的虚拟文件系统

虚拟文件系统是一种神奇的抽象&#xff0c;它使得 “一切皆文件” 哲学在 Linux 中成为了可能。 什么是文件系统&#xff1f;根据早期的 Linux 贡献者和作家 Robert Love 所说&#xff0c;“文件系统是一个遵循特定结构的数据的分层存储。” 不过&#xff0c;这种描述也同样适用…

海的记忆篇章:海滨学院班级回忆录项目

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了海滨学院班级回忆录的开发全过程。通过分析海滨学院班级回忆录管理的不足&#xff0c;创建了一个计算机管理海滨学院班级回忆录的方案。文章介绍了海滨学院班级回…

【WebRTC】WebRTC的简单使用

目录 1.下载2.官网上的使用3.本地的使用 参考&#xff1a; 【webRTC】一、windows编译webrtc Windows下WebRTC编译 1.下载 下载时需要注意更新python的版本和网络连接&#xff0c;可以先试试ping google。比较关键的步骤是 cd webrtc-checkout set https_proxy127.0.0.1:123…

【05】如何解决tomcat命令提示符控制台乱码问题

Web项目开发过程中&#xff0c;直接在命令提示符窗口中通过输入startup.bat命令运行tomcat&#xff0c;在新弹出的tomcat命令提示符窗口中输出的中文是乱码问题的处理。 如何解决tomcat命令提示符控制台乱码问题 文章目录 如何解决tomcat命令提示符控制台乱码问题1.解决问题思路…

Golang | Leetcode Golang题解之523题连续的子数组和

题目&#xff1a; 题解&#xff1a; func checkSubarraySum(nums []int, k int) bool {m : len(nums)if m < 2 {return false}mp : map[int]int{0: -1}remainder : 0for i, num : range nums {remainder (remainder num) % kif prevIndex, has : mp[remainder]; has {if …

JeecgBoot集成工作流实战教程

Activiti是一个轻量级的工作流程和业务流程管理&#xff08;BPM&#xff09;平台&#xff0c;它主要面向业务人员、开发人员和系统管理员。这个平台的核心是一个快速且可靠的Java BPMN 2流程引擎。Activiti是开源的&#xff0c;并且基于Apache许可证进行分发。它可以运行在任何…

springcloud整合sentinel,限流策略持久化到nacos,详细配置案例

目录 1.组件下载和启动 &#xff08;1&#xff09;sentinel-dashboard下载 &#xff08;2&#xff09;nacos下载 &#xff08;3&#xff09;jmeter下载 &#xff08;4&#xff09;redis下载&#xff08;与流控关系不大&#xff0c;与项目启动有关&#xff09; 2.本微服务项…

利用Docker Compose构建微服务架构

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 利用Docker Compose构建微服务架构 引言 Docker Compose 简介 安装 Docker Compose 创建项目结构 编写 Dockerfile 前端 Dockerf…

Python毕业设计选题:基于大数据的旅游景区推荐系统_django

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 系统首页界面 用户注册界面 用户登录界面 景点信息界面 景点资讯界面 个人中心界面 …

02- 模块化编程-002 DS1302数码显示时间与日期

1、数码显示时间日期的电路 2、电路原理简介 电路组件与功能 单片机&#xff08; PIC16F887&#xff09;&#xff1a; 作为系统的主控芯片&#xff0c;处理所有输入输出&#xff0c;进行时间控制和显示信息更新。 DS1302&#xff08;实时时钟芯片&#xff09;&#xff1a; 用于…

token无感刷新+处理并发的后端方案

问题描述&#xff1a; 当用户通过登陆后进入一个web网站&#xff0c;会把token保存到localStorage。假设token过期时间30min。 那么当用户在网站快乐地玩耍了30min后&#xff0c;这时进行了一次提交表单&#xff0c;它会被重定向到登陆页面。 作为用户&#xff1a;我表单填了…

atoi函数学习

文章目录 一、atoi函数1、函数原型2、函数功能3、函数返回 二、atoi使用三、atoi函数模拟实现 一、atoi函数 1、函数原型 atoi函数参数为一个字符指针&#xff0c;返回类型是int&#xff0c;作用将字符串转换为整型。使用函数需要包含头文件stdlib.h 2、函数功能 解析c字符串…

基于vue框架的的考研信息共享平台v0eyp(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;国家政策,用户,院校政策,院校信息,考研资料,资料分类,考研论坛 开题报告内容 基于Vue框架的考研信息共享平台开题报告 一、研究背景与意义 随着考研人数的逐年增长&#xff0c;考研学生对高效、便捷、个性化的信息获取需求愈发强烈。…

UG NX二次开发(C#)-计算圆柱面与其他平面的夹角

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、首先创建一个三维模型3、 源代码4、调用代码1、前言 在QQ群中,有群友提问了如何判断圆柱面与某一平面是否垂直,我这里以案例的形式计算圆柱面主轴矢量与平面法矢的夹角,如果夹角为0,…

【Linux】IPC进程间通信:并发编程实战指南(一)

&#x1f308; 个人主页&#xff1a;Zfox_ &#x1f525; 系列专栏&#xff1a;Linux 目录 一&#xff1a;&#x1f525; 进程间通信介绍 &#x1f98b; 1.进程通信的目的&#x1f98b; 2.进程通信的方式 二&#xff1a;&#x1f525; 「匿名管道」通信 &#x1f98b; 匿名管道…

数据采集-Kepware OPCUA 服务器实现

KepserverEX OPC UA server设置 系列文章目录 数据采集-Kepware 安装证书异常处理 目录 KepserverEX OPC UA server设置系列文章目录一、OPC UA(OPC Unified Architecture)二、防火墙的配置三、配置KepserverEX的OPC UA3.1 启用远程连接3.2 启动OPCUA服务器接口 四、管理OPCU…

spring-boot(mybatisplus条件构造、接口、生成器)

条件构造器 除了新增以外&#xff0c;修改、删除、查询的SQL语句都需要指定where条件。因此BaseMapper中提供的相关方法除了以id作为where条件以外&#xff0c;还支持更加复杂的where条件。 使用&#xff1a; 第一步创建条件查询&#xff1a; //条件的构造查询 QueryWrapper…

单个相机矫正畸变

1、通过标定助手获取到内参外参&#xff0c;外参在此无效&#xff0c;只用到了内参 2、然后通过halcon算子进行矫正 参考&#xff1a;超人视觉