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

3.2《数据与结构》（第2课时）任务单
学习目标：
1.掌握树结构的定义和特点。
2.掌握图结构的定义和特点。
3.理解队列、树、图结构的区别。
活动1.家谱中“隐藏”的数据结构
同学们对于四大名著之一的《红楼梦》并不陌生，里面主要讲述了四大家族的兴衰历程。在《红楼梦》中，主要的故事情节都是以贾家作为主线贯穿的。贾家的人物关系也是错综复杂。
但是，如果用我们所学的知识，将贾家的家谱稍作整理，立马变得清晰明确……
思考.
《红楼梦》中贾家的人物关系显然不能用线性结构来表示，那这是一种什么数据结构呢？它具备什么特点？
温故知新：线性数据结构
结构类型 数据节点之间的关系 生活中相应结构应用举例
栈（线性）
队列（线性）
知识点1：树结构
树结构是一种具有____________________________________________。
树是由n个节点组成的有限集合。n=0为空树。
任何一个非空树均满足以下两个条件：
1.仅有一个称为根的节点；
2.当n>0时，其余节点可分为m个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。
树结构中，数据元素之间是_____________的关系。
如上图，节点A为____________；BCD为A的子树的根节点；EFG是B子树的根节点；B是EFG的______________。
活动2 清明节旅游路线规划
清明节假期临近，小明想利用其中一天假期去几个景点旅游，由于景点分布于不同位置，为了节约时间，减少在路上时间浪费，请你帮他规划一下最优旅游路线。
思考.
下图是各景点的分布位置图，如果小明从家里出发，选择哪条路线是最佳旅游路线呢？
知识点2：图结构
图结构是由一组节点（称为顶点）和一组节点间的连线（称为边）构成的一种数据结构。
图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是______________的关系。
如上图，标号是1的顶点与两条边相连，顶点4与2,8,9相连。
思考.
在旅游路线图中，我们如何根据路线选择最优路径呢？
比一比：数据结构的比较
结构类型 数据节点之间的关系 生活中相应结构应用举例
队列（线性）
树
图
上机练习：人、狼、羊、菜过河问题
有一个人带着一只狼、一只羊、一捆白菜，来到一条河边。河边只有一条小船，人每次过河最多只能带一样，如果人不在现场，狼就要吃羊，羊就要吃菜。他应该怎样安排过河？
优秀的你：这节课学会了什么？还有什么疑惑？给自己的表现打个分吧！