二叉树——存储结构
二叉树的存储结构
二叉树一般可以使用两种结构存储,一种是顺序结构,另一种是链式结构。
一、顺序存储
二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。
依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映结点之间的逻辑关系,既最大可能地节省存储空间,且可以利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。但对于一般的二叉树,为了让数组下标能反映二叉树中结点之间的逻辑关系,只能添加一些并不存在的空结点大让其每个结点与完全二叉树上的结点相对照,再存储到一维数组的相应分量中。
实际就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。所以二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
例:二叉树的顺序存储中,一定要把二叉树的节点编号与完全二叉树对应起来
* i的左孩子 ——2i
* i的右孩子 ——2i+1
* i的父节点 ——[i/2]
在最坏情况下:高度为h且只有h个结点的单支树(所有结点只有右孩子)也至少需要2h-1个存储单元。其中0表示并不存在的空结点。
结论:二叉树的顺序结构,只适合存储完全二叉树。

二叉树的顺序存储结构描述如下:
#define MAXSIZE 20
typedef struct BiTNode {
ElemType data; //数据域
int 1child, rchild; //存放左、右孩子的数组下标
}BiTNode; //二叉树节点的类型BiTNode tree[MAXSIZE];
int n; //树中实际所含节点的个数
int root; //存放根节点的数组下标
二、链式存储
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域 (data)和左(lchild)、右(rchild)指针域,左、右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。


二叉树的链式存储结构描述如下:
typedef struct BiTNode {
ElemType data;//数据域
struct BiTNode *1child, *rchild;//左、右孩子指针
}BiTNode, *BiTree;
所以使用不同的存储结构时,实现二叉树操作的算法也会不同,因此要根据实际应用场合(二叉树的形态和需要进行的运算)来选择合适的存储结构。容易验证,在含有n个结点的二叉链表中,含有n+ 1个空链域
相关文章:
二叉树——存储结构
二叉树的存储结构 二叉树一般可以使用两种结构存储,一种是顺序结构,另一种是链式结构。 一、顺序存储 二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点元素存储…...
LangChain - OpenGPTs
文章目录 MessageGraph 消息图认知架构AssistantsRAGChatBot 持久化配置新模型新工具astream_events总结 关键链接: OpenGPT GitHub 存储库YouTube 上的 OpenGPT 演练LangGraph:Python、JS 两个多月前,在 OpenAI 开发日之后,我们…...
pe格式从入门到图形化显示(四)-节表
文章目录 前言一、什么是Windows PE格式节表?二、解析节表并显示1.节表数据结构以及字段描述2.节表的属性3.解析4.显示 前言 通过分析和解析Windows PE格式,并使用qt进行图形化显示 一、什么是Windows PE格式节表? PE格式的节表(…...
路由策略与路由控制之双点双向重发布(OSPF-ISIS)实验
双点双向重发布在路由协议中,特别是在OSPF(开放式最短路径优先)与IS-IS(中间系统到中间系统)等协议之间,指的是在两个协议间或者两个进程间进行路由信息共享的机制。这种机制涉及到在两个不同的协议区域使用…...
9proxy—数据采集工具全面测评
9Proxy数据采集工具Unlock the web with 9Proxy, the top residential proxy provider. Get unlimited bandwidth, affordable prices, and secure HTTPS and Socks5 configurations.https://9proxy.com/?utm_sourceblog&utm_mediumcsdn&utm_campaignyan 前言 在当今数…...
上海晶珩树莓派工业智能机械臂,亮相2024年embedded world博览会!
上海晶珩树莓派工业智能机械臂,亮相2024年embedded world博览会! 工业智能机械臂是上海晶珩(EDATEC)团队基于树莓派工业相机ED-AIC2000和树莓派工业触摸屏ED-HMI2320开发的创新应用案例。 工业智能机械臂具备卓越的定位能力&…...
蓝桥杯——求和
题目 给定 n 个整数 a1, a2,…,an,求它们两两相乘再相加的和即: Sa1a2a1a3a1ana2a3 a(n-2)*an...a(n-1)*an 输入格式 输入的第一行包含一个整数 n。 第二行包含 几 个整数 a1,a2,,an。 输出格式 输出一个整数 S,表示所…...
设计模式:责任链模式示例
责任链模式可以应用于多种场景,下面是几个不同场景的例子,每个例子都包括完整的代码。 示例1:日志处理系统 在日志处理系统中,日志消息可以根据其严重性(错误、警告、信息)被不同级别的日志处理器处理。 …...
SpringBoot快速入门笔记(4)
文章目录 一、Vue框架1、前端环境准备2、简介3、快速开始4、事件绑定 二、Vue组件化开发1、NPM2、Vue Cli3、组件化开发4、SayHello自定义组件5、Movie自定义组件 一、Vue框架 1、前端环境准备 编码工具:VSCode 依赖管理:NPM 项目构建:VueCl…...
GoPro相机使用的文件格式和频率
打开GoPro相机(以11为例),里面是一个DCIM文件夹。 DCIM是digital camera in memory 的简写,即存照片的文件夹,常见于数码相机、手机存储卡中的文件夹名字。 正常手机拍照和视频都是保存在此文件夹的。正常建议不用删,因为只要拍照…...
Redis Stack 安装部署
参考:Run Redis Stack on Docker | Redis Redis-stack 初体验_redis stack-CSDN博客 【docker】运行redis_docker run redis-stack-server requirepass-CSDN博客 Redis Stack 是一组软件套件,它主要由三部分组成。 一个是 Redis Stack Server&#x…...
【经典算法】LeetCode 5: 最长回文子串(Java/C/Python3实现含注释说明,Medium)
目录 题目描述思路及实现方式一:动态规划法思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式二:中心扩展法思路代码实现Java版本C语言版本Python3版本 复杂度分析 总结相似题目 标签(题目类型):回文串、动态规划 题目描述 给定一…...
39.Python从入门到精通—parseString 方法 Python 解析XML实例 使用xml.dom解析xml
39.Python从入门到精通—parseString 方法 Python 解析XML实例 使用xml.dom解析xml parseString 方法Python 解析XML实例使用xml.dom解析xml parseString 方法 parseString 方法是 Python 标准库中 xml.dom.minidom 模块中的一个函数,用于解析 XML 字符串并构建 DO…...
【蓝桥杯第九场小白赛】(部分)
最近写的零零散散的,感觉这两天遇到的题对于短时间提升意义已经不大了,还是做简单题保持手感吧哎 盖印章 #include <iostream> using namespace std; using LLlong long; int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);LL n,m…...
【Linux】Supervisor 基础
要在Linux上启动Supervisor,你可以按照以下步骤进行操作: 确保你已经安装了Supervisor。使用适合你的Linux发行版的包管理器进行安装。例如,对于Ubuntu,可以运行以下命令安装Supervisor: sudo apt-get update sudo apt…...
48 全连接卷积神经网络 FCN【动手学深度学习v2】
全连接卷积神经网络:神经网络处理语义分割问题的奠基性工作,目前已不太常用。 了解一下全卷积网络模型最基本的设计。 如 下图所示,全卷积网络先使用卷积神经网络抽取图像特征,然后通过11卷积层将通道数变换为类别个数࿰…...
pytorch中的nn.MSELoss()均方误差损失函数
一、nn.MSELoss()是PyTorch中的一个损失函数,用于计算均方误差损失。 均方误差损失函数通常用于回归问题中,它的作用是计算目标值和模型预测值之间的平方差的平均值。 具体来说,nn.MSELoss()函数的输入是两个张量,即模型的真实值…...
三国游戏(贪心 排序)
三国游戏 利用贪心、排序、前缀和的计算方法,特别注意不要数据溢出了,sum 加long long s[i] x[i]-y[i]-z[i]输入: 3 1 2 2 2 3 2 1 0 7输出: 2#include <bits/stdc.h> using namespace std;const int N 1e5100;typedef long long ll;bool cm…...
GPU环境安装与虚拟环境安装(适用于Windows下的李沐GPU)
之前我是用的都是VMware的虚拟机且安装的是cpu的pytorch版本,因为想要使用GPU,最终实现了在Windows上使用GPU,并且相关原理也在参考文章或视频内,可以通过原理自行挑选自己所需的配置并安装。 文章目录 1.GPU安装1.1 名词解释1.2 卸载旧版本的CUDA1.3 版本选择步骤(Nivida显卡…...
Http Download
Http / Https 下载文件,startWith不能验证https,测试地址:https://storage.googleapis.com/golang/go1.7.3.windows-amd64.msi private static final Logger logger Logger.getLogger(MethodHandles.lookup().lookupClass());private static…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
