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）树的结点：）树的结点： 结点结点： 父结点（双亲结点）、子结点和兄弟结点父结点（双亲结点）、子结点和兄弟结点 树根结点（简称树根结点（简称“根结点根结点”） 叶子结点叶子结点来源:学_科_网 2 2）子树与空树）子树与空树 来源来源: :学学. .科科. .网网 子树：子树： 空树：空树
3、：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。 3 3）结点的度和层次）结点的度和层次 对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（结点的度（DegreeDegree）。 结点的层次结点的层次 4 4）有序树和无序树）有序树和无序树 如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为 无序树。 5 5）森林：）森林： 来源来源:Z,xx,k.Com:Z,xx,k.Com 由 m（m = 0）个互不相交的树组成的集合被称为森林。 3 3、二叉树：、二叉树： 在日常的应用中， 我们讨论和用的更多的是树的其中一种结构， 就是二叉树。
4、 二二叉树叉树是树的特殊一种， 具有如下特点： 1、每个结点最多有两颗子树，结点的度最大为2。 2、左子树和右子树是有顺序的，次序不能颠倒。 3、即使某结点只有一个子树，也要区分左右子树。 二叉树是一种比较有用的折中方案，它添加，删除元素都很快， 并且在查找方面也有很多的算法优化， 所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常 有用。 【说一说】社会、工作、生活中的树形结构实例： 树结构之行政区划树结构之行政区划 （程序下发至学生机）（程序下发至学生机） 三、图结构三、图结构 图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一
5、种数据结构。图 结 构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。 1 1、常见的概念、常见的概念 1）顶点（顶点（vertex）：）： 2）边（边（edge）：）： 3）无向图无向图 如果一个图结构中，所有的边都没有方向性， 那么这种图便称为无向图。 （图二图二 无向图无向图） 4）有向图有向图 一个图结构中，边是有方向性的，那么这种图就称为有向图。 图三图三 有向图有向图 【活动】规划取快递最快路线 【朴素算法】穷举遍历，依次列出所有可能走法如图3.2.10。将图中每个节点进行编号， 编号互不相同：如作为根节点的“家”编号为“X”,其3个子节点（快递门店A，快
6、递门店B， 快递门店C）分别编号为“A” “B” “C”，详见下图。 【算法演示 1】求解最短时间（基于图 3.2.10 的分析树）来源:学&科&网 Z&X&X&K 【算法演示 2】求解最短时间（直接对图 3.2.9 进行深度优先遍历） 练习练习 人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊和一捆白菜，来到一条河边，河边只有一条 小船， 人每次过河最多只能带一样， 如果人不在现场， 狼就要吃羊， 羊就要吃菜。 他应该怎样安排过河呢？ 请完成下面的“树”结构分析图，帮他找到可行的过河方案。 提示：可约定对象在左岸用0表示，在右岸用1表示。 要求：能以纸笔方式画出分析树得出结论即可。 （解答略） 六、课后作业：六、课后作业：
