高中二年级信息技术选择性必修1《用二叉树排序》教学设计

高中二年级信息技术选择性必修1《用二叉树排序》教学设计一、教学背景分析本课选自教科版（2019）高中信息技术选择性必修1《数据与数据结构》第六章"数据的排序"第二课时。学生在必修模块中已经掌握顺序查找、二分查找和冒泡排序的基本思想，在第五章学习了线性结构之后，本章首次接触树形结构。二叉排序树（二叉查找树）是连接"树的认识"与"高效排序"的关键节点，它把数据的存储结构与查找、排序算法融为一体，是理解后续平衡树、堆排序等内容的逻辑起点。高二学生抽象思维趋于成熟，但对"结构决定效率"这一核心观念缺乏直觉体验。多数学生会背冒泡排序的比较次数，却说不清为什么要换一种结构来存数据。本课的教学价值不在于让学生默写建树代码，而在于让他们亲手经历"无序序列—插入建二叉树—中序遍历得有序序列"的完整过程，体会非线性结构带来的查找效率跃迁，从而建立用结构解决问题的计算思维习惯。二、教学目标1.信息意识：能从"图书归架""成绩排名"等真实情境中感知有序数据的价值，主动识别可以用二叉排序树解决的数据组织问题。2.计算思维：理解二叉排序树"左小右大"的构造规则，能用纸笔画出任一给定序列插入生成的二叉排序树，并能说明中序遍历输出有序序列的原因；初步比较二叉排序树查找与顺序查找、冒泡排序在比较次数上的差异。3.数字化学习与创新：能借助Python实现二叉树节点类与插入、中序遍历过程，并利用在线可视化工具验证自己的手工建树结果，养成"先推演、后验证"的学习习惯。4.信息社会责任：在合作探究中尊重同伴的不同建树顺序，理解输入序列不同会导致树形不同这一事实，形成对算法多样性与数据依赖性的理性认识。三、教学重难点教学重点：二叉排序树的构造规则与插入过程；中序遍历得到递增有序序列的原理。教学难点：理解"同样一组数据，插入顺序不同，树形不同、效率不同"；从结构角度解释查找效率的提升，而非停留在结论记忆。四、教学方法与课时安排方法：情境驱动法、纸笔推演法、可视化验证法、小组互助法。课时：2课时连排，90分钟。课前准备：学生机房预装Python环境，绘制用大白纸、磁贴数字卡片若干，板书用磁性黑板分区。五、教学过程环节一：情境导入——图书馆的烦恼（8分钟）上课伊始，教师展示一张实拍照片：学校图书馆还书车上堆着278本归还图书，管理员要在开馆前把它们全部归架。提问：如果采用最朴素的办法，一本一本从书架头找到尾，大约要做多少次比较？学生口算后得出最坏情况约278平方的一半量级，近4万次。教师追问：如果把书架想象成一个不断生长的结构，每来一本书，只问一句"比当前的这本书的编号大还是小"，然后向左走或向右走，会出现什么现象？请两名学生用磁贴在黑板上模拟：先放编号53，再放37，37比53小放左边；再放68，比53大放右边；再放41，比53小、比37大，放37的右边。磁贴很快形成一个倒挂的小树。教师揭示：这棵树就是二叉排序树，中文也称二叉查找树。它的规矩只有一条——对每个节点，左边子树上的值都比它小，右边子树上的值都比它大。板书主题：6.2用二叉树排序。本环节设计意图是用真实劳动情境制造认知冲突，让学生感到"必须换一种存法"，而不是被告知要背一个新名词。环节二：规则探究——动手建一棵树（18分钟）教师给出待排序序列：40、72、38、55、63、12、27、88、45。提出任务单第一项：四人一组，在白纸中央写下第一个数40作为根，然后依次处理后面每个数——从根出发，比当前节点小就往左走，大就往右走，走到空位就安家。人人动笔，组内互查。巡视中发现三类典型问题。第一类，有学生把63接到55的左子树上，原因是走到55时忘了再比较一次方向；第二类，有学生画出链状的倾斜树后认为"画错了"，教师及时肯定：树本身没错，这正是输入顺序影响树形的证据；第三类，多数组能正确完成，教师请最快的一组上台用磁贴复现建树全过程，每插一个数口述判断路径。全班核对标准结果：根为40，其左孩子38、右孩子72；38左子树挂12，12的右孩子27；38右子树为55，55的左孩子45、右孩子63；72的右孩子是88。教师强调插入规则的两个隐含约定：相等元素按约定放右（或左），本课约定放右；每个新值永远是叶子，老节点绝不搬动。随后抛出关键问题：现在这棵树里躺着9个乱序的数，怎样把它们有序地"读"出来？给学生2分钟静默思考，不要求回答，只要求在纸上写下猜想。此设计为下一环节的中序遍历埋下悬念，避免教师直接灌输结论。环节三：原理揭示——中序遍历的魔法（15分钟）教师引导学生回忆第五章遍历三兄弟：先序、中序、后序，指出中序遍历的口诀是"左—根—右"。学生在自建树上执行中序遍历：从40出发先去最左，依次读出12、27、38、40、45、55、63、72、88。巡视确认后全班齐读输出序列，学生自然发现：读出来的正好是递增有序数列。教师追问"为什么必然有序"，引导链式推理：中序遍历保证任何节点输出之前，其左子树已输出完毕，而左子树的值全小于它；它输出之后，右子树才输出，右子树的值全大于它。对每一个节点成立，对整个树就成立。请一名学生用自己的话复述，教师将其提炼为一句板书：结构存秩序，遍历现秩序。随即进行对比实验。教师出示两张统计表：冒泡排序9个元素最多比较36次；刚才建树的9次插入，比较次数分别为0、1、1、2、2、2、3、2、2，合计15次，遍历本身只访问9个节点。学生直观看到比较次数腰斩。再展示极端情形：如果输入序列本身已经有序，比如12、27、38……依次插入，树退化成一条右斜链，比较次数又涨回36次左右。学生由此明白：二叉排序树的效率与输入顺序有关，平均情况远好于最坏情况，这正是日后学习平衡树的动机。教师点到为止，不展开平衡树细节。环节四：编码实现——让树在屏幕上站起来（25分钟）任务单第二项：把纸上的树变成程序。教师给出半成品代码框架：先定义节点类Node，含data、left、right三个属性；再写insert函数，参数为当前节点与新值，用递归实现"小往左、大往右"；最后写inorder函数，按左—根—右递归输出。课堂分解为三个递进子任务。任务A（保底）：补全insert中的两个递归方向判断，使9个数按课堂上的顺序插入后，中序遍历输出有序序列。任务B（提高）：把输入改为input读入一行任意整数，空格分隔，程序自动建树排序，实现一个通用排序器。任务C（挑战）：统计建树过程中的比较总次数并输出，与冒泡排序的比较次数做对照，验证环节三的结论。学生独立编码15分钟，教师巡视频次最高的两个错误：一是递归插入忘记把返回的子树根重新赋回父节点（root.left=insert(root.left,x)中的赋值被漏写），导致新节点挂丢；二是中序遍历函数中把输出语句放到了递归调用之前，写成先序。教师不直接改错，而是让出错学生画出递归调用三层示意图自查。随后请完成任务C的学生展示运行截图，比较次数的数字让算法优劣一目了然。本环节的评价嵌入过程而非留到课后：三个任务分别对应"会模仿—能迁移—善反思"三个水平，学生完成即举手，教师在学习平台勾选等级，形成即时学习档案。环节五：可视化验证与协作互审（12分钟）学生打开教师推荐的二叉树可视化页面（教师提前把网址做成机房桌面快捷方式），输入自己组内设计的另一组序列，观察程序自动生成的树形，与自己课前纸笔推演的结果对照。要求每人在便利贴上写一句话回答两个问题之一：我的手工建树和屏幕上的树一致吗？如果不一致，错在哪一步？便利贴贴到黑板"思维留痕区"。随后组间互审：A组向B组口述自己序列的建树路径，B组只听不看画出树，再与A组原图比对。错图引发的争论最热烈，教师遴选一例典型分歧公开讲评：两组建68、45、88这串子序列时，一方把45挂到了68右侧，暴露出"走到叶子忘记它比68小"的共性漏洞。讲评聚焦路径意识，而非批评个人。环节六：课堂小结与作业布置（12分钟）小结采用学生主述、教师补网的方式。教师只给三句话的框架：今天学了什么结构，规矩是什么；它凭什么实现排序；它的效率由什么决定。三名学生各补一句，全班共同把答案凝练成板书最后三行：左小右大定结构；中序遍历出有序；输入顺序定高矮。分层作业设计如下。必做一（基础巩固）：给定序列57、33、79、21、48、66、90、17，画出插入完成后的二叉排序树，写出中序遍历结果，并标出每个新节点插入时的比较次数。必做二（迁移应用）：用本课程序对你最近一次数学测验的全班原始成绩（学委处可获取脱敏数据，或自行虚构50个分数）排序，输出前三名与后五名，并粘贴运行截图。选做（拓展探究）：研究如果允许重复成绩且约定重复值放右子树，代码需要改动哪一行？再思考若想把结果按从大到小输出，中序遍历的口诀应怎样调整，写100字说明。实践作业：观察家中或小区里的快递柜、图书角，找一处可以用"左小右大"思想优化取放秩序的场景，拍一张照片配三行说明，下节课展示。六、板书设计主板书三区：左区磁贴树形（动态生成），中区规则归纳——二叉排序树：左<根<右，插入新值必为叶；中序遍历：左→根→右；右区效率对照表：冒泡36次对比建树15次，附注"输入顺序决定树形，最坏退化为链"。副板书留"思维留痕区"张贴学生便利贴。七、教学评价设计本课采用"三轨并行"的评价。任务轨：三个编码任务对应基础、提高、挑战三档，即时勾选；留痕轨：便利贴与互审结果计入课堂参与分；作业轨：必做题看规范，选做题看推理，实践作业看迁移。评价语言坚持描述性原则，如"已能独立判断插入方向，需加强递归返回值意识"，不打笼统分数。八、