4.2 二叉树的基本操作 教学设计2026-2027学年浙教版高中信息技术选择性必修1

| 6页
| 18人阅读
| 0人下载
普通

学科网 zxxk.com学科网 zxxk.com

4.2 二叉树的基本操作 教学设计

课题

4.2 二叉树的基本操作

教材版本

浙教版(2019)选择性必修1《数据与数据结构》

所在单元

第四章 树

课型

新授课

课时安排

2课时(80分钟)

授课对象

高中二年级学生

授课教师

 

授课时间

 

教材分析

本节是第四章“树”的第二节,承接 4.1 节树与二叉树的概念,学习二叉树在计算机中的存储(建立)与访问(遍历)两类基本操作。教材先解决“二叉树怎样存进计算机”的问题,介绍两种建立方式:一是数组实现——完全二叉树从根节点开始,按从上而下、自左往右的顺序对 n 个节点编号,根节点编号为 0、最后一个节点编号为 n-1,节点编号与数组下标一一对应;非完全二叉树先补全为一棵完全二叉树,补上的节点及分支用虚线表示,存储时对应位置空缺,并引导学生讨论“数组表示一般二叉树时,一个深度为 k 且只有 k 个节点的树需要 2^k-1 个节点的存储空间、容易造成空间浪费”的不足;二是链表实现——二叉树的节点至少需要三个域,一个数据域和两个指针域,两个指针域分别指向节点的左孩子和右孩子,这样得到的链表称为二叉链表;教材还给出用列表(list)构造二叉树的方法,空树用 None 表示,非空二叉树用包含三个元素的列表 [d, l, r] 表示。接着教材解决“怎样访问每一个节点”的问题,给出遍历的概念——按照一定的规则和次序访问二叉树中的所有节点,使每个节点都被访问一次且仅被访问一次,并依次讲解前序遍历(根左右)、中序遍历(左根右)与后序遍历(左右根)的规则,强调对二叉树的任意一个局部都必须遵守同一遍历规则;最后通过表达式树说明中序遍历得到中缀表达式、后序遍历得到后缀表达式(也称逆波兰表达式)的应用。本节上承 4.1 节的概念,下启 4.3 节抽象数据类型与后续算法,是学生从“认识二叉树”走向“操作二叉树”的关键一课,教学中应多用图示、动画与上机实践,帮助学生把抽象的存储与访问过程变得可见。

一、教学目标

1.信息意识:能从“二叉树该怎样存进计算机”“该按什么顺序访问每一个节点”等实际问题出发,认识到存储方式与访问顺序对数据处理的影响;在比较数组表示与链表表示的优劣中,体会根据数据的实际特点选择合适存储结构的意义,养成有意识地组织数据的习惯。

2.计算思维:理解二叉树的两种建立方式(数组实现与链表实现)以及用列表(list)构造二叉树的方法,能说出完全二叉树编号与数组下标一一对应的关系、二叉链表page number 0

 

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


学科网 zxxk.com学科网 zxxk.com

节点“一个数据域+两个指针域”的组成;理解二叉树遍历的概念,掌握前序(根左右)、中序(左根右)、后序(左右根)三种遍历规则,能写出给定二叉树的三种遍历序列;能体会把非线性结构转化为线性序列的抽象与建模方法,初步形成递归的思维方式。

3.数字化学习与创新:能借助图示、动画演示与 Python 编程工具完成二叉树的建立与遍历,能在上机实践中用代码验证自己写出的遍历序列;能与同伴合作探究,用列表表示二叉树并比较三种遍历的不同结果。

4.信息社会责任:在表达式树、文件目录等实例中体会二叉树在信息社会中的广泛应用,理解良好的数据组织方式与访问规则对信息处理效率的意义;在存储方式的比较与程序调试的过程中养成严谨、规范的操作习惯。

5.合作育人:通过小组讨论、上机协作、成果展示等活动,培养团队协作能力、交流表达能力与批判性思维。

二、教学重点与难点

教学重点:二叉树的两种建立方式(数组实现与链表实现);二叉树前序、中序、后序三种遍历规则及遍历序列的确定。

教学难点:非完全二叉树用数组表示时“补全后存储位置空缺”的理解;二叉树遍历的递归思想(对任意一个局部都遵守同一规则);由数组表示还原二叉树以及表达式树中遍历序列与数学表达式的对应。

三、教学方法与教学准备

教学方法:情境导入法、直观演示法、对比探究法、任务驱动法、小组合作法。

教学准备:教师准备多媒体课件(含数组表示二叉树与二叉链表结构示意图、三种遍历的动态演示、表达式树示例等)、Python 编程与运行环境、课堂任务单;学生准备教材、练习本与笔,复习 4.1 节树与二叉树的概念以及数组、链表的相关内容,思考“一棵二叉树怎样才能存进计算机,又该按什么顺序访问它的每一个节点”。

四、教学过程

教学环节

教师活动

学生活动

设计意图

情境导入(5分钟)

1.屏幕展示 4.1 节学过的一棵二叉树,提问:我们已经认识了二叉树的样子,可是计算机里并没有“树”这种形状的存储空间——这棵二叉树该怎样存进计算机?存放在哪里?又该按什么顺序访问它的每一个节点?

2.引导学生回忆:前面学过数组(连续存储)和链表(链式存储),能不能用它们来存放二叉树的节点?

观察二叉树,思考“怎样存”和“按什么顺序访问”两个问题;回顾数组与链表的存储特点,尝试说出自

由 4.1 节遗留的问题切入,把“建立”与“遍历”作为本节的驱动问题,让学生带着明

page number 1

 

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


学科网 zxxk.com学科网 zxxk.com

 

3.顺势提出本节要解决的两个问题——二叉树的建立(存储)与二叉树的遍历(访问),引出本节课题——4.2 二叉树的基本操作。

己的想法,在讨论中感到“非线性结构也需要恰当的组织方式”。

确的问题意识进入新课;同时唤起对数组、链表等旧知的回忆,为学习两种存储方式做好铺垫。

探究一 二叉树的建立:数组实现与链表实现(20分钟)

1.讲解数组实现。以一棵完全二叉树为例:从根节点开始,按从上而下、自左往右的顺序对 n 个节点编号,根节点编号为 0,最后一个节点编号为 n-1,节点编号与数组下标一一对应,依次把二叉树的节点存入一组连续的一维数组元素。

2.讲解非完全二叉树的数组实现:先把它补全为一棵完全二叉树,补上的节点及分支用虚线表示,存储时这些位置空缺,其他节点的存储位置参照完全二叉树确定。

3.组织学生思考讨论:用数组表示二叉树有什么优缺点?引导学生发现——完全二叉树用一维数组表示既简单又节省存储空间,而一般的二叉树(一个深度为 k 且只有 k 个节点的树需要 2^k-1 个节点的存储空间)容易造成存储空间的浪费。

4.讲解链表实现:用任意一组存储单元存放节点,节点至少需要三个域——一个数据域和两个指针域,两个指针域分别指向节点的左孩子和右孩子(左指针、右指针),这样得到的链表称为二叉链表;再介绍用列表(list)构造二叉树的方法:空树用 None 表示,非空二叉树用包含三个元素的列表 [d, l, r] 表示,d 为根节点元素,l 与 r 为左右子树。

5.结合课堂任务单,让学生把一棵给定的二叉树分别用数组编号与二叉链表的方式表示出来。

听讲并对照图示理解两种建立方式;在任务单上给一棵完全二叉树编号并写出对应的数组;尝试把一棵非完全二叉树补全后写出各节点的存储位置;动手画出二叉链表,写出节点的数据域与两个指针域;讨论并说出数组表示与链表表示各自的优缺点。

把“建立”这一抽象问题落到学生熟悉的数组与链表两种结构上,借助编号、补全、画图等活动让存储过程看得见;通过优缺点的讨论让学生自己发现数组表示一般二叉树的局限,体会“按数据特点选择存储结构”的思想。

探

1.给出遍历的概念:按照一定的规则和次

观察动画

用“根

page number 2

 

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。