二叉树——存储结构
二叉树的存储结构
二叉树一般可以使用两种结构存储,一种是顺序结构,另一种是链式结构。
一、顺序存储
二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为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…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
WebRTC调研
WebRTC是什么,为什么,如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
