当前位置: 首页 > 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. …...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...