【数据结构】二叉树的性质和存储结构
性质
-
在二叉树的第i层上至多有2^{i-1}个结点,至少有1个结点
-
深度为k的二叉树至多有2^{k-1}个结点(k≥1),至少有k个结点
-
对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0=n2+1
-
具有n个结点的完全二叉树的深度为log_2n+1(向下取整)
-
如果对一棵有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,这个是父组件,代码如下: <template><ChildDemo /> </template><script setup> import ChildDemo from "./child.vue"; import { ref, provide } from "vue"; // 提供响应式的值 c…...
使用html2canvas实现前端截图
一、主要功能 网页截图:html2canvas通过读取DOM结构和元素的CSS样式,在客户端生成图像,不依赖于服务端的渲染。它可以将指定的DOM元素渲染为画布(canvas),并生成图像。多种输出格式:生成的图像…...
使用 Python 爬取某网站简历模板(bs4/lxml+协程)
使用 Python 爬取站长素材简历模板 简介 在本教程中,我们将学习如何使用 Python 来爬取站长素材网站上的简历模板。我们将使用requests和BeautifulSoup库来发送 HTTP 请求和解析 HTML 页面。本教程将分为两个部分:第一部分是使用BeautifulSoup的方法&am…...
深度学习模型中音频流式处理
音频流式处理的介绍 在现代深度学习应用中,音频处理是一个重要的领域,尤其是在语音识别、音乐生成和音频分类等任务中。流式处理(Streaming Processing)是一种有效的处理方式,它允许模型逐帧处理音频数据,…...
C语言(字符数组和字符指针)
字符串实现 在C语言中,表示一个字符串有以下两种形式: 用字符数组存放一个字符串。用字符指针指向一个字符串。 案例 #include <stdio.h>/*** 方式1:使用字符数组实现字符串*/ 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 (中介者接口)2.2 ChatRoom (具体中介者类)2.3 User (同事接口)2.4 ChatUser (具体同事类)2.5 Test (测试)2.6 运行结果 3. …...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
