高中二年级信息技术二叉树的基本操作及抽象数据类型教学设计

高中二年级信息技术二叉树的基本操作及抽象数据类型教学设计一、教学内容分析本课选自浙教版（2019）高中信息技术选修1《数据与数据结构》第四章第二节，是树结构单元的核心课时。学生此前已经学习了二叉树的概念、性质与存储表示，本节则要从"是什么"走向"怎么用"，完成二叉树的建立、遍历以及抽象数据类型的定义三项任务。教材以家族谱系、表达式求值等情境为线索，把二叉树的四种遍历方式与递归思想紧密结合，最后落脚于用抽象数据类型（ADT）描述二叉树的操作集合，为学生后续学习二叉排序树、哈夫曼树铺设台阶。从学科核心素养看，本课重点落在计算思维与数字化学习两个维度：学生需要把现实问题抽象为树形结构，用递归方式拆解问题，并用代码实现操作；同时借助在线评测与可视化工具，体验"抽象—建模—实现—验证"的完整过程。二、学情分析授课对象为高二年级选修本模块的学生。他们已经掌握Python基本语法、函数定义与递归初步，也学习了线性表的顺序存储与链式存储。学习难点集中在三处：其一，递归遍历的调用次序与学生习惯的单线程顺序思维存在冲突，容易把"先序、中序、后序"混为一谈；其二，链式存储中"结点—指针—子树"的指代关系抽象程度高，部分学生画图能力弱，导致代码改不出错因；其三，抽象数据类型的概念首次明确出现，学生容易把ADT误认为"就是写个类"，忽视接口与实现分离的思想。针对上述情况，本课采用"具身操作先行、代码还原跟进、抽象封装提升"的路径：先让学生在棋盘上摆棋子走遍历路线，再看可视化动画，最后写代码并封装为类。三、教学目标其一，能说出二叉树先序、中序、后序、层序遍历的访问规则，给定一棵不超过七层的二叉树，能正确写出四种遍历序列。其二，能基于递归思想编写先序遍历函数，并在教师给出的框架上独立完成中序、后序遍历，理解递归出口与递归体的作用。其三，能用二叉链表结构描述二叉树的存储方式，用列表或类的方式实现结点的定义，掌握"数据域＋左右孩子指针"的建模方法。其四，能从接口角度描述二叉树的抽象数据类型，说出创建树、取根、访问左子树、遍历等操作应包含的要素，体会ADT把"做什么"与"怎么做"分离的思想。其五，在小组协作构建哈夫曼编码雏形或家族谱系树的活动中，感受树结构处理分层信息的优势，形成用合适结构解决真实问题的意识。四、教学重点与难点教学重点是二叉树的四种遍历方式及递归实现。教学难点是递归执行次序的理解，以及抽象数据类型的定义方法。突破策略有三：一是用"走迷宫式"的图示法标注访问时机，把先序理解为"每次新到一结点先标记"，中序理解为"从左子树回来的路口标记"，后序理解为"结点将被放弃时标记"；二是借助可视化网站逐帧观察递归栈的变化，让"看不见的保护现场与恢复现场"显性化；三是通过对比手写函数版与类封装版代码，引出ADT定义的通用格式。五、教学准备硬件网络机房、Python3.x环境、教师用投影；磁吸式二叉树结点道具一套；学习任务单每生一份，含三道遍历填空、一道画树题、一道ADT格式填空；可视化网址提前写入任务单二维码。六、教学过程（一）情境导入：一张族谱怎么存进计算机（约5分钟）上课伊始，教师展示某家族四代人的族谱照片，提出问题："这张族谱里每个人的'左孩子'和'右孩子'并没有现实含义，但如果我们规定长子在左、次子在右，它就成了一棵二叉树。计算机要从这张树上快速找出某人的所有祖先、或者按辈分逐代输出名字，它得先会两件事：把树存进去，把树走出来。"板书两个关键词：存储、遍历。教师追问："数组能不能存这棵树？"学生很快回忆起上节课的顺序存储，教师顺势指出：当树接近满二叉树时顺序存储效率高，但现实中大多数树形状不规则，空位浪费严重，所以链式存储才是普遍方案。由此引入结点结构：每个结点包含数据域、左孩子指针、右孩子指针。教师在大屏上给出结点定义代码，边写边解释含义：classNode:def__init__(self,data):self.data=dataself.left=Noneself.right=None提问："建一棵只有三个结点的树，需要几行代码？"请一名学生到讲台前用上述类写出根结点加左右孩子的建立过程。学生完成后，教师用鼠标演示改变某个指针后树形状的变化，强调"指针就是父子关系本身"。（二）新知探究一：遍历的四种规则（约12分钟）1.具身操作每组领取一套磁吸结点，在黑板上摆出一棵指定的二叉树（根A，左子树B、D、E，右子树C、F，共六结点）。任务单要求组内一人扮演"遍历者"，手指沿树外沿画一条闭合路线，规定每当手指首次经过某结点时记录一个"①"，第二次经过记录"②"，第三次记录"③"。三分钟后，各组分享发现：所有结点的①按时间先后排列，得到的是A、B、D、E、C、F；②的排列是D、B、E、A、C、F；③的排列是D、E、B、F、C、A。教师揭示：这三种次序正是先序、中序、后序，区别仅在于"访问根的时机"——先序是到先得，中序是从左边回来，后序是彻底离开之前。2.规则归纳教师板书三条规则，并用颜色区分根（R）、左子树（L）、右子树（R'）的相对位置：先序为R→L→R'，中序为L→R→R'，后序为L→R'→R。随即提问："为什么是'递归'的规则？"学生回答：左右子树本身也是二叉树，规则要一层套一层地执行下去。教师强调：遍历规则天然是递归定义的，这决定了代码也自然是递归的。3.层序遍历教师补充提问："族谱按辈分逐代输出怎么办？"学生尝试后发现沿外沿走的办法不适用。教师引导出队列思想：根先入队，出队时访问并把左右孩子入队，重复直到队空。学生在任务单上手工模拟一遍六结点树的层序过程，得到A、B、C、D、E、F，与族谱按辈分输出的需求吻合。（三）新知探究二：递归代码的实现与复盘（约12分钟）4.教师示范先序遍历教师现场敲出函数框架，故意先漏掉递归出口，运行后让学生观察报错，引出"递归必须有出口"：defpreorder(root):ifrootisNone:returnprint(root.data,end='')preorder(root.left)preorder(root.right)教师强调三行代码与规则R→L→R'的一一对应："写遍历代码不需要背，把规则翻译过来就行。"5.学生独立改写学生在自己的电脑上把先序函数改造成中序、后序版本，只调整三行核心语句的顺序。教师巡视，发现共性问题：有学生把print语句挪进if内部写错缩进；有学生忘记递归调用参数是root.left而非left。点评时教师指出："函数内部看不到整棵树，它只认识传进来的这一个结点，这就是递归的视野。"6.可视化复盘教师打开递归可视化网页，逐帧演示中序遍历一棵六结点树时调用栈的压入与弹出。每到一次函数返回，暂停提问："此时程序为什么知道该回到哪？"学生答出"栈里记录了待恢复的现场"。教师补充：这一点与课本中递归算法的执行过程相互印证，遍历的时间代价是每个结点恰被访问常数次，故为O(n)，递归栈深度最坏等于树高。（四）新知探究三：从函数到抽象数据类型（约8分钟）教师展示两份代码：左边是散落的建树语句与三个遍历函数，右边是把它们封装为BinaryTree类的版本。提问："右边多做了什么？"学生答出：把数据和操作打包，使用者只需调接口，不必关心指针怎么连。教师顺势给出二叉树抽象数据类型的通用描述框架，学生对照任务单填空：ADT二叉树{数据对象：若干结点的有限集合，一个根结点，每个结点最多有两棵互不相交的子树；基本操作：CreateTree（建树）、IsEmpty（判空）、Root（取根）、LeftChild／RightChild（取孩子）、Preorder／Inorder／Postorder／Levelorder（遍历）、Destroy（销毁）}教师强调ADT的意义在于"只规定做什么，不规定怎么做"：同一套接口，底层用数组也行、用链表也行，今天写的类只是其中一种实现。这个思想是数据结构课程的主线，也是从"会写代码"走向"会设计"的分水岭。（五）巩固提升：双向练习（约6分钟）第一题，给出先序序列A、B、D、E、C、F和中序序列D、B、E、A、C、F，要求画出原树。学生小组讨论后汇报：先序首元素定根，到中序中找到根，左边的是左子树、右边的是右子树，递归处理即可重建整棵树。教师指出这正是先序与中序唯一确定一棵二叉树的原因，并追问"先序加后序行不行"，留给学有余力的学生课后思考。第二题，算术表达式"3+4×5"建立表达式二叉树（根为＋，右子树根为×），写出其先序、中序序列，体会前缀式与中缀式的对应关系，埋下后续课程的伏笔。（六）课堂小结（约2分钟）师生共同完成板书框架：存储上，二叉链表以"数据＋双指针"刻画结点关系；操作上，四种遍历规则对应四段递归代码，本质区别在访问根的时机；理念上，抽象数据类型把接口与实现分离，是设计数据结构的标准姿势。七、作业设计基础层：补全任务单剩余遍历练习；完成层序遍历的代码实现（提示用列表模拟队列）。提高层：编写函数统计二叉树的结点总数与叶子结点数，体会"任何对树的批量处理都是遍历的变体"。拓展层：尝试用先序加中序重建任意二叉树的程序，下节课选两组展示。八、板书设计主板书分三区：左侧"存储"区画结点结构图