4.堆_树（汇总版）

目录

1.树概念及结构

1.1树的概念

1.2 树的相关定义

1.3 树的表示

2.二叉树概念及结构

2.1概念

2.2现实中的二叉树

2.3 特殊的二叉树

2.4 二叉树的性质

2.5 二叉树的存储结构

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

3.1 二叉树的顺序结构--堆

3.2 堆的实现

3.2.1打印

3.2.2 堆向下调整算法

3.2.3 堆的创建

3.2.4 堆的插入

！！！3.2.5 堆的删除

3.2.6 堆的代码实现

1.树概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

  • 有一个特殊的结点，称为根结点，根节点没有前驱结点
  • 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
  • 因此，树是递归定义的。

 

【注意】：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2 树的相关定义

  • 节点的度：子树的个数
  • 叶节点或终端节点：度为0的节点称为叶节点
  • 分支节点：度不为0的节点
  • 兄弟节点：具有相同父节点的节点
  • 树的度：树最大的节点的度
  • 节点的层次：根为第1层，根的子节点为第2层，以此类推
  • 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
  • 堂兄弟节点：双亲在同一层的节点互为堂兄弟
  • 祖先：从根到该节点所经分支上的所有节点
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
  • 森林：由m（m>0）棵互不相交的树的集合称为森林；

根据上图，读懂这一段话就没问题啦，A的度是6，PQ是叶，DE是分支节点也是兄弟节点，树的度为6，A为第一层，树的高度为4，HI是堂兄弟结点，A是祖先，其余的都是子孙

重点理解度：结点连接的子树个数

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间 的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。

表示文件系统的目录树结构

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，可以帮其想象为一颗计划生育的树

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

3. 最大度为2

4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2现实中的二叉树

哈哈膜拜一下

2.3 特殊的二叉树

1. 满二叉树：如果每一个层的结点数都达到最大值。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，最后一层从左到右排，可以不排满。满二叉树是一种特殊的完全二叉树。 长度为h的完全二叉树，节点数量的范围[ 2^(h-1) , 2^h-1]

2.4 二叉树的性质

1. 非空二叉树的第i层上最多有 2^(i-1) 个结点.

2. 深度为h的二叉树的最大结点数是2^h-1  .

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n(0)＝n(2)＋1

以满二叉树理解, i 层(即度为0）是2^(i-1) ,  以上（i-1）层（即度为2）有节点2^(i-1)-1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= . (log以2 为底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，奇为左孩子，偶为右孩子，双亲为（i-1)/2

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序结构，数组存储（完全二叉树适用）

2.链式结构，链表实现  (后面红黑树，会涉及到三叉链表)

模拟实现：

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

3.1 二叉树的顺序结构--堆

完全二叉树更适合使用顺序结 构存储。通常把堆(一种二叉树)使用顺序结构的数组来存储

【区分】

二叉树堆：一种数据结构

虚拟进程地址空间中的堆：操作系统中管理内存的一块区域分段。

小堆头最小，大堆头最大

3.2 堆的实现

3.2.1打印

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

3.2.2 堆向下调整算法

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

模拟实现如下：

//向下调整
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 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 = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}

3.2.3 堆的创建

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

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (!hp->_a)
	{
		perror("malloc fail");
		exit(-1);
	}

	hp->_capacity = hp->_size = n;

	//将a中的元素全部转移到堆中
	memcpy(hp->_a, a, sizeof(HPDataType) * n);

	//从最后一位开始遍历调整
	for (int i = n; i >0; i--)
	{
		Adjustup(hp->_a, i);//按向上调整，此建立大堆
	}

}

建堆的时间复杂度为O(N)

3.2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->_capacity == hp->_size)//扩容
	{
		int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* new = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (!new)
		{
			perror("realloc fail");
			exit(-1);
		}

		hp->_a = new;
		hp->_capacity = newcapacity;
	}

	hp->_a[hp->_size++] = x;

	Adjustup(hp->_a, hp->_size - 1);

}

！！！3.2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据交换，然后删除数组最后一个数据，再进行向下调 整算法。

//删除堆顶
void HeapPop(Heap* hp)//先将最后一个数与堆顶交换，然后再让size--，再进行向下调整
{
	assert(hp);

	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;

	Adjustdown(hp->_a, hp->_size, 0);

}

3.2.6 堆的代码实现

.h：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
 
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
void AdjustDown(HPDataType* a, int n, int parent);
void AdjustUp(HPDataType* a, int child);
void Swap(HPDataType* p1, HPDataType* p2);
 
 
// 堆的构建
void HeapCreate(HP* hp, HPDataType* a, int n);
 
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
 
// 保持他继续是一个堆 O(logN)
void HeapPush(HP* php, HPDataType x);
 
// 删除堆顶的数据，并且保持他继续是一个堆 O(logN)
void HeapPop(HP* php);
 
HPDataType HeapTop(HP* php);
 
int HeapSize(HP* hp);
// 堆的判空
bool HeapEmpty(HP* hp);

heap .c:

#include"pile.h"

//交换的模拟实现
void swap(HPDataType* s1, HPDataType* s2)
{
	HPDataType temp = *s1;
	*s1 = *s2;
	*s2 = temp;
}
//向上调整
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 = (child - 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 HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (!hp->_a)
	{
		perror("malloc fail");
		exit(-1);
	}

	hp->_capacity = hp->_size = n;

	//将a中的元素全部转移到堆中
	memcpy(hp->_a, a, sizeof(HPDataType) * n);

	//建堆
	for (int i = 1; i < n; i++)
	{
		Adjustup(hp->_a, i);//按向上调整，此建立大堆
	}

}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;

	hp->_capacity = hp->_size = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->_capacity == hp->_size)//扩容
	{
		int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* new = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (!new)
		{
			perror("realloc fail");
			exit(-1);
		}

		hp->_a = new;
		hp->_capacity = newcapacity;
	}

	hp->_a[hp->_size++] = x;

	Adjustup(hp->_a, hp->_size - 1);

}
//删除堆顶
void HeapPop(Heap* hp)//先将最后一个数与堆顶交换，然后再让size--，再进行向下调整
{
	assert(hp);

	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;

	Adjustdown(hp->_a, hp->_size, 0);

}

HPDataType HeapTop(Heap* hp)//取堆顶
{
	assert(hp);
	assert(hp->_size > 0);

	return hp->_a[0];
}

int HeapSize(Heap* hp)//堆大小
{
	assert(hp);

	return hp->_size;
}

int HeapEmpty(Heap* hp)//判堆空
{
	assert(hp);

	return hp->_size == 0;
}

test.c

#include"pile.h"
 
 
void test()
{
	Heap hp;//创建一个堆
	int arr[] = { 1,6,2,3,4,7,5 };
	HeapCreate(&hp, arr, sizeof(arr) / sizeof(arr[0]));
	//HeapPush(&hp, 10);
	printf("%d\n", HeapSize(&hp));
	while (!HeapEmpty(&hp))
	{
		printf("%d %d \n", HeapTop(&hp), HeapSize(&hp));
		HeapPop(&hp);
	}
 
	printf("%d\n", HeapSize(&hp));
	HeapDestory(&hp);
	
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
 
	printf("\n");
}
 
int main()
{
	test();
	return 0;
}

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

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

相关文章

el-select 点击按钮滚动到选择框顶部

el-select 点击按钮滚动到选择框顶部

主要代码是在visibleChange 在这个 popper 里面找到 .el-select-dropdown__list let popper ref.$refs.popper const ref this.$refs.select let dom popper.querySelector(.el-select-dropdown__list) setTimeout(() > { dom.scrollIntoView() }, 800) <templat…
阅读更多...
Debian mariadb 10.11设定表名 大小写不敏感方法

Debian mariadb 10.11设定表名 大小写不敏感方法

目录 问题表现&#xff1a;应用中查询 表提示 表不存在 处理步骤&#xff1a; 1、查询表名大小写敏感情况&#xff1a; show global variables like %case%; 2、修改mariadb 配置设置大小写 不敏感 mysql 配置大小写不敏感 mariadb 10.11设置表名大小写不敏感 /etc/mysq…
阅读更多...
【项目部署】手把手带你从零部署项目：宝塔 + uwsgi + Django + 腾讯云 + Websocket

【项目部署】手把手带你从零部署项目：宝塔 + uwsgi + Django + 腾讯云 + Websocket

1. 前言 哈喽&#xff0c;大家好&#xff0c;我是jiaoxingk。今天带来的是有关Django项目部署的教程。 当我们完成了一个项目作品之后&#xff0c;我们肯定会迫不及待的就准备上线部署啦&#xff0c; 这篇教程将带你从服务器的配置选购&#xff0c;再通过安装宝塔的形式进行项目…
阅读更多...
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点

【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点

力扣对应题目链接&#xff1a;LCR 140. 训练计划 II - 力扣&#xff08;LeetCode&#xff09; 核心考点 &#xff1a;链表&#xff0c;前后指针的使用&#xff0c;边界条件检测。 一、《剑指Offer》内容 二、分析问题 较优解题思路&#xff1a; 题目中的链表是单链表&#xff0…
阅读更多...
数据库SQL语言实战（七）

数据库SQL语言实战（七）

前言 这次的有一点点难~~~~~我也写了好久 练习题 题目一 在学生表pub.student中统计名字&#xff08;姓名的第一位是姓氏&#xff0c;其余为名字&#xff0c;不考虑复姓&#xff09;的使用的频率&#xff0c;将统计结果放入表test5_01中 create table test5_01(First_name…
阅读更多...
Mars3d实现用一个button控制一个map.control的显示与隐藏

Mars3d实现用一个button控制一个map.control的显示与隐藏

原生js,想做一个button,控制比如compass的显示与隐藏 点一下显示 再次单击的时候就隐藏掉 写了一个function控制显示隐藏 function addCompass(){ if(compass.showtrue) { compass.showfalse; } else{ compass.showtrue; } } 功能示例(Vue版) | Mars3D三维可视化平台 | 火星…
阅读更多...
corCTF2023 -- kcipher

corCTF2023 -- kcipher

前言 本次仅仅是通过 modprobe_path 拿 flag&#xff0c;但是 modprobe_path 是可以提权的&#xff08;&#xff1a;只需要把 /etc/passwd 的权限修改为 777 即可 这里存在 kmalloc-96 大小的 UAF/Double free 所以其实利用方式挺多的~~~但是这里就不深究了 题目分析 内核版…
阅读更多...
实测好评！微信自动回复消息神器！高效沟通拿捏住！

实测好评！微信自动回复消息神器！高效沟通拿捏住！

随着企业规模的扩大和客户数量的增加&#xff0c;有效管理和回复每一条消息变得越来越具有挑战性。今天&#xff0c;就给大家分享一个高效的自动回复消息神器——个微管理系统&#xff0c;让你能够轻松应对各种沟通需求。 1、自动通过好友&#xff0c;提高沟通效率 每当有新的…
阅读更多...
Shell脚本编写-定时清空文件内容，定时记录文件内容大小

Shell脚本编写-定时清空文件内容，定时记录文件内容大小

find命令 – 根据路径和条件搜索指定文件 – Linux命令大全(手册)find命令的功能是根据给定的路径和条件查找相关文件或目录&#xff0c;其参数灵活方便&#xff0c;且支持正则表达式&#xff0c;结合管道符后能够实现更加复杂的功能&#xff0c;是Linux系统运维人员必须掌握的…
阅读更多...
基于现有语言大模型，定制“人人AI气象”公众号天气助手

基于现有语言大模型，定制“人人AI气象”公众号天气助手

最近&#xff0c;月之暗面的Kimi大模型非常受欢迎&#xff0c;尝试用了moonshot(128K)基座模型&#xff0c;通过调用各种公开渠道的API&#xff0c;简易实现了一个天气助手&#xff0c;可以回答天气相关的基础概念、原理、应用等方面的问题&#xff0c;同时也可调用多个插件获取…
阅读更多...
ComfyUI搭建和注意事项for WIN[笔记]

ComfyUI搭建和注意事项for WIN[笔记]

下载ComfyUI(GitHub - comfyanonymous/ComfyUI: The most powerful and modular stable diffusion GUI, api and backend with a graph/nodes interface.) 从源码上搭建比较麻烦&#xff0c;一般不推荐&#xff0c;所以跑到release里面找一个下载。我的显卡是GeFore GTX 1050 …
阅读更多...
【ITK统计】第一期 分类器

【ITK统计】第一期 分类器

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ：870202403 公众号：VTK忠粉 前言 本文分享ITK中的分类器及其使用情况，希望对各位小伙伴有所帮助！ 感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！ 你的点赞就是我的动力(＾Ｕ＾)ノ~ＹＯ 在统计分…
阅读更多...
私域流量引流方式有哪些？

私域流量引流方式有哪些？

私域流量引流的方法无非是营销渠道投放、各平台KOL投放、自有自媒体平台账号内容引流、线下引流、老客户转介绍裂变等几个方面&#xff0c;下面对各种不同方法进行简单介绍。 1、营销渠道投放&#xff1a;选择广点通、粉丝通、某些app的信息流和dou等大平台自带的推广渠道工具…
阅读更多...
JavaScript中的事件模型

JavaScript中的事件模型

JavaScript中的事件模型分为&#xff1a;事件和事件流、原始事件、标准事件和IE事件。 事件与事件流 JavaScript中的事件&#xff0c;可以理解为HTML文档或者浏览器中发生的一种交互操作&#xff0c;让网页有互动的功能。常见的事件就是加载事件、鼠标事件和自定义事件。 因…
阅读更多...
JavaScript中Math函数与舍入

JavaScript中Math函数与舍入

立方根 console.log(Math.sqrt(25)); //数学方式25平方根 console.log(25 ** (1 / 2)); //25的0.5次方 console.log(8 ** (1 / 3)); //8的1/3次方计算最大最小值 console.log(Math.max(1, 5, 88, 22, 132)); //返回最大值 console.log(Math.max(1, 5, 88, 22, 132)); //…
阅读更多...
STM32CubeMX学习笔记29---FreeRTOS任务通知

STM32CubeMX学习笔记29---FreeRTOS任务通知

一、简介 1 、基本概念 FreeRTOS 从 V8.2.0 版本开始提供任务通知这个功能&#xff0c;每个任务都有 一个 32 位 的通知值&#xff0c;在大多数情况下&#xff0c;任务通知可以 替代二值信号量、计数信号量、事件组&#xff0c;也可以替代长度为 1 的队列&#xff08;可以保存…
阅读更多...
wordpress外贸建站公司歪建站新版网站上线

wordpress外贸建站公司歪建站新版网站上线

wordpress外贸建站公司 歪猫建站 歪猫WordPress外贸建站&#xff0c;专业从事WordPress多语言外贸小语种网站建设与外贸网站海个推广、Google SEO搜索引擎优化等服务。 https://www.waimaoyes.com/dongguan
阅读更多...
一键 input 苹果 OpenELM，零门槛 Llama 3 教程，40+ 优质模型/数据集/教程，建议收藏！...

一键 input 苹果 OpenELM，零门槛 Llama 3 教程，40+ 优质模型/数据集/教程，建议收藏！...

现在 AI 行业什么最火&#xff1f; 「大模型」一定仍然排在前三甲的位置。 自从 2022 年底 ChatGPT 面世以来&#xff0c;大模型在各行各业已经带来了太多的惊喜&#xff0c;应用场景愈发丰富&#xff0c;同时也带动了相关底层技术的普及与普适化。尤其是在开源模型繁荣发展之下…
阅读更多...
拼多多标准推广怎么开出自然流量呢

拼多多标准推广怎么开出自然流量呢

拼多多标准推广开出自然流量的策略如下&#xff1a; 拼多多推广可以使用3an推客。3an推客&#xff08;CPS模式&#xff09;给商家提供的营销工具&#xff0c;由商家自主设置佣金比例&#xff0c;激励推广者去帮助商家推广商品链接&#xff0c;按最终有效交易金额支付佣金&…
阅读更多...
408数据结构-树与森林 自学知识点整理

408数据结构-树与森林 自学知识点整理

前置知识&#xff1a;树的基本概念与性质 树的存储结构 树既可以采用顺序存储结构&#xff0c;又可采用链式存储结构。但无论采取哪种方式&#xff0c;都要求能够唯一地反映树中各结点之间的逻辑关系。 1. 双亲表示法 这种存储结构采用一组连续空间来存储每个结点&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站