当前位置: 首页 > news >正文

【数据结构】二叉树的性质和存储结构

性质

  1. 在二叉树的第i层上至多有2^{i-1}个结点,至少有1个结点

  2. 深度为k的二叉树至多有2^{k-1}个结点(k≥1),至少有k个结点

  3. 对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0=n2+1

  4. 具有n个结点的完全二叉树的深度为log_2n+1(向下取整)

  5. 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第一层到第log_2n+1层,每层从左到右),则对任一结点i,有:

(1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点i/2(向下取整)

(2)如果2i>n,则结点i无左孩子(结点i为叶子结点),否则其左孩子是结点2i

(3)如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1

存储结构

顺序存储

实现:按满二叉树的结点层次编号,依次存放二叉树的数据元素

#define MAXSIZE 100
Typedef TElemType SqBiTree[MAXSIZE]
SqBiTree bt;

顺序存储的缺点:浪费空间

最坏情况:深度为k的且只有k个节点的单支树需要长度为2^k-1的一维数组

适合于满二叉树和完全二叉树

链式存储

二叉链表:一个数据域和两个指针域,指向左右孩子

typedef struct BiNode{TElemTYpe data;struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode, *BiTree;

在n个结点的二叉链表中,有n+1个空指针域

n个结点共有2n个指针域,除根结点外,每个结点有且仅有一个双亲,所以有n-1个结点的指针域存放指向孩子的指针,剩余n+1个指针为空指针

三叉链表:增加一个指针域指向双亲

typedef struct TriNode{TElemTYpe data;struct TriNode *lchild,*rchild,*parent;//左右孩子指针和双亲指针
}TriNode, *TriTree;

相关文章:

【数据结构】二叉树的性质和存储结构

性质 在二叉树的第i层上至多有2^{i-1}个结点,至少有1个结点 深度为k的二叉树至多有2^{k-1}个结点(k≥1),至少有k个结点 对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0n21 具有n个结点的完…...

gbase8s之查看锁表的sql

#只能看当前锁表的sql,看不到历史的。 #使用方法:sh 脚本文件名 库名 表名 database$1 table$2 hexoncheck -pt $database:$table|grep -i partnum|awk {printf ("%x|",$3)} #echo $hex #echo ${hex%?} #ownonstat -k |grep -iE ${he…...

URI 未注册(设置 语言和框架 架构和 DTD)

一、问题描述:在springboot项目中的resources中新建mybatis-config.xml文件时,从mybatis文档中复制的代码报错:URI 未注册(设置 | 语言和框架 | 架构和 DTD) 二、解决:在Springboot项目的设置->架构和DTD中添加 红色的网址&…...

Ubuntu上使用system()函数运行不需要输入密码

使用system()运行一些终端命令的时候,需要sudo权限,也就是必须输入密码,那么在程序自启动的时候就无法成功启动。如果设置Ubuntu下所有操作都不需要密码,安全性太低,所以我们可以将需要用到的终端指令给予无需输入密码…...

【MySQL】数据库必备知识:全面整合表的约束与深度解析

前言:本节内容讲述表的约束的相关内容。 表的约束博主将会通过两篇文章进行讲解, 这是第一篇上半部分。 讲到了约束概念。 以及几种常见约束。下面友友们开始学习吧! ps:友友们使用了mysql就可以放心观看喽! 目录 表的约束概念 …...

Windows下Docker快速安装使用教程

在当今软件开发和部署的世界中,Docker 已经成为一个不可或缺的工具。这里不对Docker进行详细阐述,需要系统学习Docker的伙伴可寻求更专业详细的教程或书籍学习。本文主要讲解Windows系统下Docker安装及使用。 一、环境准备 1.1检查电脑是否开启虚拟化 …...

PTA DS 6-2 另类堆栈 (C补全函数)

6-2 另类堆栈 分数 15 全屏浏览 切换布局 作者 DS课程组 单位 浙江大学 在栈的顺序存储实现中,另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满? 函数接口定义: …...

rk3568之mpp开发笔记mpp移植到开发板

前言: 大家好,今天给大家介绍的内容是rk平台的mpp编解码这块的内容,在rk目前看到有三套框架涉及到编解码内容: 1、rkmedia 2、rockit 3、mpp 这三种不同形式的编解码方式,后面再做详细的框架对比,今天我…...

Vue解决跨域问题

要解决 Vue 项目的跨域问题并通过 vue.config.js 配置代理,可以按照以下步骤修改 vue.config.js 文件。你提供的代码大部分已经正确,只需要做一些格式上的调整。以下是正确的 vue.config.js 配置: // vue.config.jsmodule.exports {devServ…...

Kubernetes Nginx-Ingress | 禁用HSTS/禁止重定向到https

目录 前言禁用HSTS禁止重定向到https关闭 HSTS 和设置 ssl-redirect 为 false 的区别 前言 客户请求经过ingress到服务后,默认加上了strict-transport-security,导致客户服务跨域请求失败,具体Response Headers信息如下; 分析 n…...

TortoiseGit的下载、安装和配置

一、TortoiseGit的简介 tortoiseGit是一个开放的git版本控制系统的源客户端,支持Winxp/vista/win7.该软件功能和git一样 不同的是:git是命令行操作模式,tortoiseGit界面化操作模式,不用记git相关命令就可以直接操作,读…...

如何绕过IP禁令

网站、游戏和应用程序可以屏蔽特定IP地址,从而阻止使用该IP地址的任何人访问其服务。这称为IP禁令。管理员可以出于多种原因(例如发出过多请求或可疑活动)屏蔽IP地址。但是,这些禁令会使收集数据或访问在线内容变得更加困难。 一…...

Vue3的provide和inject实现多级传递的原理

先来看个demo&#xff0c;这个是父组件&#xff0c;代码如下&#xff1a; <template><ChildDemo /> </template><script setup> import ChildDemo from "./child.vue"; import { ref, provide } from "vue"; // 提供响应式的值 c…...

使用html2canvas实现前端截图

一、主要功能 网页截图&#xff1a;html2canvas通过读取DOM结构和元素的CSS样式&#xff0c;在客户端生成图像&#xff0c;不依赖于服务端的渲染。它可以将指定的DOM元素渲染为画布&#xff08;canvas&#xff09;&#xff0c;并生成图像。多种输出格式&#xff1a;生成的图像…...

使用 Python 爬取某网站简历模板(bs4/lxml+协程)

使用 Python 爬取站长素材简历模板 简介 在本教程中&#xff0c;我们将学习如何使用 Python 来爬取站长素材网站上的简历模板。我们将使用requests和BeautifulSoup库来发送 HTTP 请求和解析 HTML 页面。本教程将分为两个部分&#xff1a;第一部分是使用BeautifulSoup的方法&am…...

深度学习模型中音频流式处理

音频流式处理的介绍 在现代深度学习应用中&#xff0c;音频处理是一个重要的领域&#xff0c;尤其是在语音识别、音乐生成和音频分类等任务中。流式处理&#xff08;Streaming Processing&#xff09;是一种有效的处理方式&#xff0c;它允许模型逐帧处理音频数据&#xff0c;…...

C语言(字符数组和字符指针)

字符串实现 在C语言中&#xff0c;表示一个字符串有以下两种形式&#xff1a; 用字符数组存放一个字符串。用字符指针指向一个字符串。 案例 #include <stdio.h>/*** 方式1&#xff1a;使用字符数组实现字符串*/ void str_test1(){// 定义一个伪字符串char str[] &q…...

SkyWalking Helm Chart 4.7.0 安装、配置

https://skywalking.apache.org/events/release-apache-skywalking-kubernetes-helm-chart-4.7.0/https://github.com/apache/skywalking-helm/tree/v4.7.0https://skywalking.apache.org/zh/2020-04-19-skywalking-quick-start/简介 skywalking 是分布式系统的 APM(Applicat…...

微搭低代码AI组件单词消消乐从0到1实践

目录 1 为什么要开发单词消消乐2 需要具备什么功能3 采用什么技术方案实现4 逻辑设计4.1 数据结构设计4.2 游戏的核心逻辑4.3 数据设计 5 代码详解5.1 导入依赖5.2 定义函数组件5.3 数据初始化5.4 状态定义5.5 打乱解释的逻辑5.6 定义选择单词的函数5.7 定义选择解释的函数5.8 …...

23种设计模式之中介者模式

目录 1. 简介2. 代码2.1 Mediator &#xff08;中介者接口&#xff09;2.2 ChatRoom &#xff08;具体中介者类&#xff09;2.3 User &#xff08;同事接口&#xff09;2.4 ChatUser &#xff08;具体同事类&#xff09;2.5 Test &#xff08;测试&#xff09;2.6 运行结果 3. …...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...