当前位置： 首页 > article >正文

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

article 2024/11/7 14:46:24

文章目录

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

http://www.kler.cn/a/383099.html

相关文章：

  • 【实用教程】Blazor 文件管理器中引入分页功能
  • k8s图形化显示（KRM）
  • 《Linux运维总结：基于银河麒麟V10+ARM64架构CPU部署redis 6.2.14 TLS/SSL哨兵集群》
  • 第11章 LAMP架构企业实战
  • ECC校验算法的验证
  • 机器人零位、工作空间、坐标系及其变换，以UR5e机器人为例
  • Linux基础-常用操作命令详讲
  • 《Java核心技术 卷I》对象克隆
  • LeetCode 热题100之图论
  • Hive 2.x 的安装与配置
  • GPU架构概述
  • python数据分析笔记
  • 如何选择适合TikTok创作者的高性价比专线网络：全方位指南
  • 【算法篇】--重温算法题
  • Pulsargeist：恐怖类型的 XR 大空间项目创新玩法
  • SQL练习专场--01
  • 【glm4-voice-9b 本地运行并测试 gradio+notebook】
  • 探索空间计算与 VR 设备的未来：4K4DGen 高分辨率全景 4D 内容生成系统
  • ssm061基于SSM框架的个人博客网站的设计与实现+vue(论文+源码)_kaic
  • AI 搜索来势汹汹，互联网将被颠覆还是进化？
  • Openlayers高级交互（20/20）：超级数据聚合，页面不再混乱
  • 使用 Let’s Encrypt 获取免费SSL证书
  • 城镇住房保障系统：SpringBoot开发要点
  • TLU - Net：一种用于钢材表面缺陷自动检测的深度学习方法
  • c语言架构的一点构想
  • 挂钩图像分割安全状态与危险状态识别系统：更新创新流程