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