【数据结构】C++语言实现二叉树的介绍及堆的实现(详细解读)

9efbcbc3d25747719da38c01b3fa9b4f.gif

 c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343

给大家分享一句我很喜欢我话：

知不足而奋进，望远山而前行！！！

铁铁们，成功的路上必然是孤独且艰难的，但是我们不可以放弃，远山就在前方，但我们能力仍然不足，所有我们更要奋进前行！！！

今天我们更新了二叉树内容，

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

树

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

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

有关树的一些概念：

  1. 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为6
  2. 叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I…等节点为叶节点非终端节点或分支节点:度不为0的节点;如上图:D、E、F、G…等节点为分支节点
  3. 兄弟节点:具有相同父节点的节点互称为兄弟节点;如上图:B、C是兄弟节点
  4. 树的度:一棵树中，最大的节点的度称为树的度;如上图:树的度为6
  5. 节点的层次:从根开始定义起，根为第1层，根的子节点为第2层，以此类推;
  6. 树的高度或深度:树中节点的最大层次;如上图:树的高度为4（有两种说法-从0开始还是从1开始，空树-1，空树0）
  7. 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
  8. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
  9. 森林:由m (m>0)棵互不相交的多颗树的集合称为森林;(数据结构中的学习并查集本质就是一个森林)——(日常很少碰到森林，并查集就是一个森林)

其中这些概念中第 4、6、7条较为重要，其余了解一下即可。

树的要求：

  • 子树是不相交的
  • 除了根结点之外，每个结点有且仅有一个父结点
  • 一个N个结点的树有N-1条边

树的表示

相对于线性表，树的结构就复杂很多了。最常用的表示方法——孩子兄弟表示法。

二叉树

与普通的树最大的不同是它最多只有两个子树。

特殊的二叉树

  1. 满二叉树：每一层都是满的。

    假设一棵满二叉树的高度是 h,那么它的总结点个数是：20+21+22+…2(h-1) =N。

    推导公式:2^h-1 = N;h = log2N+1以2位底N的对数+1。

  2. 完全二叉树

完全二叉树是个效率很高的数据结构，完全二叉树是由满二叉树引出来的。

假设树的高度是h,前h-1层是满的，最后一层不满，但是最后一层从左往右都是连续的。

最后一层最少有一个结点。

结点个数为:2^h-1-X= N,高度近似为:h = log2N+1+X以二为底N的对数+1

图有点难看不要介意

这些就是关于树的一些基本概念，下面我们来介绍一下关于树的实现。

堆的实现：

这里我们将会分为初始化、销毁、建堆、堆的删除、取出堆顶元素、判断是否为空、向上调整和向下调整这几步来完成。

头文件及堆结构的定义：

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#include<cmath>
#include<utility>



typedef int HPDataType;

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

初始化：

//初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size= 0;

}

销毁：

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

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

向上调整：

//向上调整(小根堆)
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])//小于就换就相当于建小堆
		//if (a[child] > a[parent])//大于就换就会变成大堆
		{
			std::swap(a[child], a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

建堆：

void HPPush(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 failed!!!");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

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

	//向上调整
	AdjustUp(php->a, php->size - 1);
}

向下调整：

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
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			std::swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
	
}

删除堆顶的数据：

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


	return php->a[0];
}

判空：

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

	return php->size == 0;
}

总代码：

TEST.c:

#include"Heap.h"


void TestHeap1()
{
	int a[] = { 4,2,8,1,5,6,7,9 };
	HP hp;
	HPInit(&hp);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}


	HPDestroy(&hp);
}

void HeapSort(int* a, int n)
{
	//首先建堆
	//升序：建大堆
	//降序：建小堆
	for (int i=0;i<n;i++)
	{
		AdjustUp(a, i);
	}

	int end = n - 1;
	///这里>0即可，因为=0时只剩下最后一个，就不再需要继续进行了
	while (end>0)//思路就是：比如我们升序排序，那么我们就利用大根堆，每次都将最大的那个数放在最顶上，然后将它和最后一个交换，然后让整体的大小--，那么最后一个就不再会受影响
	{
		std::swap(a[0], a[end]);
		AdjustDown(a, end, 0);
		--end;
	}


}

void TestHeap2()
{
	int a[] = { 4,2,8,1,5,6,9,7,3,10,23,14,125 };
	HeapSort(a, sizeof(a) / sizeof(0));

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		std::cout << a[i] << " ";
	}
}

int main()
{
	TestHeap2();

	return 0;
}

Heap.c:

#include"Heap.h"


//初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size= 0;

}


//销毁
void HPDestroy(HP* php)
{
	assert(php);

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


//向上调整(小根堆)
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])//小于就换就相当于建小堆
		//if (a[child] > a[parent])//大于就换就会变成大堆
		{
			std::swap(a[child], a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}



//建堆
void HPPush(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 failed!!!");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

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

	//向上调整
	AdjustUp(php->a, php->size - 1);
}

//向下调整
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
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			std::swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
	
}

//删除堆顶的数据
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	std::swap(php->a[0], php->a[php->size - 1]);//就是将第一个与最后一个换掉，然后将他们向下调整，
	php->size--;//直接size--删去最后一个元素

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



//取出堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);


	return php->a[0];
}



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

	return php->size == 0;
}

Heap.h:

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#include<cmath>
#include<utility>



typedef int HPDataType;

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

//初始化
void HPInit(HP* php);


//销毁
void HPDestroy(HP* php);


//建堆
void HPPush(HP* php,HPDataType x);

//堆的删除
void HPPop(HP* php);

//取出堆顶数据
HPDataType HPTop(HP* php);

bool HPEmpty(HP* php);

void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);

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

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

相关文章

【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 删除并获得点数（难度⭐⭐）（76）

【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 删除并获得点数（难度⭐⭐）（76）

1. 题目解析 题目链接&#xff1a;LCR 091. 粉刷房子 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 1. 状态定义 在解决这类问题时&#xff0c;我们首先需要根据题目的具体要求来定义状态。针对房屋粉刷问题&#…
阅读更多...
malloc_consolidate

malloc_consolidate

此文章用于详细介绍malloc_consolidate。 众所周知&#xff0c;fastbin一般是不能合并&#xff0c;但在malloc_consolidate中是个例外。 1.触发机制 首先构造这样的堆块结构 一个0x40的堆块在fastbin中&#xff0c;一个0x110的堆块在unbin中 随后我们尝试分配一个0x300的堆…
阅读更多...
智能BI（后端）-- 系统异步化

智能BI（后端）-- 系统异步化

文章目录 系统问题分析什么是异步化&#xff1f;业务流程分析标准异步化的业务流程系统业务流程 线程池为什么需要线程池&#xff1f;线程池两种实现方式线程池的参数线程池的开发 项目异步化改造 系统问题分析 问题场景&#xff1a;调用的服务能力有限&#xff0c;或者接口的…
阅读更多...
strcpy函数详解

strcpy函数详解

strcpy函数详解 1.函数简介2.strcpy函数的使用2.1使用方法一2.1使用方法二 3.strcpy在使用过程中的注意事项3.1被复制字符必须以\0结尾3.2目标空间必须能够大于源字符串长度3.3目标空间必须可变 1.函数简介 strcpy函数包含在<string.h>库函数中&#xff0c;是将一个字符…
阅读更多...
共享文件夹（以及问题解决方法）

共享文件夹（以及问题解决方法）

目录 文件夹共享 第一步&#xff0c;将文件夹共享 第二步&#xff0c;设置用户权限 第三步&#xff0c;打开网络发现 第四步&#xff0c;访问 网络中没有设备问题 控制面板&#xff0c;启动 重启 还是不行&#xff1f;计算机管理&#xff0c;启动 FDResPub服务&#x…
阅读更多...
波搜索算法(WSA)-2024年SCI新算法-公式原理详解与性能测评 Matlab代码免费获取

波搜索算法(WSA)-2024年SCI新算法-公式原理详解与性能测评 Matlab代码免费获取

​ 声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原理简介 一、初始化阶段 二、全…
阅读更多...
JumpServer堡垒机应用(v3.10.8) 下

JumpServer堡垒机应用(v3.10.8) 下

目录 JumpServer堡垒机简单式部署与管理(v3.10.8) 上-CSDN博客 一. 资产管理 1.1创建资产 1.2 给资产主机创建用户 1.2.1 普通账户&#xff1a; 1.2.2 特权账户&#xff1a; 1.2.3 创建用户 二. 命令过滤 2.1 创建命令组 2.2 创建命令过滤 ​编辑 三. 创建资产授权 …
阅读更多...
大模型算法(一)：从Transformer到ViT再到LLaMA

大模型算法(一)：从Transformer到ViT再到LLaMA

单任务/单领域模型 深度学习最早的研究集中在针对单个领域或者单个任务设计相应的模型。 对于CV计算机视觉领域&#xff0c;最常用的模型是CNN卷积模型。其中针对计算机视觉中的不同具体任务例如分类任务&#xff0c;目标检测任务&#xff0c;图像分割任务&#xff0c;以CNN作…
阅读更多...
Linux的常用指令 和 基础知识穿插巩固（巩固知识必看）

Linux的常用指令 和 基础知识穿插巩固（巩固知识必看）

目录 前言 ls ls 扩展知识 ls -l ls -a ls -al cd cd 目录名 cd .. cd ~ cd - pwd 扩展知识 路径 / cp [选项] “源文件名” “目标文件名” mv [选项] “源文件名” “目标文件名” rm 作用 用法 ./"可执行程序名" mkdir rmdir touch m…
阅读更多...
Springboot+Vue项目-基于Java+MySQL的制造装备物联及生产管理ERP系统(附源码+演示视频+LW)

Springboot+Vue项目-基于Java+MySQL的制造装备物联及生产管理ERP系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…
阅读更多...
Leetcode—3146. 两个字符串的排列差【简单】

Leetcode—3146. 两个字符串的排列差【简单】

2024每日刷题&#xff08;135&#xff09; Leetcode—3146. 两个字符串的排列差 实现代码 class Solution { public:int findPermutationDifference(string s, string t) {int maps[26];int mapt[26];for(int i 0; i < s.size(); i) {int idxs s[i] - a;int idxt t[i] …
阅读更多...
案例|200多套设备实时监测，守护江西彰湖水库安全

案例|200多套设备实时监测，守护江西彰湖水库安全

中型水库作为水利建设的重要组成部分&#xff0c;在防洪、供水、农业灌溉、改善民生和生态效益等方面都具有重要意义。国务院发布《关于切实加强水库除险加固和运行管护工作的通知》&#xff0c;重点提出要提升信息化管理能力&#xff0c;要加快建设水库雨水情测报、大坝安全监…
阅读更多...
判断上三角矩阵 分数 15

判断上三角矩阵 分数 15

题目展示&#xff1a; 代码展示&#xff1a; 点这里&#xff0c;输入题目名称即可检索更多题目答案 ​#include<stdio.h>int main() {//T-tint t 0;scanf("%d",&t);while(t--)//循环t次&#xff0c;处理t个矩阵{int n 0;scanf("%d",&n);…
阅读更多...
C语言学习【printf函数和scanf函数】

C语言学习【printf函数和scanf函数】

C语言学习【printf函数和scanf函数】 printf()函数和scanf()函数可以让用户与程序交流&#xff0c;是输入/输出函数 printf()函数 请求printf()函数打印数据的指令要与待打印数据的类型相匹配。例如&#xff0c;打印整数时使用%d&#xff0c;打印字符时使用%c。这些符号被称…
阅读更多...
字符串_字符函数和字符串函数

字符串_字符函数和字符串函数

C语言中对字符和字符串的处理很是频繁&#xff0c;但是C语言本身是没有字符串类型的&#xff0c;字符串通常放在常量字符串中或者字符数组中。 字符串常量适用于那些对它不做修改的字符串函数。 目录 1.函数介绍 1.1strlen 1.1.1strlen函数的模拟实现 1.2strcpy 1.2.1st…
阅读更多...
性能测试学习二

性能测试学习二

瓶颈的精准判断 TPS曲线 tps图 响应时间图 拐点在哪里呢？ 这是一个阶梯式增加的场景，拐点在第二个压力阶梯上就出现了，因为响应时间增加了，tps增加的却不多，在第三个阶段时，tps增加的就更少了，响应时间也在不断增加，所以性能瓶颈在加剧，越往后越明显【tps的增长，…
阅读更多...
【35分钟掌握金融风控策略29】贷中模型调额调价策略

【35分钟掌握金融风控策略29】贷中模型调额调价策略

目录 贷中客户风险管理和客户运营体系 用信审批策略 用信审批策略决策流与策略类型 贷中预警策略 对存量客户进行风险评级 基于客户的风险评级为客户匹配相应的风险缓释措施和建议 调额策略 基于定额策略的调额策略 基于客户在贷中的风险表现的调额策略 调价策略 存…
阅读更多...
鸿蒙开发接口Ability框架：【ApplicationContext】

鸿蒙开发接口Ability框架：【ApplicationContext】

ApplicationContext ApplicationContext模块提供开发者应用级别的的上下文的能力&#xff0c;包括提供注册及取消注册应用内组件生命周期的监听接口。 说明&#xff1a; 开发前请熟悉鸿蒙开发指导文档&#xff1a; gitee.com/li-shizhen-skin/harmony-os/blob/master/README.m…
阅读更多...
留学资讯 | 2024英国学生签证申请需要满足哪些条件？

留学资讯 | 2024英国学生签证申请需要满足哪些条件？

英国移民局于2020年9月10日发布了《移民规则变更声明: HC 707》&#xff0c;对学生签证制度进行了全面改革。该法案于2020年10月5日正式生效。根据此法案&#xff0c;新的学生签证——The Student and Child Student Routes学生和儿童学生路线&#xff0c;将替代原先的Tier 4学…
阅读更多...
基于java的超级玛丽游戏的设计与实现（论文 + 源码）

基于java的超级玛丽游戏的设计与实现（论文 + 源码）

Java的超级玛丽游戏.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89313347 基于java的超级玛丽游戏的设计与实现 摘要 近年来&#xff0c;Java作为一种新的编程语言&#xff0c;以其简单性、可移植性和平台无关性等优点&#xff0c;得到了广泛地应用。J2SE称…
阅读更多...
最新文章

Copyright @ 2022~2023