数据结构界的终极幻神----树

目录

一.数的概念和分类

种类

二.重点概念

哈希树:

二叉树的线索化

什么是线索化

为什么要线索化

特殊的查找树

完全二叉树

三.手撕完全二叉树(堆)

重点讲解

向上搜索算法

向下搜索算法


一.数的概念和分类

树(tree)是包含 n(n≥0) [2] 个节点,当 n=0 时,称为空树,非空树中

条边的有穷集,在非空树中:

(1)每个元素称为节点(node)。

(2)有一个特定的节点被称为根节点或树根(root)。

(3)除根节点之外的其余数据元素被分为个互不相交的集合,其中每一个集合本身也是一棵树,被称作原树的子树(subtree)。

树也可以这样定义:树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点,所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位,这个节点称为该树的根节点,或称为树根。

树中的节点具有明显的层级关系,并且一个节点可以对应多个节点。 我们可以形式地给出树的递归定义如下:

单个节点是一棵树,树根就是该节点本身。

是树,它们的根节点分别为

。用一个新节点

作为

的父亲,则得到一棵新树,节点n就是新树的根。我们称

为一组兄弟节点,它们都是节点

的子节点。我们还称

为节点n的子树。

空集合也是树,称为空树。空树中没有节点;

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

节点的度:一个节点含有的子节点的个数称为该节点的度;

叶节点或终端节点:度为0的节点称为叶节点;

非终端节点或分支节点:度不为0的节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

兄弟节点:具有相同父节点的节点互称为兄弟节点;

树的度:一棵树中,最大的节点的度称为树的度;

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次;

堂兄弟节点:双亲在同一层的节点互为堂兄弟;

节点的祖先:从根到该节点所经分支上的所有节点;

子孙:以某节点为根的子树中任一节点都称为该节点的子孙;

森林:由

棵互不相交的树的集合称为森林。

种类

无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;

有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;

二叉树:每个节点最多含有两个子树的树称为二叉树;

满二叉树:叶节点除外的所有节点均含有两个子树的树被称为满二叉树;

完全二叉树:除最后一层外,所有层都是满节点,且最后一层缺右边连续节点的二叉树称为完全二叉树;

二叉搜索树:满足左子节点比父节点小,右子节点比父节点大

哈夫曼树(最优二叉树):带权路径最短的二叉树称为哈夫曼树或最优二叉树。

二.重点概念

哈希树:

其实在数据结构中哈希树的概念并不怎么被认可,不过在区块链中确实有这种概念

哈希树,也称为默克尔树(Merkle Tree),是一种树形数据结构,用于在计算机科学中高效地验证和组织数据。哈希树特别适用于需要快速查找和验证大量数据的情况,如在区块链技术中。

哈希树的每个节点都包含数据的哈希值,这使得它可以用于数据完整性的验证。树的根节点包含整个数据结构的哈希值,即默克尔根(Merkle Root)。如果数据结构中的任何部分发生更改,会导致默克尔根变化,从而能够检测到这些更改。

哈希树在密码学和安全领域有着广泛的应用,特别是在数字签名和加密货币(如比特币)中,它用于确保交易记录的安全性和不可篡改性。

二叉树的线索化

什么是线索化

线索化的步骤:

根据某种遍历序列(前、中后序遍历),先确定下来每个节点的前驱和后继。
对于每个节点来说,他的左右指针可能没有指向节点(值为NULL),这时候我们可以运用这些“空闲”的指针。比如:左指针如果有空闲,就用这个指针指向这个节点对应遍历序列的前驱,右指针如果有空闲,就用这个指针指向这个节点对应遍历序列的后继。(注意:遍历序列中一头一尾是没有前驱或者后继的,所以如果指针有空闲,我们还是当它指向的是孩子,而不是前驱或者后继)
对于每个节点都实现了步骤2后,线索化完成

为什么要线索化

我们来线索化主要有两个原因

从空间上来说
对于一颗有n个节点二叉树,每个节点都有两个指针,这一棵树的所有节点总共有2n个指针。对于除了根节点以外的节点,每个节点都对应着一个指向其的指针,有且仅有这些指针是非空的,共有(n-1)个指针,那么空值指针就有n+1个,这个数量是很大的,对于空间的浪费也比较多
从遍历实现上
在我们用二叉树的递归遍历时,会遇到两个问题,一是:遍历需要的时间较多;二是:递归时候不断创建函数副本,对于内存来说也有一定压力。如果我们只用先进行一次递归遍历实现线索化,之后通过线索来遍历,能大大减少遍历时间和内存风险。
或者栈等数据结构来保持遍历的状态。而线索化后的二叉树可以通过线索(即额外的指针)直接找到前驱和后继节点,从而无需用额外的空间。这样可以提高遍历的效率和性能。
原文链接:https://blog.csdn.net/m0_74222411/article/details/132240822

我们常听到有的人说线索二叉树,但其实这种说法并不准确,准确来说应该是二叉树的线索化

特殊的查找树

但所有子节点都比父节点大时,就会破会树状结构,这是就引入了一些新的树形结构AVL树,红黑树

完全二叉树

通俗来讲就是,该结构的n-1层都被填满,最后一层可以不满,但从左至右不能有空位,必须按位置顺序排列,不能两个子节点中间空一个节点的位置

而满二叉树则是一种特殊的完全二叉树,堆则是完全二叉树

堆分为大堆和小堆

大堆即父节点的数据大于子节点,小堆反之

三.手撕完全二叉树(堆)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* data;
	int size;
	int capacity;
}HP;
void initHP(HP* php)
{
	assert(php);
	php->data = NULL;
	php->size = 0;
	php->capacity = 0;
}
void destroyHP(HP* php)
{
	assert(php);
	free(php->data);
	php->capacity = 0;
	php->size = 0;
}
void Swap(HeapDataType* x, HeapDataType* y)
{
	HeapDataType temp = *x;
	*x = *y;
	*y = temp;
}
void adjustUP(HeapDataType* p, int size, HeapDataType data)
{
	int child = size;
	int parent = (child - 1) / 2;
	while (parent >= 0)
	{
		if (p[parent] < p[child])
		{
			Swap(&p[parent], &p[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else break;
	}
}
void pushHP(HP* php, HeapDataType data)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(php->data, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
			return;
		php->data = tmp;
		php->capacity = newcapacity;
	}
	php->data[php->size] = data;
	php->size++;
	adjustUP(php->data, php->size - 1, data);
}
bool isEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
HeapDataType topHP(HP* php)
{
	assert(php);
	assert(!isEmpty(php));
	return php->data[0];
}
void adjustDown(HeapDataType* p, int size, HeapDataType data)
{
	int parent = 0;
	int child = parent * 2 + 1;
	if (p[child] < p[child + 1])
		child++;
	while (child <= size)
	{
		if (child + 1 <= size && p[parent] < p[child])
		{
			Swap(&p[parent], &p[child]);
			parent = child;
			child = child * 2 + 1;
			if (p[child] < p[child + 1])
				child++;
		}
		else break;
	}
}
void popHP(HP* php)
{
	assert(php);
	assert(!isEmpty(php));
	Swap(&php->data[0], &php->data[php->size - 1]);
	php->size--;
	adjustDown(php->data, php->size, php->data[0]);
}

重点讲解

向上搜索算法

在我们插入新的数据到该结构时(这里以小堆为例),我们需要判断子节点是否会比父节点还小,如果是,则要将子节点与父节点进行交换,直到不是

向下搜索算法

与向上搜索算法同理,应用于删除第一个节点

首先将第一个数据和最后一个数据交换位置,然后让新的第一个数据向下(因为这个数据为父节点,有可能比下面的某个子节点小),这是我们有两个选择,与左节点交换还是右节点,答案是最小的那个,这样才能保证最后被换上来的父节点最小

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

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

相关文章

4万+条LDZ数据上线啦!快来体验专属于你的设计数据包

利驰电天下资源集市LDZ库正式上线后&#xff0c;物料数据已更新至44151条&#xff01;你在做自动化设计时找不到元件物料&#xff1f;物料过时&#xff1f;物料信息有误&#xff1f;花高价买的物料信息重复&#xff1f;利驰官方的LDZ库可以帮助你解决这些问题。 LDZ库为电气设…

解决 Pandas 导出文件出现 dtype: object 字样

文章目录 1. 问题2. 解决方法 1. 问题 python 用 pandas 输出 excel 文件时&#xff0c;发现有些列的单元格出现 “dtype: object” 的字样&#xff0c;如下图&#xff1a; 这是 pandas 没有处理好导致的 2. 解决方法 结果用 .values 进行输出&#xff0c;这样就转成字符串…

请说明Vue中的Error Boundaries

当我们开发基于Vue框架的应用时&#xff0c;我们经常会遇到各种错误处理的情况。Vue提供了一种非常强大且简单的方式来处理这些错误&#xff0c;那就是Error Boundaries&#xff08;错误边界&#xff09;。本文将从概念、用法和示例代码三个方面来详细介绍Vue中的Error Boundar…

多媒体信息处理-重点知识-3. Feature Indexing and Retrieval

Chap 3. Feature Indexing and Retrieval 什么是索引&#xff1f; 为了提高数据集的检索效率而生成的结构化信息 基于特征的相似度匹配是多媒体数据检索方法的基础 从多媒体对象中提取重要特征&#xff0c;将其转化成高维特征向量存储在数据库中 相似性度量&#xff1a; 两种…

springboot245科研项目验收管理系统

科研项目验收管理系统 摘 要 使用旧方法对科研项目信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在科研项目信息的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次…

Tomcat性能调优

1‍.应用场景/常见内容溢出问题‍ 常见问题为内存溢出&#xff0c;分为堆内存溢出、非堆内存溢出&#xff0c;比较常见的为堆内存溢出&#xff0c;后2类属于非堆内存溢出。 堆溢出&#xff1a; java.lang.OutOfMemoryError:Java heap spcace 原因:项目运行阶段,new的对象过多…

Linux CentOS系统安装Spug并结合内网穿透实现远程访问本地运维平台

目录 前言 1. Docker安装Spug 2 . 本地访问测试 3. Linux 安装cpolar 4. 配置Spug公网访问地址 5. 公网远程访问Spug管理界面 6. 固定Spug公网地址 结语 作者简介&#xff1a; 懒大王敲代码&#xff0c;计算机专业应届生 今天给大家聊聊Linux CentOS系统安装Spug并结合…

Leetcode刷题(三十八)

旋转矩阵&#xff08;Medium&#xff09; 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。示例 1&#xff1a;输入&#xff1a;mat…

Blazor系统教程(.net8)

Blazor系统教程 1.认识 Blazor 简单来讲&#xff0c;Blazor旨在使用C#来替代JavaScript的Web应用程序的UI框架。其主要优势有&#xff1a; 使用C#编写代码&#xff0c;这可提高应用开发和维护的效率利用现有的NET库生态系统受益于NET的性能、可靠性和安全性与新式托管平台(如…

MYSQL使用mysqldump备份、复原数据库

参考 添加链接描述 1. 备份数据库 C:\Windows\system32>mysqldump -uroot -p test student>C:\student.sql Enter password: ****2. 备份多个数据库 mysqldump -u root -p --databases test mysql>C:\testandmysql.sql3. 备份所有数据库 mysqldump -u root -p -…

二维码样式修改如何在线处理?在电脑上改二维码图案的方法

随着网络的不断发展&#xff0c;二维码的应用场景不断增多&#xff0c;很多人都会将内容放到二维码中&#xff0c;通过扫码的方式将储存在云端的数据调取显示。而面对不同的用途时&#xff0c;对二维码的样式也会有单独的要求&#xff0c;比如需要改变颜色、加入文字、logo、尺…

加油!你也可以成为学生口中的“好老师”

在教育的道路上&#xff0c;每一位教师都承载着塑造未来的重要使命。而成为学生口中的“好老师”&#xff0c;无疑是每位教育工作者的追求和荣耀。那么&#xff0c;如何才能成为这样的“好老师”呢&#xff1f; 一、热爱教育&#xff0c;关爱学生 成为“好老师”的首要条件是对…

神经网络(neural network)

在这一章中我们将进入深度学习算法&#xff0c;学习一些神经网络相关的知识&#xff0c;这些是有更加强大的作用&#xff0c;更加广泛的用途。 神经元和大脑(neurons and the brain): 我们对于我们的编程的进步主要来自我们对于大脑的研究&#xff0c;根据我们对于大脑的研究…

Vue系列-环境快速搭建

vue环境快速搭建 演示视频 快速搭建Vue开发环境pnpm和yarn 1. 基本信息 作者: GMCY系列: Vue仓库: GitHub | Gitee话题(GitHub): tools \ vue创建时间: 2024/03/02 2. 介绍 功能 批处理文件vue 环境的快速搭建nodejs, npm, pnpm, yarn 自动 下载安装npm, pnpm, yarn 自动 …

网络空间资产安全解决方案

长期以来&#xff0c;我们一直强调要做好网络安全建设&#xff0c;而其中的第一步就是要做好对自身资产的发现和清点&#xff0c;正如大家经常所说的那句话——“你无法保护你看不见的东西”。的确&#xff0c;如果不知道自己拥有什么资产&#xff0c;那么如何去了解与它们相关…

js 实现点击按钮小球加入购物车动画

本文旨在实现类似点击按钮实现小球加入购物车效果。 使用技术&#xff1a; Vue2使用 Pubsub 监听按钮点击事件&#xff08;如果不想用也可以自己改造下&#xff09;监听 onmousemove 来获取按钮点击时的鼠标位置 小球组件&#xff1a; html css&#xff1a; 小球父元素&am…

小心!Springer旗下34年老刊大量撤稿中国论文,16天见刊,中国人该如何应对?

毕业推荐 SCIE&#xff1a; • 计算机类&#xff0c;6.5-7.0&#xff0c;JCR1区&#xff0c;中科院2区 • 2个月19天录用&#xff0c;6天见刊&#xff0c;36天检索 SCI&EI&#xff08;CCF-C类&#xff09; • 算法类&#xff0c;2.0-3.0&#xff0c;JCR3区&#xff0c;…

ChatGPT提问技巧——标准提示

ChatGPT提问技巧——标准提示 标准提示是一种通过向模型提供一个具体要完成的任务&#xff0c;指导ChatGPT输出的简单方式。例如&#xff0c;如果你想生成一个新闻的总结&#xff0c;你要提供一个任务像这样的“总结一下这篇新闻文章“。 提示格式&#xff1a;”生成【任务】…

IoT数据采集网关在企业应用中扮演着关键角色-天拓四方

随着物联网&#xff08;IoT&#xff09;技术的不断发展&#xff0c;越来越多的企业开始利用IoT技术实现智能化、自动化的生产和管理。在这个过程中&#xff0c;IoT数据采集网关作为连接物理世界与数字世界的桥梁&#xff0c;发挥着至关重要的作用。 IoT数据采集网关是一种硬件…

LeetCode 2917.找出数组中的 K-or 值:基础位运算

【LetMeFly】2917.找出数组中的 K-or 值&#xff1a;基础位运算 力扣题目链接&#xff1a;https://leetcode.cn/problems/find-the-k-or-of-an-array/ 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 nums 中的 K-or 是一个满足以下条件的非负整数&#xff1a; 只有…