山东省枣庄市第八中学东校区高中信息技术教科版（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）树的结点： 结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图 1中，数据元素 A 就是一个结点； 父结点（双亲结点）、子结点和兄弟结点：对于图 1（A）中的结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子结点（也称“孩子结点”）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。 树根结点（简称“根结点”）：每一个非空树都有且只有一个被称为根的结点。图 1（A）中，结点A就是整棵树的根结点。树根的判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。 叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如图 1（A）中，结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。 2）子树与空树 子树：如图 1（A）中，整棵树的根结点为结点 A，而如果单看结点 B、E、F、K、L 组成的部分来说，也是棵树，而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树；同样，结点 E、K、L 构成的也是一棵子树，根结点为 E。 注意：单个结点也是一棵树，只不过根结点就是它本身。图 1（A）中，结点 K、L、F 等都是树，且都是整棵树的子树。 知道了子树的概念后，树也可以这样定义：树是由根结点和若干棵子树构成的。 空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。