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

教学设计 课程基本信息 学科 信息技术 年级 高二 学期 秋季 课题 4.2二叉树的基本操作 教科书 书 名：选择性必修1 数据与数据结构 出版社：浙江教育出版社 出版日期：2019年12月 教学目标 1.掌握二叉树的两种建立方式。 2.熟练掌握二叉树的三种遍历方式。 教学内容 教学重点： 1. 用数组和链表实现对二叉树的建立。 2. 理解二叉树的前中后序三种遍历方式。 教学难点： 1.二叉树的三种遍历方式，了解规则并能实际上手操作。 教学过程 一、课堂导入 教师提问 1. 通过知识回顾，区分两种二叉树进行问题导入。对于二叉树我们如何组织、存储和处理其节点信息？ 2. 提示学生：我们之前学过的数组和链表知识，可采用数组形式和链表形式存储节点信息。 学生活动 积极回顾知识，并对问题进行分析和思考。 2、 二叉树的建立 教师活动 讲解基本知识点，引导学生利用数组对二叉树进行建立。 学生活动 学生认真听讲学习新知，并思考与动手，用数组实现对二叉树的建立。 1.数组实现 （1）完全二叉树： 从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 （2）非完全二叉树： 对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。 然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左往右的顺序对n个节 点进行编号，根节点的编号为0，最后一个节点的编号为n–1。依次把完全二叉树中原二叉树的节点用一维数组元素的各个元素来表示，节点编号与数组的下标一一对应。 教师活动 提出思考题，数组表示二叉树有什么优缺点？ 学生活动 学生认真思考数组实现二叉树的优缺点。 （3） 思考讨论：用数组表示二叉树，在计算机中是否可取？ 对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。如上图所示，一个深度为k且只有k个节点的树需要如上图乙所示2k –1个节点的存储空间才能表示出来。 教师活动 讲解基本知识点，引导学生利用链表对二叉树进行建立。 学生活动 学生认真听讲学习新知，并思考与动手，用链表实现对二叉树的建立。 2.链表实现 二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。 由于二叉树的节点可能有两个孩子，即左孩子和右孩子，因此二叉树的节点至少需要3个域：一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针，这样得到的链表也称为二叉链表。 教师活动 提出问题，让学生巩固知识。 学生活动 学生认真思考动手，完成已知数组，还原二叉树的操作。 3. 课堂小练 前面学的用数组建立二叉树，现在已知数组，我们就可以根据数组，一层层的把二叉树画出来。然后找到节点D的右孩子节点为G。 教师活动 讲解基本知识点，引导学生对二叉树进行遍历。 学生活动 学生认真听讲学习新知并思考，与老师一起进行二叉树的遍历。 三、二叉树的遍历 在完成二叉树的建立操作后，就可以对二叉树的各个节点进行访问，即遍历操作。 概念：按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。 1.前序遍历（根左右） 规则：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。 2.中序遍历（左根右） 规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。 3.后序遍历（左右根） 规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。 如果选取其中一种遍历规则对二叉树进行遍历，对于二叉树的左右子树，也需遵守该遍历规则，即二叉树的任意一个局部都必须遵守该遍历规则。对一棵二叉树进行前序遍历时，根节点总是处于遍历序列之首；中序遍历时根节点位置居中，左子树的所有节点都在其左边，右子树所有节点都在其右边；后序遍历时根节点位置在最后，其所有节点都在其左边。 4.课堂小练 对上图的二叉树实行中序遍历，将得到遍历序列：8 * ( 3 - 2 ) + 4，即人们平时习惯书写的数学表达式，也称为中缀表达式。 如果对图中二叉树实行后序遍历，那么得到遍历序列：8 3 2 - * 4 +，称为后缀表达式（也称逆波兰表达式）。 由于中缀表达式要将运算符放在两个操作数中间，并且在许多情况下为了确定运算顺序，括号是必不可少的。而书写后缀表达式时，因为采用了运算符紧跟在两个操作数之后的方法，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右依序完成计算，并方便求得结果。 教师活动 提出问题，引导学生们积极思考。 学生活动 学生认真思考与尝试，进行讨论。 5.探讨与讨论 已知前序和后序遍历序列，能否唯一确定一棵二叉树？ 学生回答：不能，比如说前序遍历序列AB和后序遍历序列BA，我们就可以生成如上图两棵树。 教师指导：当二叉树中某个节点仅仅只有一个子树节点的时候，其前序和后序遍历序列不能具体确定是左右子树的那一个。 四、课堂小结 1.二叉树的建立 （1）数组实现 ①完全二叉树 ②非完全二叉树 （2）链表实现 2.二叉树的遍历 （1）前序遍历 （2）中序遍历 （3）后序遍历 五、课后作业 思考如何使用Python实现二叉树的建立和遍历？ 下节实践课将进行程序编写与调试运行。 学科网（北京）股份有限公司 $