浙教版（2019）信息技术选修1 第四章 树 课件（3课时，22张PPT）

(共22张PPT)
选择性必修1《数据与数据结构》
第四章 树
4.1 树与二叉树
情境导入
演示组织关系为树结构的生活示例
学生列举树结构的生活实例
知识讲解
1.树的概念
树
左子树、右子树
2.树的度、节点的度
3.树的深度
4.根节点、分支节点、叶子节点
自主学习
小组讨论
2.若干个家庭一起组织自助游，准备阶段需要考虑旅游路线的规划、食宿安排以及旅途中各项娱乐活动的人员组队等问题。
如何用学过的数据结构知识来更好地帮助制订相关计划
知识讲解
1.二叉树的概念
2.二叉树的形态
自主学习
表述出“满二叉树”与“完全二叉树”的不同点与相同点？
知识讲解
1.二叉树的性质1
例1:画仅有一个节点的二叉树。
例2:画一棵高度大于3的非满二叉树。
例3:画一棵满二叉树。
自主学习
树的概念
二叉树的概念
满二叉树、完全二叉树
二叉树的性质
课堂小结
课堂作业
1.思考教材“问题与讨论”中的两个问题。
“问题与讨论”
1.如何管理计算机中的照片，使得浏览起来更加方便。
2. 从数据的组织处理效率来看，二叉树本质上是对数组和链表的一种折中处理，如何看待这种说法
4.2 二叉树的基本操作
情境导入
演示完全二叉树
演示非完全二叉树
如何存储完全二叉树与非完全二叉树？
知识讲解
1.数组形式建树
2.链表形式建树
3.二叉树的前序遍历
自主学习
小组讨论
已知前序遍历和后序遍历序列，能否唯一确定一棵二叉树？
4.3 抽象数据类型
知识讲解
1.数据类型
2.抽象数据类型
自主学习
4.3.2 抽象数据类型的描述
定义一个抽象数据类型，需要清晰地表述出各方面的形式要求（如操作的名字、参数的个数和类型等）和功能要求（希望这个操作完成什么样的计算或产生什么效果等)。这类对象的功能体现为一组可以对它们使用的操作。当然，还需要为这一抽象数据类型确定一个类型名。
4.3.3 抽象数据类型的作用
抽象数据类型主要体现了程序设计中问题分解、抽象和信息隐藏的特征。它把实际生活中的问题分解成多个规模较小且容易处理的问题，然后建立一个计算机能处理的数据模型，把每个功能模块作为一个独立单元，隐藏具体的实现过程，通过一次或多次的模块调用来实现整个问题的解决。
小组讨论
1. 如何描述一种抽象数据类型？
2.举例说明某种抽象数据类型的作用。
建树
二叉树的遍历
数据类型与抽象数据类型
抽象数据类型的描述及其作用
课堂小结
课堂作业
1.思考教材“问题与讨论”中的两个问题。