山东省枣庄市第八中学东校区高中信息技术教科版（2019）必修一 3.2数据与结构学案（第二课时

3.2 数据与结构(第二课时) 【学习目标】 了解树、图结构的基本概念及其特点。 根据数据结构的特点，会选用合适的数据结构组织数据解决简单的问题。 【教学重点】数据结构中的树结构和图结构。 【教学难点】数据结构中的树结构和图结构。 【教学过程】 一、探究引入 阅读第59、60页“任务二 探究快递配送过程”之“活动1 了解快递派送线路”，完成第60页的连点成树（见下图）。 二、树结构 1、树的递归定义： 树是由n（n≥0）个节点组成的有限集合。若n = 0，则称为空树。任何一个非空树均满足以下两个条件： （1）仅有一个称为根的节点。 （2）当n>0时，其余节点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。如下图所示树的结构：（图1） [来源:学科网] 2、树的常见概念： （小组讨论或网络搜索了解树结构的定义） 1）树的结点： 结点： 父结点（双亲结点）、子结点和兄弟结点 树根结点（简称“根结点”） 叶子结点 [来源:学_科_网] 2）子树与空树[来源:学.科.网] 子树： 空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。 3）结点的度和层次 对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）。 结点的层次 4）有序树和无序树 如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。 5）森林：[来源:Z,xx,k.Com] 由 m（m >= 0）个互不相交的树组成的集合被称为森林。 3、二叉树： 在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。二叉树是树的特殊一种，具有如下特点： 1、每个结点最多有两颗子树，结点的度最大为2。 2、左子树和右子树是有顺序的，次序不能颠倒。 3、即使某结点只有一个子树，也要区分左右子树。 二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。 【说一说】社会、工作、生活中的树形结构实例： ①树结构之行政区划 （程序下发至学生机） 三、图结构 图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点