（2021新教科版）高中信息技术必修一 3.2数据与结构（第二课时）ppt课件.pptx

1、3.2 数据与结构数据与结构(第第2课时课时) 【教学目标】 了解树、图结构的基本概念及其特点。 根据数据结构的特点，会选用合适的数据结构 组织数据解决简单的问题。 【教学重点】数据结构中的树结构和图结构。 【教学难点】数据结构中的树结构和图结构。 一、引入一、引入 学生预习，阅读第学生预习，阅读第59、60页页“任务二任务二 探究快递配探究快递配 送过程送过程”之之“活动活动1 了解快递派送线路了解快递派送线路”，完成第，完成第 60页的连点成树（见下图）。页的连点成树（见下图）。 二、树结构二、树结构 1、树的递归定义：、树的递归定义： 树是由树是由n（n0）个节点组成的有限集合。若）个节

2、点组成的有限集合。若n = 0，则称为空树。，则称为空树。 任何一个非空树均满足以下两个条件：任何一个非空树均满足以下两个条件： （1）仅有一个称为根的节点。）仅有一个称为根的节点。 （2）当）当n0时，其余节点可分为时，其余节点可分为m（m0）个互不相交的有限集）个互不相交的有限集 合，其中每个集合又是一棵树，并称为根的子树。合，其中每个集合又是一棵树，并称为根的子树。 如下图所示树的结构：（图如下图所示树的结构：（图1） 2、树的常见概念、树的常见概念 1）树的结点：）树的结点： 结点：使用树结构存储的每一个数据元素都被称为结点：使用树结构存储的每一个数据元素都被称为“结点结点”。例如，。

3、例如， 图图 1中，数据元素中，数据元素 A 就是一个结点就是一个结点； 父结点（双亲结点）、子结点和兄弟结点：对于图父结点（双亲结点）、子结点和兄弟结点：对于图 1（A）中的结点）中的结点 A、 B、C、D 来说，来说，A 是是 B、C、D 结点的父结点（也称为结点的父结点（也称为“双亲结点双亲结点”），）， 而而 B、C、D 都是都是 A 结点的子结点（也称结点的子结点（也称“孩子结点孩子结点”）。对于）。对于 B、C、 D 来说，它们都有相同的父结点，所以它们互为兄弟结点。来说，它们都有相同的父结点，所以它们互为兄弟结点。 2、树的常见概念、树的常见概念 1）树的结点：）树的结点： 树根

4、结点（简称树根结点（简称“根结点根结点”）：每一个非空树都有且只有一个被称为）：每一个非空树都有且只有一个被称为 根的结点。图根的结点。图 1（A）中，结点）中，结点A就是整棵树的根结点。树根的判断依就是整棵树的根结点。树根的判断依 据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。 叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶 结点）。例如图结点）。例如图 1（A）中，结点）中，结点 K、L、F、G、M、I、J 都是这棵树的都是这棵树的 叶子结

5、点。叶子结点。 2）子树与空树）子树与空树 子树：如图子树：如图 1（A）中，整棵树的根结点为结点）中，整棵树的根结点为结点 A，而如果单看结点，而如果单看结点 B、E、F、K、L 组成的部分组成的部分 来说，也是棵树，而且节点来说，也是棵树，而且节点 B 为这棵树的根结为这棵树的根结 点。所以称点。所以称 B、E、F、K、L 这几个结点组成的这几个结点组成的 树为整棵树的子树；同样，结点树为整棵树的子树；同样，结点 E、K、L 构成构成 的也是一棵子树，根结点为的也是一棵子树，根结点为 E。 注意：单个结点也是一棵树，只不过根结点就注意：单个结点也是一棵树，只不过根结点就 是它本身。图是它本

6、身。图 1（A）中，结点）中，结点 K、L、F 等都是等都是 树，且都是整棵树的子树。树，且都是整棵树的子树。 知道了子树的概念后，树也可以这样定义：树知道了子树的概念后，树也可以这样定义：树 是由根结点和若干棵子树构成的。是由根结点和若干棵子树构成的。 空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结 点。点。 补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能 有交集。例如，图有交集。例如，图 1（A）中，除了根结点）中，除了根结点 A，其余

7、元素又各自构成了三，其余元素又各自构成了三 个子树，根结点分别为个子树，根结点分别为 B、C、D，这三个子树相互之间没有相同的结点。，这三个子树相互之间没有相同的结点。 如果有，就破坏了树的结构，不能算做是一棵树。如果有，就破坏了树的结构，不能算做是一棵树。 3）结点的度和层次）结点的度和层次 对于一个结点，拥有的子树数（结点有多少分支）称对于一个结点，拥有的子树数（结点有多少分支）称 为结点的度（为结点的度（Degree）。例如，图）。例如，图 1（A）中，根结）中，根结 点点 A 下分出了下分出了 3 个子树，所以，结点个子树，所以，结点 A 的度为的度为 3。 一棵树的度是树内各结点的度

8、的最大值。图一棵树的度是树内各结点的度的最大值。图 1（A） 表示的树中，各个结点的度的最大值为表示的树中，各个结点的度的最大值为 3，所以，整，所以，整 棵树的度的值是棵树的度的值是 3。 结点的层次：从一棵树的树根开始，树根所在层为第结点的层次：从一棵树的树根开始，树根所在层为第 一层，根的孩子结点所在的层为第二层，依次类推。一层，根的孩子结点所在的层为第二层，依次类推。 对于图对于图 1（A）来说，）来说，A 结点在第一层，结点在第一层，B、C、D 为第为第 二层，二层，E、F、G、H、I、J 在第三层，在第三层，K、L、M 在第四在第四 层。层。 一棵树的深度（高度）是树中结点所在的最

9、大的层次。一棵树的深度（高度）是树中结点所在的最大的层次。 图图 1（A）树的深度为）树的深度为 4。 如果两个结点的父结点虽不相同，但是它们的父结点如果两个结点的父结点虽不相同，但是它们的父结点 处在同一层次上，那么这两个结点互为堂兄弟。例如，处在同一层次上，那么这两个结点互为堂兄弟。例如， 图图 1（A）中，结点）中，结点 G 和和 E、F、H、I、J 的父结点都在的父结点都在 第二层，所以之间为堂兄弟的关系。第二层，所以之间为堂兄弟的关系。 4）有序树和无序树）有序树和无序树 如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定如果树中结点的子树从左到右看，谁在左边，谁在右边，是有

10、规定 的，这棵树称为有序树；反之称为无序树。的，这棵树称为有序树；反之称为无序树。 在有序树中，一个结点最左边的子树称为在有序树中，一个结点最左边的子树称为第一个孩子第一个孩子，最右边的，最右边的 称为称为最后一个孩子最后一个孩子。 拿图拿图 1（A）来说，如果是其本身是一棵有序树，则以结点）来说，如果是其本身是一棵有序树，则以结点 B 为根为根 结点的子树为整棵树的第一个孩子，以结点结点的子树为整棵树的第一个孩子，以结点 D 为根结点的子树为整为根结点的子树为整 棵树的最后一个孩子棵树的最后一个孩子。 5）森林：）森林： 由由 m（m = 0）个互不相交的树组成的集合被称为森林。图）个互不相

11、交的树组成的集合被称为森林。图 1（A） 中，分别以中，分别以 B、C、D 为根结点的三棵子树就可以称为森林。前面为根结点的三棵子树就可以称为森林。前面 讲到，树可以理解为是由根结点和若干子树构成的，而这若干子讲到，树可以理解为是由根结点和若干子树构成的，而这若干子 树本身是一个森林，所以，树还可以理解为是由根结点和森林组树本身是一个森林，所以，树还可以理解为是由根结点和森林组 成的。用一个式子表示为：成的。用一个式子表示为： Tree =（root,F） 其中，其中，root 表示树的根结点，表示树的根结点，F 表示由表示由 m（m = 0）棵树组成的森）棵树组成的森 林。林。 3、二叉树：

12、、二叉树： 在日常的应用中，我们 讨论和用的更多的是树 的其中一种结构，就是 二叉树。二叉树二叉树是树的 特殊一种. 具有如下特点：具有如下特点： 1、每个结点最多有两颗子树，结点的度最大为、每个结点最多有两颗子树，结点的度最大为2。 2、左子树和右子树是有顺序的，次序不能颠倒。、左子树和右子树是有顺序的，次序不能颠倒。 3、即使某结点只有一个子树，也要区分左右子树。、即使某结点只有一个子树，也要区分左右子树。 二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且 在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也在

13、查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也 有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非 常有用。常有用。 【说一说】社会、工作、生活中的树形结构实例： 快递公司物流配送体系快递公司物流配送体系 树结构之行政区划树结构之行政区划 三、图结构三、图结构 图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或 弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点 有边相连，图结构中数

14、据元素之间是多对多的关系。有边相连，图结构中数据元素之间是多对多的关系。 1、常见的概念、常见的概念 1）顶点（）顶点（vertex）：）：图中的数据元素，如图一。 2）边（）边（edge）：）：图中连接这些顶点的线，如图一。 所有的顶点构成一个顶点集合，所有的边构成边的集合，一个完整的图 结构就是由顶点集合和边集合组成。图结构在数学上记为以下形式： G=（V,E）或者G=（V（G），E（G） 其中V（G）表示图结构所有顶点的集合，顶点可以用不同的数字或者字 母来表示。E（G）是图结构中所有边的集合，每条边由所连接的两个顶点来 表示。 图结构中顶点集合V（G）不能为空，必须包含一个顶点，而图结

15、构边集 合可以为空，表示没有边。 3）无向图）无向图 如果一个图结构中，所有的边都没有方向性， 那么这种图便称为无向图。典型的无向图， 如图二所示。由于无向图中的边没有方向性， 这样我们在表示边的时候对两个顶点的顺序 没有要求。例如顶点VI和顶点V5之间的边， 可以表示为(V2，V6),也可以表示为(V6，V2)。 对于图二无向图，对应的顶点集合和边集合如下： V（G）=V1，V2，V3，V4，V5，V6 E（G）=（V1,V2），（V1，V3），（V2，V6），（V2， V5），（V2，V4），（V4，V3），（V3，V5），（V5， V6） 4）有向图）有向图 一个图结构中，边是有方向性的

16、，那么 这种图就称为有向图，如图三所示。由 于图的边有方向性，我们在表示边的时 候对两个顶点的顺序就有要求。我们采 用尖括号表示有向边，例如表 示从顶点V2到顶点V6，而表 示顶点V6到顶点V2。 对于有向图，对应的顶点集合和边集合如下： V（G）=V1，V2，V3，V4，V5，V6 E（G）=， ， 【活动【活动3】规划取快递最快路线】规划取快递最快路线 【朴素算法】穷举遍历，依次列出所有 可能走法如图3.2.10。将图中每个节点 进行编号，编号互不相同：如作为根节 点的“家”编号为“X”,其3个子节点 （快递门店A，快递门店B，快递门店C） 分别编号为“A”“B”“C”，详 见下图。 【算

17、法演示【算法演示1】求解最短时间（基于图】求解最短时间（基于图3.2.10的分析树）的分析树） 【算法演示【算法演示2】求解最短时间（直接对图】求解最短时间（直接对图3.2.9进行深度优进行深度优 先遍历）先遍历） 练习练习 人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊和一捆白菜，人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊和一捆白菜， 来到一条河边，河边只有一条小船，人每次过河最多只能带一样，如来到一条河边，河边只有一条小船，人每次过河最多只能带一样，如 果人不在现场，狼就要吃羊，羊就要吃菜。他应该怎样安排过河呢？果人不在现场，狼就要吃羊，羊就要吃菜。他应该怎样安排过河呢？ 请完成下面的请完成下面的“树树”结构分析图，帮他找到可行的过河方案。结构分析图，帮他找到可行的过河方案。 提示：可约定对象在左岸用提示：可约定对象在左岸用0表示，在右岸用表示，在右岸用1表示。表示。 程序与调试程序与调试 课后作业：课后作业： 课后作业：课后作业： 一对一 一对多 多对多 排队（上车、过马路、付款）、 医院就诊电子牌上的就诊队列 行政区划、书的目录结构、磁 盘文件存储结构、注册表结构 全国航运图、铁路运输图、高 速公路网 谢谢大家！谢谢大家！