侵权投诉

树的递归结构和树的存储结构分析

39度创意研究所 2020-10-16 14:33 次阅读

树的递归结构

从一张图中解释什么是树 这张图,主要讲解关于cart这个单词的所有的可能组合,按照常理,需要先考虑三个字母的排列,然后对三个字母进行拆分,直到最后一个节点,这个过程就类似于树 到底什么是树 什么是树 树是节点集合(A tree is a collection of nodes), 集合:集合是允许一个元素都没有的集合,称之为空集。 首先,集合是允许一个元素都没有的集合,称之为空集,那么书是不是也允许一个节点都没有的呢,是的,一个节点都没有的树,称之为空树,如果不是空的,则会存在根节点r和零个或更多非空子树,T1,T2.。。Tk,他们的根由来自r的有向连接,什么叫有向边,大致可以理解为箭头。用图的关系说明树的内部关系 根节点(root)一棵树只有一个跟节点,所有的节点都在该节点的下面,尝试把图倒过来看,可以看成一个我们日常见到的数的根部,在这里显然字母A就是这颗树的根节点。 子节点,父节点,一个节点,它对应的下面有连这的节点,那么被连着的节点就是这个节点的子节点,也叫做孩子,那么这个节点叫做被连接的节点的父亲,看图,B被A连这,所以B是A的一个孩子,同理,CDE等等这一行都是A的孩子,同时F,它连这K L M 同时被A连这,那么F是A的一个孩子,同时又是K L M 的父亲。 树叶:树叶就是那些没有孩子的节点,比如B,C,D等等,例如下图的绿色部分。 兄弟: 按照我们的理解,同一个父母生的当然是兄妹,如下图所示,颜色相同的都是兄妹 路径 我们同样可以定义从父亲到他孩子的路径,下面的路径,我们就取上图的一部分,一个子树,作为例子 比如,A->O的路径为A->E->J->O它的长度为3,实际为它的边数,图中红色的部分。 节点的深度:节点的深度指的是节点到树根的长度,看下图,我们可以轻易的知道,j节点的深度为2,可以理解为 A-> E -> J 边长为2.显然,此时根节点的深度为0. 节点的高度:高度是从节点到叶子的最长路径,比如节点F的高度为1,显然所有叶子节点高度为0. 树的高度,树的高度是跟的高度,显然在这图中,树的高度为3,A->O 树的特点 按照正常的逻辑,一个人不能同时有两个父亲,所以树也一样,下图的两个就解释了这个问题 一颗正常的树,它的树枝是不会长成一个圆的,所以,树中,是不可能出现环形的。图中,红色箭头构成了一个环,所以都不是一颗树。 树的存储结构 树的存储结构有三种,分别为,双亲表示法,孩子表示法,孩子兄弟表示法。 双亲表示法 假设一组连续空间保存着树的特点,同时在每个节点中,附带一个指示器表示双亲节点中链表的为位置,也就是说,每个节点除了知道自己是谁以外,还知道他的双亲在哪里。 其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。 //树的双亲表示法结点结构定义 #define MAX_TRUE_SIZE 100 typedef int TElemType //树结点的数据类型 //结点结构 typedef struct PTNode { TElemType data; //结点数据 int parent; //双亲位置 }PTNode //树结构 typedef struct { PTNode nodes[MAX_TRUE_SIZE]; //结点数组 int r,n //根的位置和结点数 }PTree 有了这样的数据结构就可以来实现双亲表示法。由于根结点是没有双亲的,所以我们约定根结点的位置域设置为-1,这也就意味着,我们所有的结点都存有他双亲的位置。如图1-2中的树结构和表1-3中的树双亲表示。 这样的存储结构,我们可以根据结点的parent’指针很容易找到他的双亲结点,时间复杂度为O(1),直到parent为-1时,表示找到了树结点的根 孩子表示法 换一种完全不同的考虑方法,由于树中每个结点可能有多棵子树,可以考虑用多重链表。每个结点有多个指针域,其中每个指针指向一颗子树的根结点,我们把这种方法叫做多重链表的表示方法。不过,树的每个结点的度,也就是他的孩子个数是不同的,所以设计两种方法: 方案一 指针域的个数就等于树的度,树的度就是树各个结点度的最大值。其结构如图 其中data是数据域,child1到childd是指针域,用来指向该结点的孩子结点。对于图1-1来说,树的度是3,所以我们指针域个数就是3, 方案二 每个结点指针域的个数等于该结点的度,我们专门取一个位置来存储结点指针的个数。 data为指针域,degree为度域,也就是存储该结点的孩子结点的个数 这就是我们要说的孩子表示法,把每个结点的孩子都排列起来,以单链表为存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组, 为此,设计两种存储结构,一个是孩子链表的孩子结点, child是数据域,用来存储某个结点在表头数组中的下标。next是指针域,用来存储指向结点的下一个孩子结点的指针。另一个是表头数组的表头结点。 data是数据域,存储某结点的数据信息,firstchild是头指针域,存储该结点的孩子链表的头指针。 //树的孩子表示法结构定义 #define MAX_TRUE_SIZE 100 typedef struct CTNode //孩子结点 { int child; struct CTNode *next; }*ChildPtr; //表头结构 typedef struct { TElemType data; ChildPtr firstchild; }CTBox; //树结构 typedef struct { CTBox nodes[MAX_TRUE_SIZE]; //结点数组 int r,n; //根的位置和结点数 }CTree 把把双亲表示法和孩子表示法综合一下表示如下 这种表示法叫做双亲孩子表示法,应该算是孩子表示法的改进。 孩子兄弟表示法 任一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此。我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。 data是数据域,fitstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储位置。 //孩子兄弟表示法结构定义 typedef struct CSDNode { TElemType data; struct CSNode *firstchild,*rightsib; }CSNode,*CSTree; 这种方法的示意图如下所示 这种表示法,给查找某个结点的某个孩子带来了方便,只需要通过firstchild找到此结点的长子,然后在通过长子结点的rightsib找到它的二弟,接着一直找下去,直到找到具体的孩子。
编辑:hfy
收藏 人收藏
分享:

评论

相关推荐

什么是“红黑树”看了就知道

今天我们要说的红黑树就是就是一棵非严格均衡的二叉树,均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质,插入、搜...
发表于 10-27 17:00 30次 阅读
什么是“红黑树”看了就知道

如何使用邻接树的数据结构提高遗传算法的挖掘效率

为提高复杂网络中遗传算法的子图挖掘效率,在邻接表的链式结构基础上加入双树状结构,作为一种新型数据结构....
发表于 10-23 11:47 21次 阅读
如何使用邻接树的数据结构提高遗传算法的挖掘效率

深度解析Linux网络路径及sk_buff struct 数据结构

理解 Linux 网络栈(1):Linux 网络协议栈简单总结 本系列文章总结 Linux 网络栈,....
的头像 39度创意研究所 发表于 10-22 15:04 372次 阅读
深度解析Linux网络路径及sk_buff struct 数据结构

数据结构中堆栈出栈序列问题解析

这是工作中遇到的小问题。 数据结构中有一种数据类型堆栈,该结构中的数据项有如下特点: 除了最前面和最....
的头像 39度创意研究所 发表于 10-19 15:46 167次 阅读
数据结构中堆栈出栈序列问题解析

Git 底层知识:详细分析对象查询流程和算法

本文将系统分享 Git 底层知识:对象生命周期变化,底层数据结构,数据包文件结构,数据包文件索引,以....
的头像 39度创意研究所 发表于 10-13 15:29 534次 阅读
Git 底层知识:详细分析对象查询流程和算法

一文了解go hashmap(数据结构、实现原理、读写操作)

这是看着别人的文章结合源码来整理的自己一套理解 理解 Golang 哈希表 Map 的原理​drav....
的头像 39度创意研究所 发表于 09-30 16:19 279次 阅读
一文了解go hashmap(数据结构、实现原理、读写操作)

什么是数据结构 数据及数据之间的关系分析

数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一个目的,即为了方便后期对数据....
的头像 39度创意研究所 发表于 09-30 16:14 305次 阅读
什么是数据结构 数据及数据之间的关系分析

一堂数据结构和算法的基础课

递归空间 O(logn):递归是一个比较特殊的场景。虽然递归代码中并没有显式的声明变量或集合,但是计....
的头像 算法与数据结构 发表于 09-03 10:28 289次 阅读
一堂数据结构和算法的基础课

《程序设计与数据结构》【完整资料】分享!

       在程序设计过程中,很多开发人员在没有全局思维的把控,科学、系统的组织以及严密的测试与部署下,...
发表于 08-31 16:20 187次 阅读
《程序设计与数据结构》【完整资料】分享!

一文读懂缓存淘汰算法:LFU 算法

从实现难度上来说,LFU 算法的难度大于 LRU 算法,因为 LRU 算法相当于把数据按照时间排序,....
的头像 算法与数据结构 发表于 08-25 17:37 490次 阅读
一文读懂缓存淘汰算法:LFU 算法

C语言教程之数据类型的学习课件免费下载

一个程序应包括两个方面的内容: 1. 数据的描述(数据结构) 2. 操作的描述(即操作步骤、算法....
发表于 08-17 16:38 74次 阅读
C语言教程之数据类型的学习课件免费下载

page struct的三种存放方式

随着内存容量的增加,相对应的page struct也就增加。而这部分内存和其他的内存略有不同,因为这....
的头像 Linuxer 发表于 08-03 16:33 374次 阅读
page struct的三种存放方式

光纤通道到以太网存储结构解析

行业专家认为,以太网存储结构(ESF)是下一代存储网络的理想选择,因为其具有卓越的性能、qy88千赢国际娱乐和效率。
发表于 07-21 15:59 128次 阅读
光纤通道到以太网存储结构解析

Python参考手册第4版PDF电子书免费下载

本书是Python编程语言的杰出参考手册,书中详尽讲解了Python核心和Python库中重要的部分....
发表于 07-17 08:00 120次 阅读
Python参考手册第4版PDF电子书免费下载

数据结构C语言版习题集答案合集免费下载

1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解:数据....
发表于 06-23 08:00 80次 阅读
数据结构C语言版习题集答案合集免费下载

Ruby编程语言PDF电子书免费下载

《Ruby编程语言》详细介绍了Ruby 1.8和1.9版本各方面的内容。在对Ruby进行了简要的综述....
发表于 06-12 08:00 47次 阅读
Ruby编程语言PDF电子书免费下载

请问大神这种数据结构一般如何解析额?

请问大神,这种数据结构一般如何解析额。。 不太懂。。 ...
发表于 06-10 09:27 41次 阅读
请问大神这种数据结构一般如何解析额?

栈是一种LIFO后入先出的什么数据结构?

栈在哪里定义大小,定多大合适?这可能很多刚接触单片机开发的同学不是太清楚,下面就将比较常见的IAR开....
的头像 lhl545545 发表于 06-09 09:26 1004次 阅读
栈是一种LIFO后入先出的什么数据结构?

面向对象与C++程序设计实验之熟悉开发环境和简单程序设计的资料说明

练习string类的使用。掌握string类的insert,erase,find,replace等常....
发表于 06-09 08:00 75次 阅读
面向对象与C++程序设计实验之熟悉开发环境和简单程序设计的资料说明

为什么Linux如此流行?

Linux是免费的。你不需要为使用Linux而付费,你可以自由查看,编辑和分发源代码。当你购买装有W....
的头像 电子工程技术 发表于 06-08 16:31 573次 阅读
为什么Linux如此流行?

python算法图解PDF电子书免费下载

本书示例丰富,图文并茂,以简明易懂的方式阐释了算法,旨在帮助程序员在日常项目中更好地利用算法为软件开....
发表于 06-04 08:00 22次 阅读
python算法图解PDF电子书免费下载

你要的算法和数据结构的学习路线来了!

大公司更注重基础扎实,发展潜力,而小公司希望你立刻、马上为他干活,通常是没什么技术含量的活。小公司喜....
的头像 算法与数据结构 发表于 06-03 17:21 811次 阅读
你要的算法和数据结构的学习路线来了!

数据结构C语言题集电子书免费下载

本文档的主要内容详细介绍的是数据结构C语言题集电子书免费下载。
发表于 06-01 08:00 115次 阅读
数据结构C语言题集电子书免费下载

数据结构的基本概念是什么

数据结构之基本概念
发表于 05-27 08:29 32次 阅读
数据结构的基本概念是什么

请问C怎么提高啊??

C怎么提高啊,指针结构体,数据结构完全明白,有什么实战练习吗 ? 要打好什么基础?如何能通过做方案来提高自己啊?...
发表于 05-24 23:58 32次 阅读
请问C怎么提高啊??

DeBug太枯燥?让VS Code画个图

写代码,难免会遇到各种神奇的问题,代码短我们在脑海中「运行」一遍也就差不多能找出原因。但代码要是比较....
的头像 人工qy88千赢国际娱乐爱好者社区 发表于 05-12 09:19 1291次 阅读
DeBug太枯燥?让VS Code画个图

数据结构C语言版电子书免费下载

本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的各....
发表于 05-12 08:00 197次 阅读
数据结构C语言版电子书免费下载

程序设计与数据结构电子书免费下载

在学习程序设计时,很多初学者常常会陷入这样的误区,他们总将阻碍个人成长的原因归结为缺少机会。其实问题....
发表于 05-10 08:00 93次 阅读
程序设计与数据结构电子书免费下载

常见的数据结构

数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。 一、什么是...
发表于 05-10 07:58 291次 阅读
常见的数据结构

我的第一本算法书电子书免费下载

本书采用大量图片,通过详细的分步讲解,以直观、易懂的方式展现了 7 个数据结构和 26 个基础算法的....
发表于 05-08 08:00 129次 阅读
我的第一本算法书电子书免费下载

一个数据结构-线段树

对于求区间和的问题,前缀和数组 是一个不错的选择,构建好前缀和数组后,求一个区间和的话只要前后一减就....
的头像 算法与数据结构 发表于 05-06 11:02 1003次 阅读
一个数据结构-线段树

一道LeetCode的多种解法

对于这道题目,因为我们要求的是子串的长度,因此我们可以考虑在栈中保存 index,这样子我们不仅可以....
的头像 算法与数据结构 发表于 05-06 10:39 938次 阅读
一道LeetCode的多种解法

Linux内核快速处理路径尽量多用kmem_cache而慎用kmalloc

仅仅为了测试是否会宕机,所以我的所有的数据结构的hash值均是一样的,这样插入200个项的话,它们会....
的头像 Linuxer 发表于 04-30 15:35 1186次 阅读
Linux内核快速处理路径尽量多用kmem_cache而慎用kmalloc

企业如何解决数据科学家短缺详细方法什么

 随着企业以数据为中心的文化,以做出决策和规划,数据科学家对全球企业的重要性日益增加。但是企业无法足....
的头像 Wildesbeast 发表于 04-18 10:31 1382次 阅读
企业如何解决数据科学家短缺详细方法什么

是什么使神经网络变成图神经网络?

这是一种很灵活的数据结构,它囊括了很多其他的数据结构。例如,如果没有边,那么它就会变成一个集合;如果....
的头像 倩倩 发表于 04-17 10:18 672次 阅读
是什么使神经网络变成图神经网络?

哈希表是什么?为什么需要使用哈希表

我们在这篇文章将要学习最有用的数据结构之一—哈希表,哈希表的英文叫 Hash Table,也可以称为....
的头像 Wildesbeast 发表于 04-06 13:50 2035次 阅读
哈希表是什么?为什么需要使用哈希表

这些程序员必须知道的数据结构你知道多少

数据结构是一种特殊的组织和存储数据的方式,可以使我们可以更高效地对存储的数据执行操作。数据结构在计算....
的头像 Wildesbeast 发表于 04-06 12:09 789次 阅读
这些程序员必须知道的数据结构你知道多少

程序设计与数据结构PDF电子书免费下载

1. C语言学习中的痛点:针对当前工程师在C语言学习中的痛点,如指针函数与函数指针,如何灵活应用结构....
发表于 03-24 08:00 187次 阅读
程序设计与数据结构PDF电子书免费下载

环形缓冲区的实现原理

在通信程序中,经常使用环形缓冲区作为数据结构来存放通信中发送和接收的数据。环形缓冲区是一个先进先出的....
的头像 西西 发表于 03-22 10:03 1375次 阅读
环形缓冲区的实现原理

C51的数据结构详细课件详细说明

 在C51语言中,除了整型(int)、浮点型(float)、字符型(char)、无值型(void)几....
发表于 03-17 16:41 110次 阅读
C51的数据结构详细课件详细说明

unix基本概念汇总

unix是一种抢占式多任务系统,我们常说的多人多任务系统,就是一台主机可以允许多个人多个任务共同运行....
发表于 03-11 16:19 69次 阅读
unix基本概念汇总

数据结构有哪些知识重点

不管你现在是不是需要用到数据结构的相关知识,在工作的过程中理解、掌握好数据结构,对现在的工作和以后的....
发表于 03-06 10:05 194次 阅读
数据结构有哪些知识重点

浅谈STM32CubeMX的理解心得与运用

用心去学习STM32CubeMX,你会有不一样的收获
的头像 黄工的嵌入式技术圈 发表于 03-03 14:17 5433次 阅读
浅谈STM32CubeMX的理解心得与运用

数据结构与算法知识点有哪些?

数据结构与算法的知识点有哪些?
的头像 黄工的嵌入式技术圈 发表于 01-10 15:22 2517次 阅读
数据结构与算法知识点有哪些?

数据结构的简介和线性表及栈队列和数组的详细说明

两项基本任务:数据表示,数据处理 软件系统生存期:软件计划,需求分析,软件设计,软件编码,软件测试....
发表于 01-06 08:00 156次 阅读
数据结构的简介和线性表及栈队列和数组的详细说明

仿人机器人PDF电子书免费下载

《仿人机器人》是2007年清华大学出版社出版的图书,作者是梶田秀司。本书内容包括仿人机器人学的运动学....
发表于 01-03 18:03 542次 阅读
仿人机器人PDF电子书免费下载

数据结构的代码和工程文件合集免费下载

本文档的主要内容详细介绍的是数据结构的C语言代码和工程文件合集免费下载包括了:按元素类型将单链表改为....
发表于 01-02 08:00 174次 阅读
数据结构的代码和工程文件合集免费下载

Python Cookbook中文第三版PDF电子书免费下载

《Python Cookbook(第3版)中文版》介绍了Python应用在各个领域中的一些使用技巧和....
发表于 11-15 08:00 264次 阅读
Python Cookbook中文第三版PDF电子书免费下载

使用索引对子图查询技术研究有怎么样的进展了

图作为表示实体间的数据结构,在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛....
发表于 11-13 17:43 144次 阅读
使用索引对子图查询技术研究有怎么样的进展了

数据结构C语言版PDF电子书免费下载

《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参....
发表于 11-13 15:16 234次 阅读
数据结构C语言版PDF电子书免费下载

为什么Labview程序增加一部分,波形不显示了

如图程序,去掉红框,波形采集正常,加上红框部分,波形就不采集不显示了,这个可能是什么原因呢,谢谢。 ...
发表于 10-22 20:21 457次 阅读
为什么Labview程序增加一部分,波形不显示了

脚本语言的概述和与其他编程语言的关系及特点以及程序举例的详细说明

脚本语言,脚本语言或扩建的语言,又叫动态语言。是一种编程语言控制软件应用程序。脚本通常以文本(如AS....
发表于 10-15 15:26 266次 阅读
脚本语言的概述和与其他编程语言的关系及特点以及程序举例的详细说明

数据结构与算法分析—C语言描述

《数据结构与算法分析:C语言描述》曾被评为20世纪顶尖的30部计算机著作之一,作者在数据结构和算法分....
发表于 10-14 08:00 300次 阅读
数据结构与算法分析—C语言描述

什么是数据结构?数据结构的详细资料概述

随着计算机软、硬件的发展,计算机的应用范围在不断扩大,计算机所处理的数据的数量也在不断扩大,计算机所....
发表于 10-14 08:00 279次 阅读
什么是数据结构?数据结构的详细资料概述

数据结构C语言版辅导教程PDF电子书免费下载

《数据结构》是一门计算机专业基础课,各类计算机考试都禁不住要考它,专升本考试自然也不例外。我给学生辅....
发表于 09-19 08:00 268次 阅读
数据结构C语言版辅导教程PDF电子书免费下载

求推荐一本好用的数据结构的书!

RT
发表于 08-27 22:18 376次 阅读
求推荐一本好用的数据结构的书!

为什么嵌入式C语言中的size不等于所有成员size之和

结构体在C语言程序开发中,是不可或缺的语法。不过,相信不少C语言初学者遇到过这样的问题:为什么结构体....
发表于 08-19 11:50 558次 阅读
为什么嵌入式C语言中的size不等于所有成员size之和

java数据结构有哪些

List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(....
的头像 陈翠 发表于 08-15 16:27 1254次 阅读
java数据结构有哪些

请问数据结构对弄单片机重要吗?

数据结构的知识对弄单片机的人重不重要啊 大家都学得怎么样啊?...
发表于 04-12 02:43 583次 阅读
请问数据结构对弄单片机重要吗?

数据结构试题库,含答案

学习IT技术最多的就是练习题了,让理论与实践相结合,这样学习才是有效的,下面是一美女学霸,在一次次测试中,总结的常见的数...
发表于 03-07 16:19 1672次 阅读
数据结构试题库,含答案