1、3.23.2 数据与结构数据与结构( (第二课时第二课时) ) 【教学目标】 了解树、图结构的基本概念及其特点。 根据数据结构的特点，会选用合适的数据结构组织数据解决简单的问题。 【教学重点】数据结构中的树结构和图结构。 【教学难点】数据结构中的树结构和图结构。 【教学过程】【教学过程】 一、引入一、引入 学生预习，阅读第 59、60 页“任务二探究快递配送过程”之“活动 1了解快递派送线路” ，完成 第 60 页的连点成树（见下图） 。教师检查，并评讲填写情况，引出树结构。 二、树结构二、树结构 1 1、树的递归定义：、树的递归定义： 树是由n（n0）个节点组成的有限集合。若n = 0，则称
2、为空树。任何一个非空树均满足以下两个条 件： （1）仅有一个称为根的节点。 （2）当n0时，其余节点可分为m（m0）个互不相交的有限集合，其中每个集合又是一棵树，并称 为根的子树。如下图所示树的结构：（图1） 2 2、树的常见概念、树的常见概念 1 1）树的结点：）树的结点： 结点结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图 1中，数据元素 A 就是一个 结点； 父结点（双亲结点）、子结点和兄弟结点：父结点（双亲结点）、子结点和兄弟结点：对于图 1（A）中的结点 A、B、C、D 来说，A 是 B、C、 D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子
3、结点（也称“孩子结点”）。对 于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。 树根结点树根结点（简称简称“根结点根结点”）：每一个非空树都有且只有一个被称为根的结点。图 1（A）中，结点A 就是整棵树的根结点。树根的判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。 叶子结点：叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如图 1（A）中，结 点 K、L、F、G、M、I、J 都是这棵树的叶子结点。 2 2）子树与空树）子树与空树 子树子树：如图 1（A）中，整棵树的根结点为结点 A，而如果单看结点 B、E、F、K、L 组成的部分来说
4、， 也是棵树，而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树； 同样，结点 E、K、L 构成的也是一棵子树，根结点为 E。 注意：单个结点也是一棵树，只不过根结点就是它本身。图 1（A）中，结点 K、L、F 等都是树，且 都是整棵树的子树。 知道了子树的概念后，树也可以这样定义：树是由根结点和若干棵子树构成的。 空树：空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。 补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能有交集。例如，图 1（A）中， 除了根结点 A，其余元素又各自构成了三个子树，根结点分别为 B、C、D，
5、这三个子树相互之间没有相同 的结点。如果有，就破坏了树的结构，不能算做是一棵树。 3 3）结点的度和层次）结点的度和层次 对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（结点的度（DegreeDegree）。例如，图 1（A）中， 根结点 A 下分出了 3 个子树，所以，结点 A 的度为 3。 一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以， 整棵树的度的值是 3。 结点的层次结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类 推。对于图 1（A）来说，A 结点在第一层，B、C、D 为第二层，E、F、
6、G、H、I、J 在第三层，K、L、M 在 第四层。 一棵树的深度（高度）是树中结点所在的最大的层次。图 1（A）树的深度为 4。 如果两个结点的父结点虽不相同，但是它们的父结点处在同一层次上，那么这两个结点互为堂兄弟。 例如，图 1（A）中，结点 G 和 E、F、H、I、J 的父结点都在第二层，所以之间为堂兄弟的关系。 4 4）有序树和无序树）有序树和无序树 如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为 无序树。 在有序树中，一个结点最左边的子树称为第一个孩子，最右边的称为最后一个孩子。 拿图 1（A）来说，如果是其本身是一棵有序树，则以结点 B 为
7、根结点的子树为整棵树的第一个孩子， 以结点 D 为根结点的子树为整棵树的最后一个孩子。 5 5）森林：）森林： 由 m（m = 0）个互不相交的树组成的集合被称为森林。图 1（A）中，分别以 B、C、D 为根结点的 三棵子树就可以称为森林。前面讲到，树可以理解为是由根结点和若干子树构成的，而这若干子树本身是 一个森林，所以，树还可以理解为是由根结点和森林组成的。用一个式子表示为： Tree =（root,F） 其中，root 表示树的根结点，F 表示由 m（m = 0）棵树组成的森林。 3 3、二叉树：、二叉树： 在日常的应用中， 我们讨论和用的更多的是树的其中一种结构，就是二叉树。 二叉树二
8、叉树是树的特殊一种， 具有如下特点： 1、每个结点最多有两颗子树，结点的度最大为2。 2、左子树和右子树是有顺序的，次序不能颠倒。 3、即使某结点只有一个子树，也要区分左右子树。 二叉树是一种比较有用的折中方案，它添加，删除元素都很快， 并且在查找方面也有很多的算法优化， 所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常 有用。来源:学|科|网Z|X|X|K 【说一说】社会、工作、生活中的树形结构实例： 快递公司物流配送体系快递公司物流配送体系 树结构之行政区划树结构之行政区划 来源来源:Z.xx.k.Com:Z.xx.k.Com 三、图结构三、图结
9、构 图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构 中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。 1 1、常见的概念、常见的概念 1）顶点（顶点（vertex）：）：图中的数据元素，如图一。 2）边边（edge）：图中连接这些顶点的线，如图一。 所有的顶点构成一个顶点集合， 所有的边构成边 的集合，一个完整的图结构就是由顶点集合和边集 合组成。图结构在数学上记为以下形式： G=（V,E） 或者 G=（V（G），E（G） 其中 V（G）表示图结构所有顶点的集合，顶点可以用不同的数字或者字母来表示。E（G）是图结构 中所有边的
10、集合，每条边由所连接的两个顶点来表示。 图结构中顶点集合 V（G）不能为空，必须包含一个顶点，而图结构边集合可以为空，表示没有边。 3）无向图无向图 如果一个图结构中，所有的边都没有方向性， 那么这种图便称为无向图。 典型的无向图， 如图二所 示。 由于无向图中的边没有方向性， 这样我们在表示 边的时候对两个顶点的顺序没有要求。例如顶点 VI 和顶点 V5 之间的边，可以表示为(V2， V6),也可以 表示为(V6，V2)。 （图二图二 无向图无向图） 对于图二无向图，对 应的顶点集合和边集合如下： V（G）= V1，V2，V3，V4，V5，V6 E（G）= （V1,V2），（V1，V3），（
11、V2，V6），（V2，V5），（V2，V4），（V4，V3），（V3， V5），（V5，V6） 4）有向图有向图 一个图结构中， 边是有方向性的， 那么这种图就称为 有向图，如图三所示。由于图的边有方向性，我们在表示 边的时候对两个顶点的顺序就有要求。我们采用尖括号表 示有向边，例如表示从顶点 V2 到顶点 V6，而 表示顶点 V6 到顶点 V2。 图三图三 有向图有向图 对于图三有向图，对应的顶点集合和边集合如下： V（G）= V1，V2，V3，V4，V5，V6 E（G）= ， ， 【说一说】社会、工作、生活中的图结构实例： 城市交通图（铁路网，公路网，航空网） 电话网、互联网 来源:学科网
12、ZXXK 【活动3】规划取快递最快路线 【朴素算法】穷举遍历，依次列出所有可能走法如图3.2.10。将图中每个节点进行编号， 编号互不相同：如作为根节点的“家”编号为“X”,其3个子节点（快递门店A，快递门店B， 快递门店C）分别编号为“A” “B” “C”，详见下图。 【算法演示 1】求解最短时间（基于图 3.2.10 的分析树） 【算法演示 2】求解最短时间（直接对图 3.2.9 进行深度优先遍历） 四、小结四、小结 树结构和图结构，是两种比较难的数据结构。 领会树结构和图结构的本质特征， 会用树结构、 图结构对工作学习生活中的具体问题进行抽象和分析， 解决一些简单问题。 本课中的Python程序，难度较大，可作为较高要求下的研习之用。 五、练习五、练习 人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊和一捆白菜，来到一条河边，河边只有一条 小船， 人每次过河最多只能带一样， 如果人不在现场， 狼就要吃羊， 羊就要吃菜。 他应该怎样安排过河呢？ 请完成下面的“树”结构分析图，帮他找到可行的过河方案。 提示：可约定对象在左岸用0表示，在右岸用1表示。 来源:学*科*网Z*X*X*K 要求：能以纸笔方式画出分析树得出结论即可。 （解答略） 六、课后作业：六、课后作业： 来源来源: :学科网学科网
