1、第三单元 认识数据学习重点：学习重点：1.了解树、图结构的基本概念及其特点课堂导入课堂导入阅读第阅读第59、60页页“任务二任务二 探究快递配送过程探究快递配送过程”之之“活动活动1 了解快递派送线路了解快递派送线路”，完成第，完成第60页的连点成树页的连点成树（见下图）。（见下图）。快递公司物流配送体系快递公司物流配送体系树是一种具有层次关系的非线性数据结构关系：一对多一对多树的概念树的概念树的节点树的节点根节点：根节点：每一个非空树都有且只有一个被称为根的结点。图 中结点A就是整棵树的根结点。树根的判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。叶子结点：叶子结点：如果
2、结点没有任何子结点，那么此结点称为叶子结点。如图中结点 E、F、K、L、M、C、H、I、J 都是这棵树的叶子结点。父结点、子结点和兄弟结点：（节点与节点之间的关系）父结点、子结点和兄弟结点：（节点与节点之间的关系）对结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点，而 B、C、D 都是 A 结点的子结点。对于 B、C、D 来说，它们都有相同的父结点A，所以它们互为兄弟结点。（1）指出上图中树的根节点、叶子节点；（2）H和J是什么关系？H和D呢？H和G呢？练习时刻练习时刻 ：如图，整棵树的根结点为结点 A，而如果单看结点 B、E、F、K、L 组成的部分来说，也是棵树，而且节点 B 为
3、这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树；同样，结点 E、K、L 构成的也是一棵子树，根结点为 E。注意：单个结点也是一棵树，只不过根结点就是它本身。图中结点 K、L、F 等都是树，且都是整棵树的子树。知道了子树的概念后，树也可以这样定义：树是由根结点和若干棵子树构成的。子树与空树子树与空树 空树：空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能有交集。例如，图中除了根结点 A，其余元素又各自构成了三个子树，根结点分别为 B、C、D，这三个子树相互之间没有相同的结点。如果有，就破
4、坏了树的结构，不能算做是一棵树。子树与空树子树与空树 树是由n（n0）个节点组成的有限集合。若n=0，则称为空树。任何一个非空树均满足以下两个条件：（1）仅有一个称为根的节点。（2）当n0时，其余节点可分为m（m0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。树的定义树的定义图结构是由一组节点（称为顶点顶点）和一组节点间的连线（称为边边或弧弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多多对多的关系。图的概念图的概念阅读第阅读第62、63页页“任务二任务二 探究快递配探究快递配送过程送过程”之之“活动活动3 规划取快递最快路线规划取快递最快路线”。阅读第阅读第62、63页页“任务二任务二 探究快递配探究快递配送过程送过程”之之“活动活动3 规划取快递最快路线规划取快递最快路线”。【朴素算法】穷举遍历，依次列出所有可能走法如下图。分析过程利用树结构清晰地实现不重复、不遗漏地列举所有做法，更利于得到最优解。一对一一对多多对多排队（上车、过马路、付款）、医院就诊电子牌上的就诊队列行政区划、书的目录结构、磁盘文件存储结构、注册表结构全国航运图、铁路运输图、高速公路网课堂小结课堂小结Homework：练习时刻练习时刻练习时刻练习时刻Thanks
