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

数据结构—基础知识(13):树的存储结构

数据结构—基础知识(13):树的存储结构

  1. 双亲表示法

    这种表示方法中,以一组连续的存储单元存储树的结点,每个结点除了数据域data外,还附设一个parent域用以指示其双亲结点的位置。
    在这里插入图片描述

    这种存储结构利用了每个结点(除根结点外)只有唯一的双亲性质。这种存储结构下,求结点的双亲十分方便,也很容易求树的根,但求结点的孩子时需要遍历整个结构

  2. 孩子表示法

    由于树中每个结点可能有多棵子树,则可用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,此时链表中的结点可以有如下图的两种结点格式。
    在这里插入图片描述

    若采用第一种结点格式,则多重链表中的结点是同构的,其中d为树的度。由于树中很多结点的度小于 d,所以链表中有很多空链域,空间较浪费,不难推出,在一棵有n个结点度为k的树中必有n(k-1)+1 个空链域

    若采用第二种结点格式,则多重链表中的结点是不同构的,其中d为结点的度,degree 域的值同d。此时,虽能节约存储空间,但操作不方便

    另一种办法是,把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表做存储结构,则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构。

    下图(a)所示为下图中的树的孩子表示法。与双亲表示法相反,孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来,即将双亲表示和孩子链表合在一起。图(b)所示的就是这种存储结构的一例,它和图(a)表示的是同一棵树。
    在这里插入图片描述

  3. 孩子兄弟法

    孩子兄弟法又称二叉树表示法,或者二叉链表表示法,即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点(firstchild)和下一个兄弟结点(nextsibling)

    //------树的二叉链表(孩子—兄弟)存储表示------
    typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;
    }CSNode,*CSTree;
    

在这里插入图片描述

相关文章:

数据结构—基础知识(13):树的存储结构

数据结构—基础知识(13):树的存储结构 双亲表示法 这种表示方法中,以一组连续的存储单元存储树的结点,每个结点除了数据域data外,还附设一个parent域用以指示其双亲结点的位置。 这种存储结构利用了每个结…...

【Python爬虫入门到精通】小白也能看懂的知识要点与学习路线

文章目录 1. 写在前面2. 爬虫行业情况3. 学习路线 【作者主页】:吴秋霖 【作者介绍】:Python领域优质创作者、阿里云博客专家、华为云享专家。长期致力于Python与爬虫领域研究与开发工作! 【作者推荐】:对JS逆向感兴趣的朋友可以关…...

服务器数据恢复—EVA存储raid5硬盘离线的数据恢复案例

服务器数据恢复环境: 某品牌EVA某型号存储,底层是RAID5阵列,划分了若干lun。 服务器故障&分析: 该存储设备中raid5阵列有两块硬盘掉线,存储中的lun丢失。 将故障服务器存储中的所有磁盘编号后取出,硬件…...

MAMBA论文疑被拒收,计算机科学顶会评审遭质疑

2023 年底,卡内基梅隆和普林斯顿大学计算机系的两位年轻科学家(Albert Gu, Tri Dao)联合推出一种叫做“Mamba”的大语言模型(LLM)新构架。与Transformers等传统模型相比,Mamba能够更有效地处理长序列。它利…...

EHS管理系统为何需要物联网的加持?

EHS是Environment、Health、Safety的缩写,是从欧美企业引进的管理体系,在国外也被称为HSE。EHS是指健康、安全与环境一体化的管理。 而在国内,整个EHS市场一共被分成三类; 一类是EHS管培体系,由专门的EHS机构去为公司…...

记事本(父页面与iframe子页面的联通,vue3+ts展示fbx模型,与tga贴图)

vue3ts 展示fbx与tga贴图 npm i three --save <template><div ref"modelContainer"></div> </template><script setup lang"ts"> import { ref, onMounted } from vue; import * as THREE from three; import { FBXLoader…...

【好书推荐-第五期】《互联网大厂推荐算法实战》(异步图书出品)

&#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号&#xff1a;程序员洲洲。 &#x1f388; 本文专栏&#xff1a;本文…...

C++ Qt day2

自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height)&#xff0c; 定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void show() #include <io…...

Mac上如何设置映射某个网站站点域名的IP

最近某常用的站点换 IP 了&#xff0c;但是 DNS 服务器还没有修改&#xff0c;这就导致无法访问&#xff08;换 DNS 服务器也不行&#xff09;。在用了一段时间的 IP 访问之后&#xff0c;还是没好&#xff0c;不知道是 DNS 污染还是咋了&#xff0c;所以最后还是手动改一下吧。…...

智能分析网关V4智慧冶金工厂视频智能监管方案

一、背景与需求 随着工业4.0的推进&#xff0c;冶金行业正面临着转型升级的压力。为了提高生产效率、降低能耗、保障安全&#xff0c;冶金智能工厂视频监管方案应运而生。该方案通过高清摄像头、智能分析技术、大数据处理等手段&#xff0c;对工厂进行全方位、实时监控&#xf…...

WebSocket实现HTML+SpringBoot聊天功能,小程序+SpringBoot聊天功能

目录 一、认识WebSocket 二、HTML实现聊天 三、微信小程序实现聊天 一、认识WebSocket 1.首先博主在初学Java时自我感觉走了很多弯路&#xff0c;因为以前见识短&#xff0c;在接触聊天功能时根本就没能想到有WebSocket这个聊天框架&#xff0c;就只能用底层的UDP或TCP实现聊…...

SpringMVC-RESTFul

文章目录 RESTFul一、基础概念二、增删改查1.查询全部用户信息 &#xff08;GET&#xff09;2.根据id查询用户信息3.添加用户&#xff08;POST&#xff09;4.修改用户 &#xff08;PUT&#xff09;5.删除用户 &#xff08;DELETE&#xff09; RESTFul 一、基础概念 二、增删改…...

Spring Boot3整合knife4j(swagger3)

目录 1.前置条件 2.导依赖 3.配置 1.前置条件 已经初始化好一个spring boot项目且版本为3X&#xff0c;项目可正常启动。 作者版本为3.2.2 初始化教程&#xff1a; 新版idea创建spring boot项目-CSDN博客https://blog.csdn.net/qq_62262918/article/details/135785412?…...

解决Windows系统本地端口被占用

目录 一、被程序占用端口 1.通过终端杀掉占用端口的进程 2.任务管理器 二、被系统列为保留端口 前言&#xff1a; 首先了解为什么会出现端口被占用的情况 端口被占用的情况可能出现的原因有很多&#xff0c;主要有以下几点&#xff1a; 1.多个应用程序同时启动&…...

GPS位置虚拟软件 AnyGo mac激活版

AnyGo for Mac是一款一键将iPhone的GPS位置更改为任何位置的强大软件&#xff01;使用AnyGo在其iOS或Android设备上改变其GPS位置&#xff0c;并在任何想要的地方显示自己的位置。这对那些需要测试应用程序、游戏或其他依赖于地理位置信息的应用程序的开发人员来说非常有用&…...

视频号视频怎么使用视频号下载助手提取视频呢?

微信视频号怎么使用视频下载助手提取视频&#xff0c;今天就和大家一起来看看我是如何操作的。 关于视频下载助手&#xff0c;给大家准备好了。获取方式在文末。注意看下关键词&#xff0c;家人们。 微信视频号是微信平台上的一个短视频分享功能&#xff0c;类似于抖音、快手这…...

第一篇【传奇开心果短博文系列】鸿蒙开发技术点案例示例:从helloworld开始理解鸿蒙开发ArkTS编程思路

传奇开心果短博文系列 系列短博文目录鸿蒙开发技术点案例示例系列 短博文目录一、前言二、初步解读鸿蒙的helloworld三、进一步深入解读理解 系列短博文目录 鸿蒙开发技术点案例示例系列 短博文目录 一、前言 从掰碎了揉烂了详细注释解读helloworld开始&#xff0c;理解Ark…...

四、MySQL之DML DQL

有关数据表的DML操作 INSERT 针对于数据的插入DELETE 针对于数据的删除UPDATE 针对于数据的修改 4.1 INSERT语句 INSERT INTO 表名 [(列名1,列名2,....)] VALUES (值1&#xff0c;值2&#xff0c;...); 默认情况下&#xff0c;一条插入命令只针对一行进行影响INSERT INTO 表…...

YOLOv8优化策略:注意力涨点系列篇 | 多尺度双视觉Dualattention | Dual-ViT,顶刊TPAMI 2023

🚀🚀🚀本文改进:多尺度双视觉Dualattention注意yolo,提升小目标检测能力 🚀🚀🚀YOLOv8改进专栏:http://t.csdnimg.cn/hGhVK 学姐带你学习YOLOv8,从入门到创新,轻轻松松搞定科研; 1.原理介绍 论文:Dual Vision Transformer | IEEE Journals & Magazine …...

视频渲染靠cpu还是显卡 会声会影视频渲染的作用是什么

视频渲染最占用的资源就是CPU&#xff0c;多核心多线程&#xff0c;这样才能渲染快。渲染可以在时间线上实时平滑预览&#xff0c;便于编辑&#xff0c;最终导出成片的时候速度也会快一些&#xff0c;渲染就是对每桢的图像进行重新优化的过程。 渲染的作用主要是能够保证使用者…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...