二叉树——存储结构

二叉树的存储结构

二叉树一般可以使用两种结构存储,一种是顺序结构,另一种是链式结构。

一、顺序存储

      二叉树的顺序存储是指用一组连续的存储单元依次自上而下自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为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个空链域

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/540295.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

LeetCode 142.环形链表II(数学公式推导)

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整…

python图书馆图书借阅系统含网上商城管理系统7d538

,python语言,django框架进行开发,后台使用MySQL数据库进行信息管理,设计开发的图书管理系统。通过调研和分析,系统拥有管理员和用户两个角色,主要具备注册登录、个人信息修改、用户、图书分类、图书信息、借…

多模块项目使用springboot框架进行业务处理

项目目录 1、在Result定义返回结果 package com.edu.result;import lombok.Data;import java.io.Serializable;/*** 后端统一返回结果* param <T>*/ Data public class Result<T> implements Serializable {private Integer code; //编码&#xff1a;1成功&#xf…

【U8+】用友固定资产卡片拆分提示:未设置对象变量或With block变量。

【问题描述】 用友U8软件中&#xff0c; 操作固定资产模块&#xff0c;针对所有资产进行卡片拆分的时候&#xff0c; 提示&#xff1a;未设置对象变量或With block变量。 确定后仍然能打开卡片拆分界面&#xff0c;但是界面显示异常看不到拆分明细信息&#xff0c;并且保存后拆…

LeetCode-Java:303、304区域检索(前缀和)

文章目录 题目303、区域和检索&#xff08;数组不可变&#xff09;304、二维区域和检索&#xff08;矩阵不可变&#xff09; 解①303&#xff0c;一维前缀和②304&#xff0c;二维前缀和 算法前缀和一维前缀和二维前缀和 题目 303、区域和检索&#xff08;数组不可变&#xff…

一些 VLP 下游任务的相关探索

一、Image-Text Retrieval (ITR , 图像文本检索) 任务目的&#xff1a; 检索与给定文本最匹配的图像&#xff0c;或者给定图像最匹配的文本。 跨模态图像-文本检索&#xff08;ITR&#xff09;是根据用户给定的一种模态中的表达&#xff0c;从另一模态中检索出相关样本&#x…

工厂方法模式:解锁灵活的对象创建策略

在软件设计中&#xff0c;工厂方法模式是一种非常实用的创建型设计模式&#xff0c;它不仅提升了系统的灵活性&#xff0c;还简化了对象的创建过程。本文将详细探讨工厂方法模式的核心概念、实现方式、应用场景以及与其他设计模式的对比&#xff0c;旨在提供一份全面且实用的指…

flutter中鼠标检测事件的应用---主要在于网页端使用

flutter中鼠标检测事件的应用—主要在于网页端使用 鼠标放上去 主要代码 import package:flutter/material.dart;class CustomStack extends StatefulWidget {override_CustomStack createState() > _CustomStack(); }class _CustomStack extends State<CustomStack>…

MySQL——创建和插入

一、插入数据 INSERT 使用建议; 在任何情况下建议列出列名&#xff0c;在 VALUES 中插入值时&#xff0c;注意值和列的意义对应关系 values 指定的值顺序非常重要&#xff0c;决定了值是否被保存到正确的列中 在指定了列名的情况下&#xff0c;你可以仅对需要插入的列给到…

C++——StackQueue

目录 一Stack 1介绍 2接口 3模拟实现 4栈的oj题 二Queue 1介绍 2接口 3模拟实现 三容器适配器 1再谈栈和队列 四优先级队列 1接口 ​编辑 2仿函数 五dequeue的简单介绍 一Stack 1介绍 先来看看库中对栈的介绍&#xff1a; 1. stack是一种容器适配器&#x…

自养号测评技术:如何快速提高亚马逊、速卖通、沃尔玛新号的权重?

亚马逊平台高度关注买家账号权重&#xff0c;对于希望快速提升listing曝光与销量的卖家而言&#xff0c;拥有高权重买家账号进行下单至关重要。前提是&#xff0c;确保您的listing已经过精细优化。当前&#xff0c;市场上存在众多自养号服务商&#xff0c;然而由于多种原因&…

外汇兑换问题的最优子结构分析

外汇兑换问题的最优子结构分析 一、 当所有交易佣金为零时1.1 伪代码示例&#xff1a;1.2 C代码示例 二、 佣金不为零时的最优子结构性质三、 结论 在考虑外汇兑换问题时&#xff0c;我们面临的是如何通过一系列兑换操作&#xff0c;以最小的成本将一种货币转换为另一种货币。这…

网络变压器(网络隔离变压器)是如何影响网通设备的传输速率的呢?

Hqst华轩盛(石门盈盛)电子导读&#xff1a;今天介绍网络变压器&#xff08;网络隔离变压器/网络滤波器&#xff09;是如何影响网通设备的传输速率的 一、网络变压器&#xff08;网络隔离变压器/网络滤波器&#xff09;的工作原理 网络变压器&#xff08;网络隔离变压器/网络滤…

Docker 学习笔记(六):挑战容器数据卷技术一文通,实战多个 MySQL 数据同步,能懂会用,初学必备

一、前言 记录时间 [2024-4-11] 系列文章简摘&#xff1a; Docker学习笔记&#xff08;二&#xff09;&#xff1a;在Linux中部署Docker&#xff08;Centos7下安装docker、环境配置&#xff0c;以及镜像简单使用&#xff09; Docker 学习笔记&#xff08;三&#xff09;&#x…

arm-linux-gnueabihf-gcc默认目录

默认编译的头文件目录&#xff1a; /usr/local/arm/gcc-linaro-4.9.4-2017.01-x86_64_arm-linux-gnueabihf/arm-linux-gnueabihf/lib 默认编译的库文件目录&#xff1a; /usr/local/arm/gcc-linaro-4.9.4-2017.01-x86_64_arm-linux-gnueabihf/arm-linux-gnueabihf/include/ …

校招生如何准备软件测试、测试开发岗位的面试?

校招生如何准备软件测试、测试开发岗位的面试&#xff1f; 求职建议 大家都很困惑如何学习测试&#xff1f;如何准备测试方面的面试&#xff1f; 我有朋友是做研发的&#xff0c;他认为测试不用准备&#xff0c;直接用开发的简历就行。也有人认为要学习一些测试理论&#xf…

使用 create-vue 脚手架工具创建一个基于 Vite 的项目,并包含加入 Vue Router 等可选项

如果你打算启动一个新项目&#xff0c;你可能会发现使用 create-vue 这个脚手架工具更容易&#xff0c;它能创建一个基于 Vite 的项目&#xff0c;并包含加入 Vue Router 的选项&#xff0c;指令如下&#xff1a; // npm npm create vuelatest// yarn yarn create vue// pnpm …

HTML、CSS --javaweb学习笔记

记录一些重要的知识点 CSS引入方式 行内样式&#xff1a;<h1 style"...">内嵌样式&#xff1a;<style>…</style>外联样式&#xff1a;xxx.css <link href"..."> 颜色表示 关键字&#xff1a;red、green.......rgb表示法&…

java快速构建飞书API消息推送、消息加急等功能

文章目录 飞书机器人自定义机器人自定义应用机器人 自定义应用发送消息普通文本 text富文本 post图片 image文件 file语音 audio视频 media消息卡片 interactive分享群名片 share_chat分享个人名片 share_user 批量发送消息消息加急发送应用内加急发送短信加急 发送电话加急spr…

【随身wifi京东金榜排名】格行vs华为vs上赞随身wifi哪款最好用?格行随身wifi官方正品,格行随身wifi怎么样?

第一名&#xff1a;格行随身wifi 综合分99.1 随身WiFi行业领跑品牌 &#xff0c;15年行业经验 &#xff0c;随身WiFi口碑榜第一名。轻便小巧&#xff0c;支持三网通&#xff0c;可以随时随地提供稳定高速的网络连接。使用目前先进的马维尔芯片&#xff0c;信号稳定&#xff0…