【NOI】树的初步认识

文章目录

前言
一、树
- 1.什么是树？
- 2.树的基本概念
- 3.树的基本术语
- - 3.1 节点
  - - 3.1.1 根节点
    - 3.1.2 父节点、子节点
    - 3.1.3 兄弟节点、堂兄弟节点
    - 3.1.4 祖先节点、子孙节点
    - 3.1.5 叶子节点/终端节点
    - 3.1.6 分支节点/非终端节点
  - 3.2 边
  - 3.3 度
  - - 3.3.1 树的度
  - 3.4 层次
  - - 3.4.1 树的深度
    - 3.4.2 树的宽度
  - 3.5 有序树
  - - 3.5.1 第一个孩子
    - 3.5.2 最后一个孩子
二、树的表示方法
- 1.树形表示
- 2.嵌套表示
- 3.广义表表示
- 4.凹入表示法
- 5.二叉链表（孩子-兄弟）表示法
三、练习
四、总结
五、感谢

前言

本章节主要介绍了树这一重要的数据结构概念及其相关术语。树作为一种模拟自然界中树状结构的抽象数据类型，在计算机科学中有广泛的应用，尤其在信息检索、文件系统、程序设计语言解析等领域。通过形象的例子阐述了如何将书籍分类体系构建为树形结构，使得读者能更好地理解树的层次化组织特性。

在详细解释树的基本术语时，我们介绍了节点、根节点、父节点、子节点、兄弟节点、堂兄弟节点、祖先节点、子孙节点以及叶子节点和分支节点的概念。同时，还介绍了树的边，它是连接节点并表示父子关系的纽带。此外，我们深入探讨了树的度，即一个节点拥有的子节点数量，以及树的度（整体意义上，即树中所有节点的最大度数），这对于理解和分析树的拓扑结构至关重要。

接着，我们详细说明了树的层次和深度，层次是根据节点与根节点的相对位置划分的级别，而深度则是从根节点到最远叶子节点的最长路径长度。树的宽度则是在特定层级上的节点最大数量，体现了树的横向扩张程度。

另外，还特别提到了有序树这一特殊类型的树，其中节点的子树是有固定顺序的，例如二叉树和二叉搜索树等。有序树中的节点有明确的“第一个孩子”和“最后一个孩子”的概念，而在无序树中则没有这样的顺序约束。

最后，本节还列举了四种常见的树表示方法，分别是树形表示法、嵌套表示法、广义表表示法和凹入表示法，每种方法都有各自的优点和适用场景，有助于实际应用中根据需要灵活选择合适的方式来表达和处理树结构的数据。

学习路线：C++从入门到NOI学习路线

学习大纲：C++全国青少年信息学奥林匹克竞赛（NOI）入门级-大纲

一、树

1.什么是树？

如果有人问你什么是树？你可能首先想到的是大自然中的树木，它们有根、枝干和树叶，彼此之间有着明显的层次和联系。

在这里插入图片描述

而在计算机科学中，我们也有一种类似的概念，叫做“树”数据结构，不过这里的“树”是虚拟的，是用来组织和管理信息的一种方式。

在这里插入图片描述

想象一下，我们在整理书架上的书籍。如果你按照一定的逻辑把书籍分成不同的类别，比如文学、科学、历史等，每个类别再细分，比如文学类可以分为小说、诗歌、戏剧等，那么这种分类的方式就可以看作是一棵树。

在这里插入图片描述

这似乎看起来也不像树啊？

在这里插入图片描述

这样看起来是不是就像多了！

在这里插入图片描述

2.树的基本概念

树是n(n≥0)个结点的有限集。
当 n=0 时称为空树;
当n>0时为非空树，在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点可分为 m(m ≥0)个互不相交的有限集 T1,T2…,Tm，其中每一个集合又称为一棵树，并且称为根的子树;同理，每一棵子树又可以分为若干个互不相交的有限集……

3.树的基本术语

接下来简单介绍一下关于树的一些基本术语。

3.1 节点

节点是构成树的基本单元，通常用于存储数据元素。在树形结构中，每个节点可能包含数据信息和指向其子节点的指针。

在这里插入图片描述

3.1.1 根节点

根节点是树的顶部节点，它是唯一没有父节点的节点，是整个树结构的起点。在现实世界的应用中，根节点往往代表最高级别的分类或组织单元。

在这里插入图片描述

一个树结构只包含一个根节点，所有其他节点都是从根节点开始逐层向下扩展的。

多个根节点那是森林。

森林是由多棵独立的树组成的集合。每棵树都有自己的根节点，并且这些树之间互不影响，不存在从一棵树的节点可以直接到达另一棵树节点的情况。

3.1.2 父节点、子节点

在树中，除了根节点之外，每个节点都有且只有一个父节点，即直接连接到该节点的上一层节点。

比如文学的父节点就是书架。

在这里插入图片描述

子节点是指直接连接到某节点下方的节点。一个节点可以有零个、一个或多个子节点。

比如文学的子节点有：小说、戏剧、诗歌。

在这里插入图片描述

而对于小说节点来说文学就是它的父节点，因此每个节点都可以是其他节点的父节点，也可以有零个或多个子节点。

在这里插入图片描述

3.1.3 兄弟节点、堂兄弟节点

兄弟节点是指具有同一个父节点的不同子节点。它们之间是并列关系，而不是父子关系。

例如小说、戏剧、诗歌就属于兄弟节点。
在这里插入图片描述

堂兄弟节点指的是位于同一层的、并且父节点之间是兄弟节点的节点。

在这里插入图片描述

什么？你还是搞不懂兄弟节点和堂兄弟节点。

这么说吧，兄弟节点就是同爸又同爷，堂兄弟节点就是同爷不同爸。

还有下面这种情况也不属于堂兄弟节点，因为差辈了，不许各论各的。

在这里插入图片描述

还是不清楚花两块钱去超市门口摇一摇去。

3.1.4 祖先节点、子孙节点

祖先节点是指从当前节点向上追溯，直至根节点所经过的所有节点。一个节点的所有祖先节点和它本身共同构成了该节点的祖先路径。

例如小说的祖先节点有文学、书架。

在这里插入图片描述

子孙节点是指以当前节点为起点，沿着边向下所能到达的所有节点。这包括当前节点的所有子节点、子节点的子节点等，直至叶子节点。

例如文学的子孙节点包括小说、戏剧、诗歌、现代诗歌。

在这里插入图片描述

3.1.5 叶子节点/终端节点

叶子节点是指没有子节点的节点。在树形结构中，叶子节点是树的末梢，它们不再向下扩展。

例如科学、历史、小说、戏剧、诗歌。

在这里插入图片描述

3.1.6 分支节点/非终端节点

分支节点是树中除叶子节点外的所有节点。它们具有一个或多个子节点，负责连接和支撑整棵树的结构。分支节点在树中起到了桥梁的作用，将各个部分连接起来，确保数据的流动和访问。

例如文学、书架就是分支节点。

在这里插入图片描述

3.2 边

边是连接两个节点的关系，表示它们之间的父子关系。在树中，边通常表示从父节点指向子节点的有向关系。

3.3 度

度是指一个节点拥有的子节点数量。一个节点的度反映了该节点的直接子节点数量，可以用来描述节点的分支情况。对于树而言，根节点的度通常等于其子节点的数量，而叶子节点的度为0。

例如“书架”是整个结构的根节点，它拥有三个直接子节点：“文学”、“科学”和“历史”。根节点有三个子节点，因此可以说根节点的度（即一个节点拥有的子节点数）为3。

在这里插入图片描述

3.3.1 树的度

树的度是指树中所有节点的最大度数。换句话说，树的度是树内任一节点的最大子节点数。例如，在一棵树中，如果节点A的度为3，节点B的度为2，节点C的度为4，那么这棵树的度就是4，因为节点C的度是最大的。

在讨论树的度时，通常所说的“度”指的是节点的度，即一个节点拥有子节点的数量。尤其是在问题描述或算法分析过程中，如果没有特别指出，提到“度”通常是指单个节点的度。

然而，在描述整个树的特性时，也会提到“树的度”，即树中各节点最大度数。这个概念主要用于刻画整棵树的拓扑结构特点，例如在讨论二叉树、m叉树等特定类型树的时候。

3.4 层次

在树形数据结构中，"树的层次"是指从根节点开始，按照节点与根节点之间的相对位置划分的级别。 根节点所在的层次定义为第1层，根节点的直接子节点位于第2层，以此类推，每一层上的节点都是其上一层节点的直接后代。

具体来说：

根节点在第1层；
根节点的每个子节点在第2层；
子节点的子节点在第3层；
依此类推，直至叶节点（没有子节点的节点）。

每增加一代子孙节点，层次就增加1。因此，树的最大层次取决于树的高度，即从根节点到最远叶节点所经过的边的数量。

在这里插入图片描述

3.4.1 树的深度

树的深度，也称为树的高度或树的层数，指的是从树的根节点到最远叶子节点的路径上经过的节点数目。 这个深度可以看作是从根节点到树中最深层次的节点所需经过的层级数。在树形结构中，深度最大的节点路径决定了整棵树的深度。

例如从书架到现代诗歌的最长路径上有4个节点。具体来说，这条路径是这样的：

从书架出发，向下进入历史节点。
然后继续向下进入诗歌节点。
再次向下进入现代诗歌节点。

这条路径包含了4个节点：书架、历史、诗歌和现代诗歌。因此，从书架到现代诗歌的最长路径上有4个节点，所以这棵树的深度是4。

在这里插入图片描述

3.4.2 树的宽度

树的宽度通常指的是某一特定层的节点数，也就是树在该层的最大节点数。 这实际上描述的是树在某个层级上最宽的部分的跨度。

例如在第二层，有3个节点（文学、科学和历史）。在第三层，有5个节点（小说、戏剧、诗歌、中国和美国）。在第四层，有1个节点（现代诗歌）。

因此，树的宽度在第三层达到最大，为5个节点。

在这里插入图片描述

树的深度和宽度是描述树形结构特性的两个不同维度。深度关注的是从根节点到最远叶子节点的纵向层级，而宽度则关注树在某个层级或某个节点上的横向扩展。

3.5 有序树

有序树是一种特殊的树形结构，其特点在于树中每个结点的各子树从左至右是有次序的，不能互换。

有序树的一个典型例子是二叉树（Binary Tree），特别是二叉搜索树（Binary Search Tree），在这种树中，每个节点的左子树中的所有节点的键值小于该节点的键值，而右子树中的所有节点的键值大于该节点的键值，这就是一种有序关系。

有序树可以进一步细分为多种类型，如二叉树、三叉树或多叉树等，只要满足子节点之间的顺序不可随意调换即可。

3.5.1 第一个孩子

如果一个节点有多个子节点（在多叉树或多子女树中），那么它的“第一个孩子”指的是按照节点间预设的顺序关系，排在首位的那个子节点。在二叉树中，如果节点有左子节点，则左子节点就是第一个孩子。

3.5.2 最后一个孩子

同样，一个节点的“最后一个孩子”是指按照预设顺序排列在末尾的那个子节点。在二叉树中，如果节点有右子节点，则右子节点就是最后一个孩子。在多叉树中，根据预先设定的顺序，最后一个孩子是所有子节点中顺序最后的那个。

有序树与之对应的是无序树。而在无序树中，子节点的顺序并不固定，因此没有“第一个孩子”和“最后一个孩子”的概念。

二、树的表示方法

1.树形表示

树形表示法：这种表示方法通过图形化的形式直观展示树的结构，通常采用自顶向下的方式绘制，根节点位于顶部，子节点按照层次和顺序排列在下方，通过线条连接表示父子关系。

在这里插入图片描述

2.嵌套表示

嵌套表示法：通常指的是嵌套集合（文氏图）表示法，该表示方法用集合表示结点之间的层次关系。对于其中任意两个集合，它们要么不相交，要么一个集合包含另一个集合。这种表示方法特别适用于将树结构存储在关系数据库中，因为每个节点都有两个值：左值和右值。对于树中的任意一个节点，其子树中所有节点的左值都大于该节点的左值，右值都小于该节点的右值。这种方法便于快速查询树结构中的数据，但更新操作可能较为复杂。

在这里插入图片描述

嵌套表示法通常使用编程语言的结构（如对象、数组或字典）来表示树。

在这里插入图片描述

例如，用对象表示动物分类树：

{
  name: "动物",
  children: [
    {
      name: "哺乳动物",
      children: [
        {
          name: "猫科",
          children: [{ name: "猫" }, { name: "老虎" }]
        },
        {
          name: "犬科",
          children: [{ name: "狗" }, { name: "狼" }]
        }
      ]
    },
    {
      name: "鸟类",
      children: [{ name: "鹰" }, { name: "鸽子" }]
    }
  ]
}

3.广义表表示

广义表表示法：广义表是一种线性结构，用于表示树结构时，可以将树看作是广义表的一种特殊情况。在广义表中，树的根节点作为表头，其子树可以看作是表元素，如果子树是非空的，则又是一个广义表。

(A, (B, (D, E), C, (F, G)))

这个广义表表示如下：

外部大圆 A 包含内部的所有小圆；
圆 B 表示集合 B，它包含元素 D 和 E；
圆 C 表示集合 C，它包含元素 F 和 G；

在这里插入图片描述
广义表类似一个列表，但允许列表中包含子列表。例如，用广义表表示上面的动物分类树：

(动物 (哺乳动物 (猫科 (猫) (老虎)) (犬科 (狗) (狼))) (鸟类 (鹰) (鸽子)))

这里，圆括号代表节点，节点名（如“猫科”）和圆括号内的子列表共同构成一个节点的内容。子列表表示该节点的子节点。这种表示法比较紧凑，适合计算机程序处理。

4.凹入表示法

凹入表示法：也称为缩进表示法，它类似于书的目录，用节点逐层缩进的方法表示树中各个节点之间的层次关系。这种方法能够清晰地展示树形结构的层次关系。

在这里插入图片描述

凹入表示法就像写作文时的缩进。

在这里插入图片描述

例如，写一个关于动物分类的文章，你会这样写：

5.二叉链表（孩子-兄弟）表示法

二叉链表（孩子-兄弟）表示法是一种用于表示树结构的数据结构，它特别适用于表示多叉树（每个节点可以有多个子节点）。在二叉链表（孩子-兄弟）表示法中，每个节点除了包含自己的数据外，还包含两个指针字段：一个指向其第一个孩子节点，另一个指向其下一个兄弟节点。
这种方法适用于表示任何类型的树，包括二叉树、多叉树等。

简单来说，就是给每个节点设计一张“名片”，上面记录了两方面的信息：

本节点的信息：比如一个人的名字、年龄，或者文件夹的名字等。我们把它称为“数据”。
与其它节点的关系：因为树中的节点之间有父子关系和兄弟关系，所以我们需要记录：

孩子信息：指向这个节点的“第一个孩子”的“名片”。如果这个节点没有孩子，就写上“无孩子”。
兄弟信息：指向这个节点的“下一个兄弟”的“名片”。如果没有兄弟，就写上“我是最后一个”。

举个例子：

假设我们有这样一颗家庭树：

在这里插入图片描述

用二叉链表（孩子-兄弟）表示法来描述，每个节点的“名片”就像这样：

爷爷的名片：

数据：爷爷的名字、年龄等
孩子信息：指向“爸爸”的名片
兄弟信息：无兄弟，写上“我是最后一个”

爸爸的名片：

数据：爸爸的名字、年龄等
孩子信息：指向“我”的名片
兄弟信息：指向“姑姑”的名片

我的名片：

数据：我的名字、年龄等
孩子信息：无孩子，写上“无孩子”
兄弟信息：指向“妹妹”的名片

妹妹的名片：

数据：妹妹的名字、年龄等
孩子信息：无孩子，写上“无孩子”
兄弟信息：我是最后一个，写上“我是最后一个”

这样，通过这些“名片”（节点），我们就可以清楚地知道每个人在家庭树中的位置，以及他们与其他家庭成员的关系了。

三、练习

参考下图的树，完成下列问题。

（1）该树有哪些节点_______________，其中的叶子节点有______________，分支节点有_________________。

（2）节点A的度为___，节点B的度为 ___，树的度为 ___。

（3）请写出A节点到K节点经过的路径 ____________________。

（4）H节点的兄弟节点有_________，堂兄弟节点有___________。

（5）F节点的祖先节点有__________，子孙节点有_____________。

（6）该树的深度为___________，树的宽度为______________。

请根据下面的树形表示法完成以下练习：

在这里插入图片描述

（1）转换成凹入表示法、嵌套表示法、广义表表示法。

四、总结

本章围绕树这一基础数据结构进行了全面介绍，不仅阐述了树的各种组成部分和相关术语，还详细描绘了树的层次结构特征，如树的深度、宽度以及节点的度数。通过对有序树和无序树的对比讲解，读者能够掌握不同类型树的特点和应用场景。此外，通过对比各种树的表示方法，使读者了解到如何借助图形化、集合化、线性化以及文本化的手段来有效展示和记录树的结构信息。这一系列基础知识的学习和掌握，对于后续在诸如算法设计、数据组织及编程实现等方面都有着极其重要的作用。通过本章内容的学习，读者应当能够熟练识别和操作树形结构，并能够在解决实际问题时合理运用树的相关概念和技术。