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

高中信息技术选择性必修1《用二叉树排序》教学设计一、教学定位与内容分析本课选自教科版高中信息技术选择性必修1《数据与数据结构》第6单元"树"的第2课时，是继顺序查找、二分查找之后，数据结构学习的又一个关键节点。二叉排序树（又称二叉查找树）兼具"插入快捷"与"查找高效"的双重优势，是连接线性结构与非线性结构的桥梁。教材将其安排在"树的概念与二叉树"之后，意在让学生亲历从"认识树"到"用树解决问题"的跃迁。本课的教学价值不止于掌握一种排序或查找方法。二叉排序树的构造过程，本质上是"二分思想"在非线性结构上的沉淀；其查找效率与树形形态之间的关联，是学生第一次真切体会"数据组织方式决定算法效率"这一计算学科核心命题。课文所述的树的不稳定性——同一组数据，插入顺序不同，树形迥异，效率差异悬殊——恰恰是培养学生辩证思维和工程意识的绝佳素材。二、学情研判授课对象为高二选考信息技术的学生。他们已具备三项基础：其一，必修模块中掌握了Python基本语法，能读写列表、调用函数；其二，上一学段学习了二叉树的概念、性质和中序遍历；其三，经历过折半查找的学习，"每次排除一半"的策略已成经验。同时存在三处明显的认知障碍。第一，递归仍是软肋。多数学生能口头复述遍历次序，却难以独立写出递归插入代码，"自己在函数里调用自己"这一层窗户纸尚未捅破。第二，指针思维缺失。学生习惯了下标和线性排列，对"每个结点只需记住左孩子、右孩子"这种局部连接支撑全局结构的方式感到陌生。第三，效率感知停留在口号层面。学生背得出"时间复杂度O（logn）"，却说不清这个对数从哪里来、何时会退化为O（n）。因此本课设计的重心是：用具象活动解构递归构造过程，用对比实验暴露效率差异，让"结构决定效率"从口号变为学生亲眼所见的事实。三、教学目标信息意识：能根据数据的动态增删特点，意识到静态线性存储的局限，主动评估引入树形结构的必要性。计算思维：经历"问题分解—局部规则归纳—递归构造"的完整过程，掌握二叉排序树的插入规则与查找路径设计；理解中序遍历输出有序序列的原理，体会左子树、根、右子树三段式的内在秩序。数字化学习与创新：能用Python链表方式或嵌套字典实现二叉排序树的插入与查找，通过改变输入序列观察树形变化，在调试中修正对局部规则的理解偏差。信息社会责任：在讨论结构退化为链表的案例中，初步形成"任何数据结构都有适用边界"的批判性认识，理解工程实践中选择比技巧更重要。教学重点：二叉排序树的构造规则与查找过程。教学难点：递归插入的逻辑实现；树形与效率关系的深层理解。四、教学准备机房环境预装Python3.10以上版本；教师准备可视化演示工具（自研小程序，可逐动画展示结点下落过程）；学案印发两组数字卡片任务单；课前在班级平台推送5分钟微课"三分钟回顾中序遍历"。五、教学过程环节一：真实情境中的结构困境（约6分钟）上课伊始，教师抛出情境：校园失物招领系统的登记簿。每捡到一件物品，登记一行，包含编号和物品描述。学期过半，登记簿已有一千多条记录。有同学来询问"编号1024的钥匙串在不在"，管理员只能从头翻到尾。教师追问：如果想查得快，上学期学的办法是什么？学生自然答出折半查找。教师肯定后继续设障：折半查找要求数据有序存放，可失物每天都在增加，每来一件新物品，为了保持有序就得插入到中间，后面成百上千条记录全部后移。查得快了，登记却慢了。有没有一种结构，登记新物品快，查找也快？学生的已有经验在此刻被同时调用又同时受挫，认知缺口清晰可见。教师板书课题：用二叉树排序——让查找和插入都快起来。这一环节的设计意图在于，不直接给出"二叉排序树"这个名词，而是先制造"线性结构无法两全"的真实矛盾，让数据结构作为解决问题的答案登场，而非作为需要记忆的考点登场。环节二：规则共建——结点该往哪里放（约10分钟）教师展示第一组数据：56，32，78，25，90，41。规则由师生共同逐条建立。第一个数56来了，它是孤独的，就任它做根。第二个数32来了，和谁比？和根比。比根小，往哪去？学生的直觉几乎一致地指向左边。第三个数78，比56大，去右边。第四个数25，先和56比，去左边；左边已经有32了，再和32比，比32小，挂到32的左边。教师在此处停顿，引导学生把刚才的走位规则压缩成一句话。经过两三轮修改，黑板上留下学生自己的语言：从根出发，小的往左，大的往右，遇到空位就安家。接着教师在可视化工具上逐个输入剩余数字，树形在屏幕上生长：90挂在78右边，41挂在32右边。一棵六结点的二叉排序树成形。教师提出本节课的第一个检验性问题：如果我现在中序遍历这棵树，会得到什么？学生分组心算或在学案上推演，得到25、32、41、56、78、90——恰好是升序排列。惊讶的表情出现在教室里。教师点破：这不是巧合。左子树所有值都比根小，右子树所有值都比根大，中序遍历"左—根—右"的访问次序，天然就是"小—中—大"。这就是"用二叉树排序"的全部秘密：构造即分类，遍历即排序。此环节教师的角色是规则的助产士而非颁布者。规则由学生的操作经验凝结而成，后续的代码实现才有认知锚点。环节三：纸上构造与互查（约8分钟）学生独立完成学案任务一：用数字38，65，97，76，13，27，49手工构造二叉排序树，画出树形图，再写出中序遍历序列验证有序性。完成后同桌互换，用"重新插入一遍"的方式互相验算——不是对答案，而是把对方的树当作黑箱，拿每个数字去走一遍查找路径，看能否在正确位置找到它。这种验证方式比对照标准答案更深刻地复现了规则。教师巡视时重点关注两类典型错误：一类是把65直接挂到38的右边就停手，忘记继续与97比较的逻辑只走了一层，这反映出"从根出发逐层比较"的链条尚不牢固；另一类是把相等值的处理遗漏，教师借此补充约定：相等时可以约定一律走右子树，规则必须封闭，不能留白。环节四：从规则到代码——递归的破局（约12分钟）这是本课最硬核的环节。教师先展示结点定义：classNode:def__init__(self,value):self.value=valueself.left=Noneself.right=None教师强调一个观念转变：不要想着"整棵树"，每个结点眼里只有自己的左口袋和右口袋。整棵树的秩序，是千千万万次局部决策的累积结果。然后师生共同完成插入函数。教师不直接给完整代码，而是给出"四格框架"，让学生口头填空：definsert(node,value):如果node是空位：把新结点放在这里，返回新结点否则如果value比node的值小：让node的左口袋接住"往左子树插入的结果"否则：让node的右口袋接住"往右子树插入的结果"返回node"让node.left接住insert（node.left,value）的返回值"这一句是理解枢纽。教师用三个结点的微型例子在黑板画调用栈：insert（56根，25）发现25该去左边，于是把任务转包给insert（32，25），32又转包给insert（None，25），空位返回新结点，32接回设为左孩子，56接回保持左孩子不变。递归的"转包—回传—挂接"三步在板书上完整显形。随后学生在机房补全代码并运行，配合教师提供的中序遍历函数，输入环节二的数据，屏幕输出有序序列即为成功。对学有余力的学生布置拓展：改用嵌套字典而非类来实现同一结构，比较两种表达的优劣。分层任务让不同起点的学生都有可达的终点。环节五：效率的显影——同一批数据，两种命运（约10分钟）教师做现场对比实验。实验一：输入56，32，78，25，90，41，程序统计查找90时的比较次数，答案是3次。实验二：输入已升序的25，32，41，56，78，90，再查找90，比较6次。教师让两名学生在黑板上分别画出两棵树：第一棵接近平衡，第二棵完全向右倾斜，活脱脱一条链表。全班的目光聚焦在这两张图上，教师说出本课最重要的一句话：二叉排序树没有骗你。查找次数等于结点的深度，而深度由树的高矮胖瘦决定，树形由插入顺序决定。最好的情况，每次都能排除一半结点，查找代价是log₂n量级；最坏的情况，树退化成链表，一切回到从头翻登记簿的老路。教师给出可视化结论：理想情况下效率约为log₂n次比较，退化情形下为n次比较，差距随数据量指数级拉大。学生分组完成任务二：给定数字1至7，试找一种插入顺序，使构造出的树高度最小（答案锚定在"先插4，再插2、6"这类先中间后两边的策略，本质是把根放在有序序列的中点）；再找一种顺序让树退化成链。正反两种构造让学生在动手中固化"顺序塑造形态、形态决定效率"的因果链。教师简短展望：工程师们不甘心树的高度听天由命，发明了能自我调整仪态的平衡树，如AVL树、红黑树，它们保证任何插入顺序下树高都维持在log₂n附近。这一块留作课后阅读，为有志深入的学生留一扇门。环节六：课堂小结与结构化梳理（约4分钟）师生共同编织本课知识网，教师板书三句话：其一，构造规则——小的向左，大的向右，空位安家，递归实现；其二，排序原理——中序遍历左中右，天然输出小中大；其三，效率真相——树形决定代价，顺序塑造树形，平衡是工程追求。回到课首的失物招领情境，请一名学生用本课知识向"管理员"口头解释新方案如何工作。能讲给别人听，才是真学会。六、作业设计本课作业分为三个层级，总量控制在60分钟内，兼顾巩固、迁移与探究。基础层（必做，约20分钟）。第一题：将序列50，72，43，85，75，20，35构造成二叉排序树，画出树形，写出中序遍历序列，并统计查找75的比较次数。第二题：改装课堂代码，为程序增加"查找功能"，输入目标值后输出查找路径（依次打印比较过的结点值），用路径的可见化反哺对树形的理解。第三题：判断改错——"二叉排序树中，任意结点的左孩子一定小于右孩子"，要求辨析这个说法与正确规则"左子树所有结点小于该结点"之间的差别，写出反例。此题直指普遍的前概念混淆。提升层（必做，约25分钟）。综合任务"班级图书角索引"：班里图书角有六十本图书，每本有索书号。学生编写完整程序实现三项功能——逐本登记（插入）、按索书号查询（查找并报告比较次数）、输出全部索书号的有序清单（中序遍历）。要求程序对重复索书号给出提示而非静默接受，呼应课堂上"规则必须封闭"的讨论。提交物包括源代码、一次完整运行的截图、不超过200字的设计说明，说明中必须回答"你的程序在最坏情况下查找要比较多少次，什么情形会触发"。探究层（选做，弹性时间）。任务一：写程序随机生成1000个不重复整数，分别按"随机顺序插入"和"升序插入"构造两棵树，测量并比较两棵树的高度与平均查找长度，用数据验证课堂结论，形成一页实验报告。任务二：阅读材料了解AVL树的旋转调整思路，用自己的话向同学解释"左左型为什么一次右旋就能恢复平衡"，可在下次课前三分钟分享。作业评价采用"正确性—表达力—洞察力"三维量规。正确性看构造与代码结果；表达力看设计说明能否讲清规则与边界；洞察力看能否主动关联插入顺序与效率。量规随作业下发，标准先行。七、板书设计主板书三区并列。左区：问题冲突——"登记要快？查找要快？线性结构两难"。中区：规则与代码骨架——"小左大右，空位安家"八字口诀，insert四格框架，