当前位置: 首页 > 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;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...