二叉树-认识树及堆，堆的实现

一、树的概念及结构

（一）树的概念

树是一种非线性的数据结构，是n(n≥0)个结点的有限集。当n=0时，称为空树。
在任意一颗非空树中应满足：

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

f27e42db44a0598e9dc302bc85fd6dc4_u=169932365,2830737350&fm=253&fmt=auto&app=120&f=JPEG_w=700&h=400.webp
树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

  • 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
  • 树中所有结点可以有零个或多个后继

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。
** 一颗N个结点的数有N一1条边。**
** 树适合于表示具有层次结构的数据。**

（二）树的基本术语（无须记忆，了解即可）

image.png
节点的度： 一个节点含有的子树的个数称为该节点的度；如. 上图： A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、1… 等节点为叶节点
非终端节点或分支节点：度不为0的节点；如上图：D、E、 F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图： B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、1互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m(m>0)棵互不相交的树的集合称为森林；

（三）树的性质

树具有如下最基本的性质：

  1. 树中的结点数等于所有结点的度数之和加1.
  2. 度为m的树中第i层上至多有 m ( i − 1 ) m^{(i-1)} m(i−1)个结点（i≥1)。
  3. 高度为h的m叉树至多有 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh−1)/(m−1)个结点。
  4. 具有n个结点的m叉树的最小高度为 [ l o g m ( n ( m − 1 ) + 1 ) ] [log_m(n(m-1)+1)] [logm​(n(m−1)+1)]。

（四）树的表示

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

typedef int DataType；
struct Node
{
 struct Node* _firstChild1； // 第一个孩子结点
 struct Node* _pNextBrother； // 指向其下一个兄弟结点
 DataType _data； // 结点中的数据域
}；

二、二叉树概念及结构

一棵二叉树是结点的一个有限集合，该集合：

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

image.png
从上图可以看出：

1.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

特殊的二叉树

1.满二叉树：

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

2.完全二叉树：

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每个结点都与深度为K的满二叉树中编号从1至n的结点一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
image.png

3.斜树

顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究的。所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。
image.png
斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。

有人会想，这也能叫树呀，与我们的线性表结构不是一样吗。对的，其实线性表结构就可以理解为是树的一种极其特殊的表现形式。

4.二叉排序树

左子树上所有结点的关键字均小于根结点的关键字；
右子树上的所有结点的关键字均大于根结点的关键字；
左子树和右子树又各是一颗二叉排序树。

5.平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2 ( i − 1 ) 2^{(i-1)} 2(i−1)个结点.
2.若规定根节点的层数为1，则深度为h的二二叉树的最大结点数是 2 h − 1. 2^h - 1. 2h−1.
3.对任何一棵二叉树，如果度为0其叶结点个数为 n 0 n_0 n0​，度为2的分支结点个数为 n 2 n_2 n2​,则有 n 0 = n 2 + 1 n_0=n_2 + 1 n0​=n2​+1.
4.若规定根节点的层数为1，具有n个结点的满二叉树的深度， h = l o g 2 ( n + 1 ) h=log_2(n + 1) h=log2​(n+1). (ps: l o g 2 ( n + 1 ) log_2(n + 1) log2​(n+1)是log以2为底，n+1为对数).
5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有:

1.若i>0，i位置节点的双亲序号: (i-1)/2; i=0, i为根节点编号，无双亲节点.
2.若2i+1<n，左孩子序号: 2i+1， 2i+1≥n否则无左孩子.
3.若2i+2<n，右孩子序号: 2i+2，2i+2≥n否则无右孩子.

三、堆

1.完全二叉树
2.大堆：树任何一个父亲都大于或等于孩子
小堆：树任何一个父亲都小于或等于孩子
image.png
应用：

  1. 堆排序–O(N*logN)
  2. topk
  3. 优先级队列

堆的实现-顺序存储结构

顺序存储结构和链式结构。
这里我们使用顺序存储结构，即使用数组来实现。

image.png

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 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,newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a,php->size-1);
}

image.png

void AdjustDown(HPDataType* a, int size, int parent)//向下调整   小堆
{
	int child = parent * 2 + 1;
	while ( child< size)
	{
		if (child + 1 < size && a[child + 1] < a[child])//注意小堆和小的比较，大堆和大的比较
		{
			++child;
		}
									// 大堆，当a[child]>a[parent]时，交换
		if (a[child] < a[parent])  //  小堆，当a[child]<a[parent]时，交换   
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)//删除根结点元素，向下调整算法来调整
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size]);
	php->size--;
	AdjustDown(php->a,php->size,0);
}

小堆的实现-代码

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

typedef int HPDataType;
typedef struct Heap//堆的实现使用数组
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void AdjustUp(HPDataType* a, int child);//向上调整
void AdjustDown(HPDataType* a, int size, int parent);//向下调整   小堆

void HeapInit(HP* php);

void HeapDestory(HP* php);

void HeapPush(HP* php, HPDataType x);//本代码以小堆为示范

void HeapPop(HP* php);

HPDataType HeapTop(HP* php);

bool HeapEmpty(HP* php);

int HeapSize(HP* php);


#define _CRT_SECURE_NO_WARNINGS

#include "Heap.h"

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

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

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 = (child - 1) / 2;
		}
		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,newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a,php->size-1);
}

void AdjustDown(HPDataType* a, int size, int parent)//向下调整   小堆
{
	int child = parent * 2 + 1;
	while ( child< size)
	{
		if (child + 1 < size && a[child + 1] < a[child])//注意小堆和小的比较，大堆和大的比较
		{
			++child;
		}
									// 大堆，当a[child]>a[parent]时，交换
		if (a[child] < a[parent])  //  小堆，当a[child]<a[parent]时，交换   
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)//删除根结点元素，向下调整算法来调整
{
	assert(php);
	assert(!HeapEmpty(php));
	swap(&php->a[0], &php->a[php->size]);
	php->size--;
	AdjustDown(php->a,php->size,0);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

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

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}


#define _CRT_SECURE_NO_WARNINGS

#include "Heap.h"

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

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

	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n",top);
		HeapPop(&hp);
	}
//	HeapPop(&hp);

	HeapDestory(&hp);
}

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

	// 10:42继续
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}
}

int main()
{
	//test1();
	test2();
	return 0;
}

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

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

相关文章

STM32F407+DHT11采集数据

STM32F407+DHT11采集数据

1、DHT11简介 DHT11 与单片机之间能采用简单的单总线进行通信&#xff0c;仅仅需要一个 I/O 口。传感器内部湿度和温度数据 40Bit 的数据一次性传给单片机&#xff0c;数据采用校验和方式进行校验&#xff0c;有效的保证数据传输的准确性。DHT11 功耗很低&#xff0c;5V 电源电…
阅读更多...
Java-Doc

Java-Doc

Java-Doc javdoc命令是用来生成自己的API文档的 参数信息&#xff1a;author作者名version版本号since知名需要最早使用的jdk版本param参数名return返回值情况throws异常抛出情况 1.参数信息的使用&#xff1a; 未完待续... ...
阅读更多...
mysql面试题 1

mysql面试题 1

为什么要使用数据库 数据保存在内存 优点&#xff1a; 存取速度快缺点&#xff1a; 数据不能永久保存 数据保存在文件 优点&#xff1a; 数据永久保存缺点&#xff1a;1、速度比内存操作慢&#xff0c;频繁的IO操作。2、查询数据不方便 数据保存在数据库 数据永久保存使用SQL语…
阅读更多...
阿里云服务器公网带宽费用全解析（不同计费模式）

阿里云服务器公网带宽费用全解析（不同计费模式）

阿里云服务器公网带宽怎么收费&#xff1f;北京地域服务器按固定带宽计费一个月23元/M&#xff0c;按使用流量计费0.8元/GB&#xff0c;云服务器地域不同实际带宽价格也不同&#xff0c;阿里云服务器网aliyunfuwuqi.com分享不同带宽计费模式下带宽收费价格表&#xff1a; 公网…
阅读更多...
基于SSM+Vue实现的宠物销售系统

基于SSM+Vue实现的宠物销售系统

基于SSMVue实现的宠物销售系统 系统介绍 系统演示 点击查看视频演示 基于SSMVue实现的宠物销售系统&#xff0c;主要实现的功能有以下几点&#xff1a;管理员&#xff1b;首页、个人中心、宠物分类管理、商品分类管理、宠物用品管理、宠物商店管理、宠物领养管理、用户管理…
阅读更多...
【刷题】图论——最小生成树：局域网

【刷题】图论——最小生成树：局域网

要想去除边&#xff0c;并且不改变连通性&#xff0c;而且去除的值最大&#xff0c;相当于保留最小生成树。 注意这题连通块有若干个&#xff0c;所以运行Kruskal相当于形成若干个最小生成树。 如果是prim只能事先处理好各个连通块&#xff0c;然后在连通块内部单独用prim 题目…
阅读更多...
vueRouter动态路由(实现菜单权限控制)

vueRouter动态路由(实现菜单权限控制)

一、权限控制管理&#xff1a; 对于企业级的项目, 我们可能需要对项目做权限控制管理, 实现不同角色的用户登录项目根据所拥有的权限访问不同的页面内容&#xff0c;此时就需要使用到动态路由来对权限页面做限制。 【使用vue-router实现动态路由&#xff0c;达到实现菜单权限…
阅读更多...
阿里云2核2G服务器这么便宜，能用来做什么？

阿里云2核2G服务器这么便宜，能用来做什么？

阿里云2核2G服务器这么便宜&#xff0c;能用来做什么&#xff1f;阿里云2核2G云服务器可以用来搭建网站、爬虫、邮件服务器、接口服务器、个人博客、企业官网、数据库应用、大数据计算、AI人工智能、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云2核2G服务…
阅读更多...
四、SpringBoot3 整合 Druid 数据源

四、SpringBoot3 整合 Druid 数据源

本章概要 创建程序引入依赖启动类配置文件编写编写 Controller启动测试问题解决 4.1 创建程序 4.2 引入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://ww…
阅读更多...
解锁电气数据新价值：SolidWorks Electrical助力企业转型

解锁电气数据新价值：SolidWorks Electrical助力企业转型

在信息化、数字化的时代&#xff0c;电气数据库已成为企业不可或缺的核心资产。它以其独特的功能和优势&#xff0c;助力企业在激烈的市场竞争中脱颖而出&#xff0c;实现数字化转型的跨越式发展。 SolidWorks Electrical电气数据库具备强大的数据整合能力。它能够将企业内部各…
阅读更多...
阿里云服务器带宽价格全解析，附报价单

阿里云服务器带宽价格全解析，附报价单

阿里云服务器公网带宽怎么收费&#xff1f;北京地域服务器按固定带宽计费一个月23元/M&#xff0c;按使用流量计费0.8元/GB&#xff0c;云服务器地域不同实际带宽价格也不同&#xff0c;阿里云服务器网aliyunfuwuqi.com分享不同带宽计费模式下带宽收费价格表&#xff1a; 公网…
阅读更多...
【论文研读】Geometric Deep Learning on Molecular Representations

【论文研读】Geometric Deep Learning on Molecular Representations

Geometric Deep Learning on Molecular Representationshttps://arxiv.org/pdf/2107.12375.pdf 一、Background 随着网络时代的发展&#xff0c;生活中产生的数据量越来越多&#xff0c;但数据大体分为两类&#xff1a;欧氏数据、非欧氏数据。如图为两类常见的数据&#xff0c…
阅读更多...
SpringBoot与MyBatisPlus的依赖版本冲突问题

SpringBoot与MyBatisPlus的依赖版本冲突问题

记录使用SpringBoot和MyBatisPlus时遇到的版本冲突问题解决。 java版本&#xff1a;jdk17 废话&#xff1a;&#xff09;目前在IDEA中使用Spring官方的脚手架最低jdk版本竟然是jdk17了。 当使用SpringBoot3.0版本(3.2.4)&#xff0c;配合使用MP3.5.2版本时报错&#xff1a; Er…
阅读更多...
鸿蒙应用开发之富文本（RichText）组件

鸿蒙应用开发之富文本（RichText）组件

前面学习了评分组件，现在来学习富文本组件，这个组件用来表示复杂的文本，把文本显示得更加有特色，比如网页一样显示。这种显示会比较复杂，所以应用的场合就会少一点。不过富文本显示最多的，就是即时通讯软件了，比如显示图片与文本，以及一些特殊的字符。 比如显示如下面的…
阅读更多...
# Contrastive Learning（对比学习）--CLIP笔记（一）

# Contrastive Learning（对比学习）--CLIP笔记（一）

Contrastive Learning&#xff08;对比学习&#xff09;–CLIP笔记&#xff08;一&#xff09; 参考&#xff1a;CLIP 论文逐段精读【论文精读】_哔哩哔哩_bilibili CLIP简介 CLIP是一种多模态预训练模型&#xff0c;由OpenAI在2021年提出&#xff0c;论文标题&#xff1a;L…
阅读更多...
通俗易懂HTTP和HTTPS区别

通俗易懂HTTP和HTTPS区别

HTTP&#xff1a;超文本传输协议&#xff0c;它是使用一种明文的方式发送我们的内容&#xff0c;没有任何的加密&#xff0c;例如我们要在网页上输入账号密码&#xff0c;如果使用HTTP协议&#xff0c;账号密码就可能会被暴露&#xff0c;默认端口是80. HTTPS&#xff1a;是HT…
阅读更多...
【hive】远程remote debug hive的方法，用于hive监听器/钩子编写

【hive】远程remote debug hive的方法，用于hive监听器/钩子编写

背景 写hive监听器时候需要拿到hive对象但hive是在集群linux主机上运行的。通过jdbc提交的sql具体执行过程不会再idea中运行。所以如果需要拿到hive对象有可能存在两个思路&#xff1a; &#xff08;1&#xff09;想办法写个钩子或者监听器&#xff0c;将需要的内容写成json字…
阅读更多...
AIX7.2下安装xlc编译器

AIX7.2下安装xlc编译器

AIX镜像中对于xlc的支持仅为提供了runtime&#xff0c;而没有对应的xlc编译器。 IBM的xlc编译器需要单独购买&#xff0c;如果不想购买可以注册IBM的账号下载一个60天的试用版。 下载地址&#xff1a; IBM 中国官方网站 &#xff08;AIX各个版本和xlc编译器版本的兼容性可以…
阅读更多...
php未能在vscode识别？

php未能在vscode识别？

在设置里搜php&#xff0c;找到settings.json&#xff0c;设置你的安装路径即可。 成功
阅读更多...
Qt Creator 12.0.2 debug 无法查看变量的值 Expression too Complex

Qt Creator 12.0.2 debug 无法查看变量的值 Expression too Complex

鼠标放在局部变量上提示“expression too complex”。 在调试窗口也看不到局部变量的值。 这应该是qt的一个bug&#xff0c;https://bugreports.qt.io/browse/QTCREATORBUG-24180 暂时解决方法&#xff1a; 如下图&#xff0c;需要右键项目然后执行"Clean"和&quo…
阅读更多...
最新文章

Copyright @ 2022~2023