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} ......

二、树的术语

要理解树这种数据结构，必须先理解一些常用的术语。

树由一个一个的节点组成，节点是构成复杂数据结构的基本组成单位。

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 都是堂兄弟节点关系。

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

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

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

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

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

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

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

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

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

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

三、树的特点

通过对树的定义和树的术语进行介绍，基本可以理解树这种数据结构了，总结起来，树有以下特点。

1. 如果树的节点数 n>0，根节点是唯一的，不可能存在多个根节点。

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

3. 每一个非根节点有且只有一个父节点。除了根节点外，其他所有节点都有父节点，并且同一个节点只有一个父节点，不可能有多个。

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

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

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

四、树的分类

所有树都满足以上的特点，除此之外，一些树还具有专有的特点。根据专有的特点，可以对树进行分类。

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

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

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

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

使用树这种数据结构，基本都是使用有序树，对于有序树，又可以分为以下几种。

1. 二叉树：每个节点最多含有两个子树的树称为二叉树，如下图。二叉树是最常用的树结构，可以对二叉树进一步细分(另外的文章再仔细研究)。

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

3. B树：是一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

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

到此这篇关于数据结构之树的概念详解的文章就介绍到这了,更多相关数据结构之树的概念内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Python从入门到实战之数据结构篇

    Python从入门到实战之数据结构篇

    前言 我是栗子--专为小白准备<Python从入门到实战>内容. 这不是上一期刚讲完循环判断,还给大家出了很多新手的题目,边学边练习才有效果嘛. 时隔几天,大家都吼完了叭~实在没写完的慢慢复习,我更新文章也挺慢的!哈哈哈哈 今天想一想:要学数据结构啦~ 一.Python有那几种数据结构? Python 有四种数据结构,分别是:列表.字典.元组,集合.每种数据结构都有自己的特点,并且都有着独到的用处.为了避免过早地陷入细枝末节. 我们先从整体上来认识一下这四种数据结构:从最容易识别的特征上来说,

  • python数据结构的排序算法

    python数据结构的排序算法

    目录 十大经典的排序算法 一.交换排序 1.冒泡排序(前后比较-交换) 2.快速排序(选取一个基准值,小数在左大数在右) 二.插入排序 1.简单插入排序(逐个插入到前面的有序数中) 2.希尔排序(从大范围到小范围进行比较-交换) 三.选择排序 1.简单选择排序(选择最小的数据放在前面) 2.堆排序(利用最大堆和最小堆的特性) 四.归并排序 五.其他排序 1.计数排序(字典计数-还原) 2.桶排序(链表) 3.基数排序 十大经典的排序算法 数据结构中的十大经典算法:冒泡排序.快速排序.简单插入排序

  • Python入门_浅谈数据结构的4种基本类型

    数据结构:通俗点说,就是储存大量数据的容器.这里主要介绍Python的4种基本数据结构:列表.字典.元组.集合. 格式如下: 列表:list = [val1,val2,val3,val4],用中括号: 字典:dict = {key1:val1,key2:val2},大括号,且每个元素是带有冒号的key与val的对应关系组: 元组:tuple = (val1,val2,val3,val4),小括号: 集合:set = {val1,val2,val3,val4},大括号. 1. 列表: list =

  • Python数据结构详细

    目录 1. 关于列表更多的内容 1.1. 把列表当作堆栈使用 1.2. 把列表当作队列使用 1.3. 列表推导式 1.4. 嵌套的列表推导式 2. del 语句 3. 元组和序列 4. 集合 6. 循环技巧 7. 深入条件控制 8. 比较序列和其它类型 1. 关于列表更多的内容 Python 的列表数据类型包含更多的方法.这里是所有的列表对象方法: list.``append(x) 把一个元素添加到列表的结尾,相当于 a[len(a):] = [x] list.``extend(L) 将一个给定

  • Python数据结构之列表与元组详解

    Python数据结构之列表与元组详解

    目录 Python 列表(list): 1.序列介绍: 2.列表的概述: 3.创建一个列表 4.列表的索引 5.列表的分片 6.列表的分片赋值 7.循环遍历列表 8.查找元素与计数 9.列表增加元素: 10.列表删除元素: 11.列表排序 Python 元组(tuple): 1.为什么要将元组设计成为不可变序列 2.创建元组 3.元组的遍历 4.元组的内置函数 Python 列表(list): 1.序列介绍:   序列是Python中最基本的数据结构.序列中的每个元素都分配一个数字 - 它的位置

  • Python数据结构之树的全面解读

    Python数据结构之树的全面解读

    目录 前言

  • Pandas与openpyxl库结合处理Excel表格实现代码

    Pandas与openpyxl库结合处理Excel表格实现代码

    前言 用过Pandas和openpyxl库的同学都知道,这两个库是相互互补的.Pandas绝对是Python中处理Excel最快.最好用的库,但是使用 openpyxl 的一些优势是能够轻松地使用样式.条件格式等自定义电子表格. 如果你又想轻松的使用Pandas处理Excel数据,又想为Excel电子表格添加一些样式,应该怎么办呢? 但是您猜怎么着,您不必担心挑选. 事实上,openpyxl 支持将数据从 Pandas DataFrame 转换为工作簿,或者相反,将 openpyxl 工作簿转换

  • Python 数据结构之十大经典排序算法一文通关

    Python 数据结构之十大经典排序算法一文通关

    目录 1.冒泡排序 算法演示 算法步骤 算法实现 2.选择排序 算法演示 算法步骤 算法实现 3.简单插入排序 算法演示 算法步骤 算法实现 4.希尔排序 算法演示 算法步骤 算法实现 5.归并排序 算法演示 算法步骤 算法实现 6.快速排序 算法演示 算法步骤 算法实现 7.堆排序 算法演示 算法步骤 算法实现 8.计数排序 算法演示 算法步骤 算法实现 9.桶排序 算法演示 算法步骤 算法实现 10.基数排序 算法演示 算法步骤 算法实现 一文搞掂十大经典排序算法 今天整理一下十大经典排序算

  • Python 数据结构之树的概念详解

    Python 数据结构之树的概念详解

    数据结构树简介 一.树简介 树(Tree)是一种抽象的数据结构,是一个数据的集合,集合中的数据组成了一个树状结构.例如上图,看起来像一棵倒挂的树,根朝上叶朝下. 树是由n(n>=0)个节点组成的具有层次关系的数据集合.当 n=0 时,树中没有节点,称为空树.当 n>0 时,有且仅有一个节点被称为根节点(Root),如果 n=1 ,树只有根节点一个节点.如果 n>1 ,除根节点外,将其余的节点分成m(m>0)个互不相交的数据集合,这 m 个集合每一个都要满足树的结构(有且仅有一个根节

  • 数据结构之树的概念详解

    数据结构之树的概念详解

    数据结构树简介 一.树简介 树(Tree)是一种抽象的数据结构,是一个数据的集合,集合中的数据组成了一个树状结构.例如上图,看起来像一棵倒挂的树,根朝上叶朝下. 树是由n(n>=0)个节点组成的具有层次关系的数据集合.当 n=0 时,树中没有节点,称为空树.当 n>0 时,有且仅有一个节点被称为根节点(Root),如果 n=1 ,树只有根节点一个节点.如果 n>1 ,除根节点外,将其余的节点分成m(m>0)个互不相交的数据集合,这 m 个集合每一个都要满足树的结构(有且仅有一个根节

  • Python数据结构与算法之算法分析详解

    Python数据结构与算法之算法分析详解

    目录 0. 学习目标 1. 算法的设计要求 1.1 算法评价的标准 1.2 算法选择的原则 2. 算法效率分析 2.1 大O表示法 2.2 常见算法复杂度 2.3 复杂度对比 3. 算法的存储空间需求分析 4. Python内置数据结构性能分析 4.1 列表性能分析 4.2 字典性能分析 0. 学习目标 我们已经知道算法是具有有限步骤的过程,其最终的目的是为了解决问题,而根据我们的经验,同一个问题的解决方法通常并非唯一.这就产生一个有趣的问题:如何对比用于解决同一问题的不同算法?为了以合理的方式

  • C++数据结构之文件压缩（哈夫曼树）实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • Python面向对象编程之继承与多态详解

    Python面向对象编程之继承与多态详解

    本文实例讲述了Python面向对象编程之继承与多态.分享给大家供大家参考,具体如下: Python 类的继承 在OOP(Object Oriented Programming)程序设计中,当我们定义一个class的时候,可以从某个现有的class 继承,新的class称为子类(Subclass),而被继承的class称为基类.父类或超类(Base class.Super class). 我们先来定义一个class Person,表示人,定义属性变量 name 及 sex (姓名和性别): 定义一

  • Python探索之URL Dispatcher实例详解

    URL dispatcher简单点理解就是根据URL,将请求分发到相应的方法中去处理,它是对URL和View的一个映射,它的实现其实也很简单,就是一个正则匹配的过程,事先定义好正则表达式和该正则表达式对应的view方法,如果请求的URL符合这个正则表达式,那么就分发这个请求到这个view方法中. 有了这个base,我们先抛出几个问题,提前思考一下: 这个映射定义在哪里?当映射很多时,如果有效的组织? URL中的参数怎么获取,怎么传给view方法? 如何在view或者是template中反解出UR

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    python实现决策树C4.5算法详解(在ID3基础上改进)

    一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

  • python 实现GUI(图形用户界面)编程详解

    Python支持多种图形界面的第三方库,包括: wxWidgets Qt GTK Tkinter: Tkinter 模块(Tk 接口)是 Python 的标准 Tk GUI 工具包的接口 .Tk 和 Tkinter 可以在大多数的 Unix 平台下使用,同样可以应用在 Windows 和 Macintosh 系统里.Tk8.0 的后续版本可以实现本地窗口风格,并良好地运行在绝大多数平台中. wxPython:wxPython 是一款开源软件,是 Python 语言的一套优秀的 GUI 图形库,允

  • Python 列表与链表的区别详解

    Python 列表与链表的区别详解

    目录 python 列表和链表的区别 列表的实现机制 链表 链表与列表的差异 python 列表和链表的区别 python 中的 list 并不是我们传统意义上的列表,传统列表--通常也叫作链表(linked list)是由一系列节点来实现的,其中每个节点都持有一个指向下一节点的引用. class Node: def __init__(self, value, next=None): self.value = value self.next = next 接下来,我们就可以将所有的节点构造成一个

随机推荐