4.2二叉树的基本操作教学设计-2025-2026学年浙教版高中信息技术选修一

| 7页
| 180人阅读
| 0人下载
普通

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

教学设计

课程基本信息

学科

信息技术

年级

高二

学期

秋季

课题

4.2二叉树的基本操作

教科书

书  名:选择性必修1 数据与数据结构

出版社:浙江教育出版社               出版日期:2019年12月

教学目标

1.掌握二叉树的两种建立方式。

2.熟练掌握二叉树的三种遍历方式。

教学内容

教学重点:

1. 用数组和链表实现对二叉树的建立。
2. 理解二叉树的前中后序三种遍历方式。
教学难点:

1.二叉树的三种遍历方式,了解规则并能实际上手操作。

教学过程

一、课堂导入

教师提问

  1. 通过知识回顾,区分两种二叉树进行问题导入。对于二叉树我们如何组织、存储和处理其节点信息?
  2. 提示学生:我们之前学过的数组和链表知识,可采用数组形式和链表形式存储节点信息。

 

学生活动

积极回顾知识,并对问题进行分析和思考。

 

二、二叉树的建立

教师活动

讲解基本知识点,引导学生利用数组对二叉树进行建立。

 

学生活动

学生认真听讲学习新知,并思考与动手,用数组实现对二叉树的建立。

1.数组实现

(1)完全二叉树:

page number 0

 

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


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

从二叉树的根节点开始,按从上而下、自左往右的顺序对n个节点进行编号,根节点的编号为0,最后一个节点的编号为n–1。然后依次将二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一对应。

 

(2)非完全二叉树:

对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示。

然后将补全后的完全二叉树,从它的根节点开始,按从上而下、自左往右的顺序对n个节

点进行编号,根节点的编号为0,最后一个节点的编号为n–1。依次把完全二叉树中原二叉树的节点用一维数组元素的各个元素来表示,节点编号与数组的下标一一对应。

教师活动

提出思考题,数组表示二叉树有什么优缺点?

学生活动

学生认真思考数组实现二叉树的优缺点。

 

(3)思考讨论:用数组表示二叉树,在计算机中是否可取?

对于完全二叉树而言,一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说,采用一维数组表示时,结构虽然简单,却容易造成存储空间的浪费。如上图所示,一个深度为k且只有k个节点的树需要如上图乙所示2k –1个节点的存储空间才能表示出来。

 

page number 1

 

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


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

教师活动

讲解基本知识点,引导学生利用链表对二叉树进行建立。

学生活动

学生认真听讲学习新知,并思考与动手,用链表实现对二叉树的建立。

 

2.链表实现

二叉树也可以采用链表来实现,用任意一组存储单元来存储二叉树的节点,用指向节点的指针来表示节点之间的关系。

由于二叉树的节点可能有两个孩子,即左孩子和右孩子,因此二叉树的节点至少需要3个域:一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子,这两个指针分别称为左指针和右指针,这样得到的链表也称为二叉链表。

教师活动

提出问题,让学生巩固知识。

学生活动

学生认真思考动手,完成已知数组,还原二叉树的操作。

 

  1. 课堂小练

前面学的用数组建立二叉树,现在已知数组,我们就可以根据数组,一层层的把二叉树

page number 2

 

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


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