请选择 进入手机版 | 继续访问电脑版

[python] Python 数据布局 之树的概念详解

[复制链接]
查看149 | 回复16 | 2021-9-13 12:23:14 | 显示全部楼层 |阅读模式

数据布局 树简介

一、树简介

Python 数据布局
之树的概念详解

树(Tree)是一种抽象的数据布局 ,是一个数据的集合,集合中的数据构成 了一个树状布局 。比方 上图,看起来像一棵倒挂的树,根朝上叶朝下。

树是由n(n>=0)个节点构成 的具有层次关系的数据集合。当 n=0 时,树中没有节点,称为空树。当 n>0 时,有且仅有一个节点被称为根节点(Root),假如 n=1 ,树只有根节点一个节点。假如 n>1 ,除根节点外,将别的 的节点分成m(m>0)个互不相交的数据集合,这 m 个集合每一个都要满足 树的布局 (有且仅有一个根节点),并且这 m 棵树都“挂”在根节点上,云云 递归下去,直到全部 节点都“挂”到这棵树上。此中 ,这 m 个集合构成的 m 棵树都被称为根节点的子树。

在明白 树的布局 和定义时,必要 运用到递归的头脑 。以下图为例,树的节点集合为 {A,B,C,D,E,F,G,H} ,n=8,根节点为 A ,除根节点 A 外,别的 节点构成 了两个(m=2)集合(m1和m2),m1集合为 {B,D,E} ,m2集合为 {C,F,G,H} 。在m1中,B 为m1的根节点,除 B 以外,别的 节点构成 两个集合,集合 {D} 和集合 {E} ,{D} 和 {E} 都只有一个节点,分别构成一棵只有一个节点的树,它们“挂”在m1的根节点 B 上,是 B 的子树,m1构成一棵树,“挂”在根节点 A 上,m1是 A 的子树。同理,在m2中,C 为m2根节点,别的 节点构成 三个集合 {F} 、{G} 和 {H} ......

Python 数据布局
之树的概念详解

二、树的术语

要明白 树这种数据布局 ,必须先明白 一些常用的术语。

树由一个一个的节点构成 ,节点是构成复杂数据布局 的基本构成 单位。

1. 子节点:又称为孩子节点,一个节点所包含的子树的根节点被称为该节点的子节点。如下图中,节点 B 有两棵子树,这两棵子树的根节点为 D 和 E ,以是 D 和 E 都是 B 的子节点。

2. 父节点:又称为父亲节点,假如 一个节点有子节点,则这个节点被称为其子节点的父节点。如下图中,节点 B 有两个子节点 D 和 E ,则 B 是 D 的父节点,也是 E 的父节点。

3. 兄弟节点:具有类似 父节点的节点互称为兄弟节点。下图中的 D 和 E 就互为兄弟节点。

4. 堂兄弟节点:假如 树的两个节点深度类似 ,但父节点不同,则它们互为堂兄弟节点。下图中的 D与F,D与G,D与H,D与I 都是堂兄弟节点关系。

Python 数据布局
之树的概念详解

5. 节点的先人 :从根节点开始,依次找到某节点所经路径上的全部 节点都称为该节点的先人 。如下图中,节点 J 的先人 节点为 A,B,D 。

6. 节点的子孙:以某节点为根的子树中,任一节点都称为该节点的子孙。如下图中,节点 C 的子孙有 F,G,H,I,M,N,O 。

Python 数据布局
之树的概念详解

7. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推。如下图中,根节点 A 在第1层,节点 M 在第4层。

8. 节点的深度:一个节点所处的层次称为该节点的深度。如下图中,根节点 A 的深度为1,节点 M 的深度为4 。(上面表明 堂兄弟节点时有效 到节点的深度,现在 可以回去看看)

9. 树的深度:又称为树的高度,一棵树中,最大的节点深度称为树的深度。如下图中的树深度为4。

关于深度和高度,有两种定义方式,一种是将根节点的深度定义为0,另一种是将根节点的深度定义为1。但不管怎样,每个深度为 k 的节点的子节点的深度都为 k+1 ,这是不变的。

Python 数据布局
之树的概念详解

10. 节点的度:一个节点含有的子树(或子节点)的个数称为该节点的度。如下图中, 根节点 A 的度为2,节点 C 的度为4,节点 I 的度为1,节点 O 的度为 0 。

11. 树的度:一棵树中,最大的节点度称为树的度。如下图中,最大的节点度是4,则树的度为4。

12. 叶节点:又称为终端节点,度为零的节点被称为叶节点。如下图中,节点 F,H,J,K,L,M,N,O 都是叶节点。

Python 数据布局
之树的概念详解

13. 丛林 :由m(m>=0)棵互不相交的树构成的集合称为丛林 。丛林 是从树延伸出来的术语,丛林 里的树肯定 是互不相交的。

Python 数据布局
之树的概念详解

三、树的特点

通过对树的定义和树的术语举行 先容 ,基本可以明白 树这种数据布局 了,总结起来,树有以下特点。

1. 假如 树的节点数 n>0,根节点是唯一的,不大概 存在多个根节点。

2. 没有父节点的节点称为根节点。根节点是没有父节点的。

3. 每一个非根节点有且只有一个父节点。除了根节点外,其他全部 节点都有父节点,并且同一个节点只有一个父节点,不大概 有多个。

4. 每个节点有零个或多个子节点。

5. 除了根节点外,子节点可以分为多个不相交的子树。这些子树肯定 是互不相交的。

6. 每个深度为 k 的节点的子节点的深度都为 k+1 。

四、树的分类

全部 树都满足 以上的特点,除此之外,一些树还具有专有的特点。根据专有的特点,可以对树举行 分类。

1. 无序树:也称为自由树,树中存在一个节点,节点的子节点之间没有次序 关系。如下图中,右边的树是无序树,从树中取一个节点 D ,D 的子节点是节点 J 和节点 E,它们是没有次序 关系的,以是 这是一棵无序树。

2. 有序树:树中恣意 节点的子节点之间有次序 关系。如下图中,左边的树是有序树,从树中恣意 取一个节点 C,C 的子节点是 F,G,H ,它们是有次序 关系的(字母次序 ),以是 这是一棵有序树。

图中的有序和无序以字母次序 作为案例,实际 应用中的“有序”并不限于字母次序 、数字次序 等,实际 的有序紧张 是指“不能互换”。

Python 数据布局
之树的概念详解

无序树的节点之间没有次序 关系,节点之间的关系不能通过代码来模仿 和控制,以是 基本没有实际 的应用场景。

利用 树这种数据布局 ,基本都是利用 有序树,对于有序树,又可以分为以下几种。

1. 二叉树:每个节点最多含有两个子树的树称为二叉树,如下图。二叉树是最常用的树布局 ,可以对二叉树进一步细分(别的 的文章再细致 研究)。

Python 数据布局
之树的概念详解

2. 霍夫曼树:又称为最优二叉树,是一种带权路径最短的二叉树。

3. B树:是一种对读写操作举行 优化的自均衡 的二叉查找树,可以或许 保持数据有序,拥有多余两个子树。

可以看到,后面的两种树都是在二叉树的基础上,根据特别 的场景独立出来的,光看定义很难懂 白 ,以是 以后的文章再研究。

到此这篇关于数据布局 之树的概念详解的文章就先容 到这了,更多干系 数据布局 之树的概念内容请搜索 脚本之家从前 的文章或继续欣赏 下面的干系 文章盼望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar penguinzhuyun | 2021-9-13 20:06:19 | 显示全部楼层
admin楼主很有经验啊!
回复

使用道具 举报

avatar 绣绣仙女酌 | 2021-9-13 20:49:32 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,运动刷步数还是免费刷的,QQ和微信都可以刷,特别好用。访问地址:http://yd.mxswl.com 猫先森网络
回复

使用道具 举报

avatar 失室创 | 2021-9-18 08:10:47 | 显示全部楼层
求加金币!
回复

使用道具 举报

avatar 唰唰冷呵映 | 2021-9-20 08:45:22 | 显示全部楼层
好好学习admin楼主的帖子!
回复

使用道具 举报

avatar 哲911 | 2021-9-21 05:07:47 | 显示全部楼层
收藏了,改天让朋友看看!
回复

使用道具 举报

avatar 不好吃荤漳 | 2021-9-30 22:45:54 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,他卖的服务器是永久的,我们的网站用 服务器都是在这家买的,你可以去试试。访问地址:http://fwq.mxswl.com
回复

使用道具 举报

avatar 123457732 | 2021-9-30 22:45:57 | 显示全部楼层
admin楼主看起来很有学问!
回复

使用道具 举报

avatar 海沙心诖 | 2021-10-6 07:36:00 | 显示全部楼层
刚看见一个妹子,很漂亮!
回复

使用道具 举报

avatar lj1282502016 | 2021-10-13 13:33:46 | 显示全部楼层
经典!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则