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

树的基本概念和存储结构

一、树的基本概念

1、树的定义


树是n(n>=0)个结点的有限集。当n = 0时,称为空树。在任意一棵非空树中应满足:

    1、有且仅有一个特定的称为根的结点。
    2、当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树。

    显然,树的定义是递归的,即在树的定义中又用到了自身,树是一种递归的数据结构。树作为一种逻辑结构,同时也是一种分层结构,具有以下特点:

    ①没有父节点的节点称为根节点;
    ②每一个非根节点有且只有一个父节点;
    ③每个子树是不相交的;
    ④n个结点的树中有n-1条边。

结合图来看,可能会更好理解

这就是一棵典型的二叉树

这里,2,3共有子节点5,也就是5有两个父亲,那么上图就不是树了。

这里,CF组成的子树与DGH组成的子树相交,那么上图也不是树了。

2、基本术语

1、祖先、子孙,父亲、孩子、兄弟:

      根节点A到结点K的路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。

       路径上最接近结点K的结点E称为K的父亲,而K为结点E的孩子。根节点A是树中唯一没有父亲的结点。

       有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。


2、节点的度、树的度

      树中一个结点的孩子个数称为该结点的度,

      树中结点的最大度数称为树的度。

      如结点B的度为2,结点D的度为3,树的度为3。


3、分支结点、叶子结点

      度大于0的结点称为分支结点(又称非终端结点,如BCDEH);

      度为0(没有孩子结点)的结点称为叶子结点(又称终端结点,如KLFGMIJ)。

     
4、结点的深度、高度、层次
     结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。

     双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。

     结点的深度是从根结点开始自顶向下逐层累加的。

     结点的高度是从叶结点开始自底向上逐层累加的。

     树的高度(或深度)是树中结点的最大层数。图中树的高度为4。

5、有序树、无序树

     树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树

     树中任意节点的子节点之间有顺序关系,这种树称为有序树

6、路径、路径长度。

      树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的的个数。
      注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。

7、森林

     森林是m (m≥0)棵互不相交的树的集合。

      森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给m棵独立的树加上一个结点,并把这m棵树作为该结点的子树,则森林就变成了树。

注意:上述概念无须刻意记忆, 根据实例理解即可。

二、树的存储结构

    1、双亲表示法

实现:定义结构数组,存放树的结点,每个结点有两个域,分别是数据域和指针域(双亲域),数据域用于存放结点本身信息,指针域用于存放本结点的双亲结点在数组中的位置。

双亲表示的结点结构

data(数据域)parent(指针域)
存储结点的数据信息存储该结点的双亲所在数组中的下标

双亲表示法示意图:

双亲表示法结构定义:

//结点结构
struct PTNode
{   int data;           //数据域int parent;         //双亲域
}PTNode;//树结构struct
{PTNode nodes[100];    //结点数组int r,n;                  //根结点位置和结点数
}

    双亲表示法的特点

  • 由于根结点是没有双亲的,约定根结点的位置位置域为-1.
  • 根据结点的parent指针很容易找到它的双亲结点。所用时间复杂度为O(1),直到parent为-1时,表示找到了树结点的根。
  • 缺点:如果要找到孩子结点,需要遍历整个结构才行

    2、孩子链表法

    把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空表,然后n个头指针又组成一个线性表,采用顺序存储结构,存放在一个一维数组中。

孩子表示法有两种结点结构:孩子链表的孩子结点表头数组的表头结点

  • 孩子链表的孩子结点的结点结构:
child(数据域)next(指针域)
存储某个结点在表头数组中的下标存储指向某结点的下一个孩子结点的指针

  • 孩子链表的双亲结点的结点结构:
data(数据域)firstchild(头指针域)
存储某个结点的数据信息存储该结点的孩子链表的头指针

孩子链表的结构示意图:

孩子链表表示法的结构定义:

//孩子结点
typedef struct CTNode
{   int child;struct CTNode *next;
}*ChildPtr; //双亲结点
typedef struct
{   ElemType data;ChildPtr firstchild;
}CTBox;//树结构
typedef struct
{   CTBox nodes[100];int r, n;              //根的位置和结点数
}CTree;

    特点:找孩子容易,找双亲困难。

    对于孩子表示法,查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。但是当要寻找某个结点的双亲时,就不是那么方便了。所以可以将双亲表示法和孩子表示法结合,形成双亲孩子表示法

树的双亲孩子链表的结构示意图:

树的双亲孩子表示法结构定义:

typedef struct CTNode{  // 孩子结点int child;  // 孩子结点的下标struct CTNode * next;  // 指向下一结点的指针
}*ChildPtr;typedef struct {  // 表头结构int data;  // 存放在数中的结点数据int parent;      // 存放双亲的下标ChildPtr firstchild;  // 指向第一个孩子的指针
}CTBox;typedef struct {  // 树结构CTBox nodes[100]; // 结点数组int r;  // 根的位置int n;  // 结点树
}CTree;


3、孩子兄弟表示法

    任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟存在也是唯一的。因此,设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。

孩子兄弟表示法的结点结构:

data(数据域)firstchild(指针域)rightsib(指针域)
存储结点的数据信息存储该结点的第一个孩子的存储地址存储该结点的右兄弟结点的存储地址

孩子兄弟表示法结构示意图:

孩子兄弟结点的结构定义:

/* 树的孩子兄弟表示法结构定义*/
typedef struct CSNode{int data;struct CSNode * firstchild;struct CSNode * rightsib;}CSNode, *CSTree;

相关文章:

树的基本概念和存储结构

一、树的基本概念 1、树的定义 树是n(n>0)个结点的有限集。当n 0时,称为空树。在任意一棵非空树中应满足: 1、有且仅有一个特定的称为根的结点。 2、当n>1时,其余节点可分为m(m>0&#xff09…...

深圳企业制作宣传片群体定位的重要性

相信众多企业都拍了自己公司的宣传片,尤其是在互联网高度发达的今天,宣传片可以说成为了我们企业对外宣传最主要的方式。看着企业多样式的宣传片种类,我们该如何评价一部宣传片的好坏呢?要知道宣传片的好坏是一个相对主观的问题&a…...

2309亚当arsd的11.1版本

原文 arsd11.1 Minigui 调整主题 在11.0中略有修改Minigui的主题,但它落后于11.1的计划.这是个重大更改,但这些更改很小. 新主题稍微变浅了默认组件的背景色和默认字体,这两者都主要影响Linux,因为窗口上的大多数组件一般使用本地主题. 更改状态栏 现有的状态栏类允许添加…...

spring---第七篇

系列文章目录 文章目录 系列文章目录一、什么是bean的自动装配,有哪些方式?一、什么是bean的自动装配,有哪些方式? 开启自动装配,只需要在xml配置文件中定义“autowire”属性。 <bean id="cutomer" class="com.xxx.xxx.Customer" autowire="…...

编程要搞明白的东西(二)

文章目录 一、简介二、面向对象编程基础2.1 面向对象编程概述2.2 类和对象2.2.1 类的定义和特点2.2.2 对象的创建和使用 2.3 封装、继承与多态的关系2.3.1 封装的概念和优势2.3.2 继承的概念和作用2.3.3 多态的概念和实现方式 三、封装3.1 封装的定义和原则3.2 封装的实现方法3…...

检索与毒害 —— 对抗人工智能供应链攻击

作者&#xff1a;DAVE ERICKSON 在这篇文章中&#xff0c;了解人工智能大语言模型的供应链漏洞&#xff0c;以及如何利用搜索引擎的人工智能检索技术来对抗人工智能的错误信息和故意篡改。 虽然对于人工智能研究人员来说可能是新鲜事&#xff0c;但供应链攻击对于网络安全世界…...

Linux 禁止用户或 IP通过 SSH 登录

Linux 禁止用户或 IP通过 SSH 登录 限制用户 SSH 登录 1.只允许指定用户进行登录(白名单): 在 /etc/ssh/sshd_config 配置文件中设置 AllowUsers 选项,(配置完成需要重启 SSHD 服务)格式如下: AllowUsers aliyun test@192.168.1.1 # 允许 aliyun 和从 19…...

14.Redis 主从复制

Redis 主从复制 redis 主从复制配置 redis 主从复制启动 redis 主从复制断开 redis 主从复制主从复制构特点主从复制的拓扑结构一主一从⼀主多从树状主从 主从复制原理数据同步psync 运行流程全量复制流程部分复制流程实时复制 关于从节点何时晋升成主节点总结 redis 主从复制 …...

常见的图像格式介绍:RAW、RGB、YUV

常见的图像格式有RAW、RGB、YUV这三大类 1. RAW raw图像指的是sensor输出的原始数据&#xff0c;常见的有8位、10位、12位之分&#xff0c;分别表示一个像素点所占的字节数为8bit、10bit、12bit。 raw数据常见的有四种Bayer模式&#xff1a;GRBG、RGGB、BGGR&#xff08;下图…...

极简极速-Bitset (bitmap)实现考勤打卡场景

文章目录 1. redis命令行操作bitmap2. RedisTemplate操作bitmap3. Java中的Bitset 1. redis命令行操作bitmap 2. RedisTemplate操作bitmap bitmap的常见业务场景主要有日活统计&#xff08;类似的月考勤&#xff09;、点赞、BloomFilter等&#xff0c;以用户mj考勤统计为例&am…...

word如何插入图片?3种常用的方法

word作为一款常用的办公软件&#xff0c;不仅可以处理文本内容&#xff0c;还能够轻松地插入图片以丰富文档内容。插入图片可以使文档更具吸引力、可读性和信息传达能力。本文将为您介绍word如何插入图片的3种方法&#xff0c;帮助您在文档中灵活、高效地添加图像元素。 word插…...

Python/C API - 模組,型別,Tuple,例外和引用計數

Python/C API - 模組&#xff0c;型別&#xff0c;Tuple&#xff0c;例外和引用計數 前言Python/C API - Common Object StructuresPyObjectPyMethodDefPyGetSetDef Python/C API - Module ObjectsPyModuleDefPyModule_CreatePyModule_AddObjectPyModule_AddObjectRef Initiali…...

人工智能轨道交通行业周刊-第59期(2023.9.4-9.10)

本期关键词&#xff1a;无锡智慧地铁、无人车站、钢轨打磨、混元大模型、开源大模型 1 整理涉及公众号名单 1.1 行业类 RT轨道交通人民铁道世界轨道交通资讯网铁路信号技术交流北京铁路轨道交通网上榜铁路视点ITS World轨道交通联盟VSTR铁路与城市轨道交通RailMetro轨道世界…...

ASP.NET Core 中的 MVC架构

MVC 架构 MVC架构把 App 按照逻辑分成三层&#xff1a; Controllers&#xff0c;接收 http request&#xff0c;配合 model&#xff0c;通过http response 返回 view&#xff0c;尽量不做别的事Models, 负责业务逻辑&#xff0c;App 的状态&#xff0c;以及数据处理Views&…...

C# PSO 粒子群优化算法 遗传算法 随机算法 求解复杂方程的最大、最小值

复杂方程可以自己定义&#xff0c;以下是看别人的题目&#xff0c;然后自己来做 以下是计算结果 private void GetMinResult(out double resultX1, out double min){double x1, result;Random random1 new Random(DateTime.Now.Millisecond* DateTime.Now.Second);min 99999…...

网络协议从入门到底层原理学习(三)—— 路由

网络协议从入门到底层原理学习&#xff08;三&#xff09;—— 路由 1、简介 路由&#xff08;routing&#xff09;是指分组从源到目的地时&#xff0c;决定端到端路径的网络范围的进程 在不同网段之间转发数据&#xff0c;需要有路由器的支持 默认情况下&#xff0c;路由器…...

2023/9/6 -- C++/QT

一、输出流对象cout 1> 该对象是来自于ostream的类对象&#xff0c;功能上类似于printf函数 2> 该类对象本质上调用成员函数插入运算符重载函数 3> 输出数据时&#xff0c;无需使用格式控制符&#xff1a;%d、%c、%s。。。&#xff0c;直接输出即可 4> 换行使用…...

python爬虫,多线程与生产者消费者模式

使用队列完成生产者消费者模式使用类创建多线程提高爬虫速度 https://sc.chinaz.com/tupian/index.html https://sc.chinaz.com/tupian/index_2.html https://sc.chinaz.com/tupian/index_3.html from threading import Thread from queue import Queue import requests from b…...

WordPress 提示“此站点遇到了致命错误”的解决方法

WordPress 提示“此站点遇到了致命错误”的解决方法 WordPress 网站博客提示“此站点遇到了致命错误。”如何解决&#xff1f;今天老唐不幸遇到了这个问题&#xff0c;搜了一下解决方法&#xff0c;发现致命错误原因有很多&#xff0c;所以需要先打开 WordPress 的 WP_DEBUG 功…...

Vue3,Typescript中引用组件路径无法找到模块报错

是这么个事&#xff0c;我在vue3新创建的项目里&#xff0c;写了个组件叫headerIndex.vue&#xff0c;放到app.vue中import就会报错 路径肯定没写错&#xff0c;找到了解决方法&#xff0c;但是也没想明白为什么 解决方法如下 在vite-env.d.ts文件中加入 declare module &qu…...

Llama-3.2V-11B-cot惊艳效果:多对象遮挡场景下的因果关系链推演

Llama-3.2V-11B-cot惊艳效果&#xff1a;多对象遮挡场景下的因果关系链推演 1. 视觉推理新标杆 在计算机视觉领域&#xff0c;多对象遮挡场景下的因果关系推演一直是个技术难题。传统方法往往只能识别可见部分&#xff0c;而无法理解遮挡背后的逻辑关系。Llama-3.2V-11B-cot的…...

如何安全高效地管理Cookie:Get cookies.txt LOCALLY本地处理终极实践指南

如何安全高效地管理Cookie&#xff1a;Get cookies.txt LOCALLY本地处理终极实践指南 【免费下载链接】Get-cookies.txt-LOCALLY Get cookies.txt, NEVER send information outside. 项目地址: https://gitcode.com/gh_mirrors/ge/Get-cookies.txt-LOCALLY 在数字时代&a…...

第 11 章 追踪与性能分析(OpenOCD)

第 11 章 追踪与性能分析 导读:现代 ARM 处理器内置了丰富的 CoreSight 追踪基础设施,包括 ETM 指令追踪、ITM/DWT 数据追踪、SWO/TPIU 追踪输出以及 SEGGER RTT 高速日志。本章将系统介绍如何在 OpenOCD 中配置和使用这些追踪功能,帮助开发者在不侵入目标程序的前提下,完成…...

4个突破式步骤:哔咔漫画下载解决方案

4个突破式步骤&#xff1a;哔咔漫画下载解决方案 【免费下载链接】picacomic-downloader 哔咔漫画 picacomic pica漫画 bika漫画 PicACG 多线程下载器&#xff0c;带图形界面 带收藏夹&#xff0c;已打包exe 下载速度飞快 项目地址: https://gitcode.com/gh_mirrors/pi/picac…...

AI 创作者指南:04.AI写作:从草稿到润色的全流程协作

第4篇AI写作:从草稿到润色的全流程协作 第一部分创意引擎学完,你现在灵感满池、选题稳稳、观点锋利,是不是已经跃跃欲试想动笔了?😊 来,正式进入第二部分:AI作为写作与表达助手! 今天第4篇——AI写作:从草稿到润色的全流程协作。 咱们还是老朋友喝茶模式:AI不是让你…...

Python办公自动化:用PyMuPDF+pdfplumber一键提取PDF文字/图片/表格(附完整代码)

Python办公自动化实战&#xff1a;PyMuPDF与pdfplumber高效提取PDF三要素 每天面对堆积如山的PDF文档&#xff0c;行政和财务人员最头疼的莫过于手动复制粘贴文字、截图保存图片、重新绘制表格。我曾见过一位财务同事为了处理200份供应商报价单&#xff0c;连续加班一周手工录入…...

从DEM到决策:如何用QGIS分析河北地形,为生态保护与项目选址提供依据?

从DEM到决策&#xff1a;QGIS地形分析在河北生态保护与项目选址中的实战指南 河北省复杂的地形地貌为各类生态保护和工程项目带来了独特挑战。作为华北地区生态屏障与经济发展的重要区域&#xff0c;如何科学评估地形特征直接影响着规划决策的质量。本文将带您用QGIS这一开源工…...

如何用LuckyLilliaBot在5分钟内构建QQ机器人:OneBot 11协议完全指南

如何用LuckyLilliaBot在5分钟内构建QQ机器人&#xff1a;OneBot 11协议完全指南 【免费下载链接】LuckyLilliaBot NTQQ的OneBot API插件 项目地址: https://gitcode.com/gh_mirrors/li/LuckyLilliaBot 想要快速搭建一个功能强大的QQ机器人吗&#xff1f;LuckyLilliaBot为…...

别再只用Unity做游戏了!用Game4Automation PRO插件,手把手教你搭建一条虚拟生产线(附PLC连接避坑指南)

跨界开发者的工业仿真指南&#xff1a;用Unity打造虚拟生产线全流程 当游戏开发者遇上工业自动化&#xff0c;会碰撞出怎样的火花&#xff1f;Unity作为全球最流行的游戏引擎之一&#xff0c;早已突破了娱乐产业的边界。今天&#xff0c;我们将探索如何利用Game4Automation PRO…...

从时频分析到信号净化:小波变换的降噪实战指南

1. 小波变换基础&#xff1a;从傅里叶到时频分析 第一次接触小波变换时&#xff0c;我和大多数工程师一样&#xff0c;脑子里全是傅里叶变换的影子。记得当时处理一组振动传感器数据&#xff0c;傅里叶变换告诉我信号里存在30Hz和50Hz的成分&#xff0c;但就是找不到这些频率具…...