4.2二叉树的基本操作教学设计-2025-2026学年浙教版高中信息技术选修一
教学设计
学科 | 信息技术 | 年级 | 高二 | 学期 | 秋季 |
课题 | 4.2二叉树的基本操作 | ||||
教科书 | 书 名:选择性必修1 数据与数据结构 出版社:浙江教育出版社 出版日期:2019年12月 | ||||
教学目标 | |||||
1.掌握二叉树的两种建立方式。 2.熟练掌握二叉树的三种遍历方式。 | |||||
教学内容 | |||||
教学重点: 1. 用数组和链表实现对二叉树的建立。 1.二叉树的三种遍历方式,了解规则并能实际上手操作。 | |||||
教学过程 | |||||
一、课堂导入 教师提问
学生活动 积极回顾知识,并对问题进行分析和思考。
二、二叉树的建立 教师活动 讲解基本知识点,引导学生利用数组对二叉树进行建立。
学生活动 学生认真听讲学习新知,并思考与动手,用数组实现对二叉树的建立。 1.数组实现 (1)完全二叉树: | |||||
学科网(北京)股份有限公司
从二叉树的根节点开始,按从上而下、自左往右的顺序对n个节点进行编号,根节点的编号为0,最后一个节点的编号为n–1。然后依次将二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一对应。
(2)非完全二叉树: 对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示。 然后将补全后的完全二叉树,从它的根节点开始,按从上而下、自左往右的顺序对n个节 点进行编号,根节点的编号为0,最后一个节点的编号为n–1。依次把完全二叉树中原二叉树的节点用一维数组元素的各个元素来表示,节点编号与数组的下标一一对应。 教师活动 提出思考题,数组表示二叉树有什么优缺点? 学生活动 学生认真思考数组实现二叉树的优缺点。
(3)思考讨论:用数组表示二叉树,在计算机中是否可取? 对于完全二叉树而言,一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说,采用一维数组表示时,结构虽然简单,却容易造成存储空间的浪费。如上图所示,一个深度为k且只有k个节点的树需要如上图乙所示2k –1个节点的存储空间才能表示出来。
|
学科网(北京)股份有限公司
教师活动 讲解基本知识点,引导学生利用链表对二叉树进行建立。 学生活动 学生认真听讲学习新知,并思考与动手,用链表实现对二叉树的建立。
2.链表实现 二叉树也可以采用链表来实现,用任意一组存储单元来存储二叉树的节点,用指向节点的指针来表示节点之间的关系。 由于二叉树的节点可能有两个孩子,即左孩子和右孩子,因此二叉树的节点至少需要3个域:一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子,这两个指针分别称为左指针和右指针,这样得到的链表也称为二叉链表。 教师活动 提出问题,让学生巩固知识。 学生活动 学生认真思考动手,完成已知数组,还原二叉树的操作。
前面学的用数组建立二叉树,现在已知数组,我们就可以根据数组,一层层的把二叉树 |
学科网(北京)股份有限公司