3.2数据与结构 第3课时课件-2021-2022学年高中信息技术教科版（2019）必修一

第三单元 认识数据 3.2 数据与结构 第3课时 树结构、图结构 学习目标 1. 了解树、图结构的基本概念及其特点。 2. 根据数据结构的特点，会选用合适的数据结构组织数据解决简单的问题。 阅读第59、60页“任务二 探究快递配送过程”之活动1 “了解快递派送线路”，完成第60页的连点成树。 一、课堂引入 一、数据类型 二、学习新知 1、概念：树结构是一种具有层次关系的非线性结构。 （一）树结构 2、特征：树是由n（n≥0）个节点组成的有限集合。若n = 0，则称为空树。 一、数据类型 任何一个非空树均满足以下两个条件： （1）仅有一个称为根的节点。 （2）当n>0时，其余节点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。 树结构 城市物流配送路线 一级快件集散分拨中心 二级公共配送中心 二级公共配送中心 共同配送点 共同配送点 共同配送点 共同配送点 共同配送点 共同配送点 想一想，生活中的树结构实例 一、数据类型 二、学习新知 1、树的结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图中数据元素 A、K、L 就是结点。 （一）树的常见概念 父结点（双亲结点）、子结点和兄弟结点：右图中（A）中的结点 B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子结点（也称“孩子结点”）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。 2、子树 子树：如下图，整棵树的根结点为结点 A，而如果单看结点 B、E、F、K、L 组成的部分来说，也是树，而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树。 单个结点也是一棵树，只不过根结点就是它本身 3、空树 如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。 2、结点的度和层次 对于一个结点，拥有的子树数（结点有多少分支）称为结点的度。 树的度是树内各结点的度的最大值。 结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。 一棵树的深度（高度）是树中结点所在的最大的层次。 3、有序树和无序树 如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之