高中信息技术选择性必修1数据与数据结构二叉树的基本操作教学设计

高中信息技术选择性必修1数据与数据结构二叉树的基本操作教学设计一、教材分析《数据与数据结构》是高中信息技术选择性必修课程的核心模块，承担着将学生从“会用程序”引向“会组织数据”的关键任务。二叉树是非线性结构的典型代表，位于区间结构之后、图结构之前，起到承上启下的桥梁作用。学生此前已经掌握了数组、链表、栈、队列等线性结构，理解了“元素之间存在一对一的次序关系”这一基本观念。本节内容即二叉树的基本操作，包括二叉树的创建、遍历、查找、插入与删除，是学生第一次系统地以“递归”的思维方式处理数据，也是从“顺序思考”跃迁到“分层思考”的转折点。浙教版2019版教材将本节安排在第四章第二节，教材以家族谱系、淘汰赛对阵图为引例，顺势引出树形结构的层次特征，再聚焦到每个结点至多有两个孩子的特殊形态，即二叉树。教材的处理体现了从特殊到一般再回到特殊的编排逻辑，教师在教学中应当尊重并放大这一逻辑，让学生在操作二叉树的过程中体会到：抽象是为了更精确地解决问题，而不是为了抽象本身。本节内容的技术要点较多，若平铺直叙地讲解五类操作，学生容易陷入“听懂了、记不住、写不出”的困境。因此本设计以“操作背后的共同思维”为暗线，以“递归分解”为明线，把创建、遍历、查找、插入、删除统一在“根—左子树—右子树”这一递归定义之下，使学生获得一把可以打开所有二叉树问题的钥匙。二、学情分析授课对象为高二年级选考信息技术的学生。他们已经具备Python编程基础，能够使用类与对象描述事物，理解函数调用的执行过程，部分学生在先前的递归函数学习中已经接触过阶乘、斐波那契数列等经典案例，对“函数自己调用自己”有初步印象，但大多数学生对递归的理解停留在语法层面，尚未形成“把大问题拆成同构的小问题”的思维习惯。从认知特点看，高二学生的抽象逻辑思维正在快速发展，但面对不可见的数据结构时仍需要大量可视化支持。学生在纸上画出二叉树并进行手工遍历并不困难，困难在于把手工操作的直觉步骤翻译成程序语言。教学应当在“手工模拟—口语描述—流程表达—代码实现”四个层级之间反复往返，帮助学生完成从直观到抽象的跨越。此外，班级内部差异明显。一部分学生参加信息学竞赛训练，对二叉树已有相当了解；另一部分学生对链表指针尚且感到吃力。教学设计需要设置分层任务：基础层保证人人会建树、会遍历、看得懂代码；提高层引导学有余力的学生探究非递归遍历、二叉树的实际应用以及操作的时间复杂度分析。三、教学目标（一）信息意识学生能够识别现实情境中的树形结构，理解为何文件夹系统、组织结构、表达式求值等场景无法简单用线性表描述，形成“根据数据之间的关系选择结构”的意识。（二）计算思维学生理解二叉树的递归定义，能够运用递归分解的思想设计遍历、查找等算法，能用自然语言、流程图和Python代码三个层次表达算法，初步分析各操作的时间代价与树的高度之间的关系。（三）数字化学习与创新学生能够在编程环境中借助列表嵌套或类对象构建二叉树，借助可视化手段观察遍历的结点访问次序，通过修改代码、对比输出的方式开展自主探究。（四）信息社会责任通过对家谱、赛事对阵等实例的分析，体会数据结构在信息组织中的价值，养成严谨、规范的编程习惯，理解高效算法对节约计算资源的意义。四、教学重点与难点教学重点：二叉树的链式存储表示；先序、中序、后序三种遍历的规则与递归实现；基于递归定义的查找与结点插入操作。教学难点：递归遍历过程中程序执行的“下去—回来”过程的理解；删除操作中不同情形的分类讨论，尤其是被删结点有两个孩子时“用中序直接后继替代”的策略；从递归定义出发自主设计新操作的方法迁移。五、教学方法与策略本课采用情境驱动、对比归纳、可视化演示与分层任务相结合的方式。以“学校社团组织架构查找负责人”为贯穿情境，引出树形结构；以黑板贴磁贴模拟结点和指针连接，让存储结构看得见；以动画逐帧演示递归遍历的调用栈变化，让算法过程看得见；以“翻译官”活动让学生把手工遍历的直觉翻译成代码，让思维过程看得见。课前为学生准备学习单、半成品代码和在线评测入口；课中以小组协作完成操作任务；课后布置分层作业并开放拓展资源。六、教学准备教师准备：多媒体课件、二叉树结点磁贴若干、递归遍历动画演示程序、半成品代码工程、课堂练习评测账号。学生准备：复习Python类与对象的基本语法，完成学习单上前置概念自测部分，回忆递归函数的执行机制。环境准备：机房每台计算机安装Python解释器与编辑器，保证网络畅通以便访问在线评测与可视化站点。七、教学过程（一）情境导入：从一张架构图说起上课伊始，教师投影学校社团联合会的组织架构图：联合会之下设科技部、文艺部、体育部，科技部之下又设机器人社、航模社、编程社，依此类推。教师提出问题：教务处想知道“编程社隶属于哪个部门”，如果所有社团信息存放在普通列表里，你会怎么查？如果把这张架构图原样搬进计算机，又该怎么查？学生给出的第一思路通常是“挨个看”“顺着箭头往上找”。教师追问：顺着箭头找的办法，和我们之前学过的数组、链表有什么不一样？学生比较后发现：这张图中的每个“结点”不止指向后面一个结点，而是“分叉”的。教师顺势揭题：这种每个结点最多分出两叉的结构叫二叉树，它是处理层次关系数据的基本模型。今天我们要做的，就是学会在计算机里把二叉树建起来、走遍它、在里面找东西、往里加结点、把结点拿掉。这五个动作，就是二叉树的基本操作。设计意图：用真实组织架构制造认知冲突，让学生意识到线性结构无法自然地表达层次关系，从而产生学习新结构的心理需要。“建、走、找、加、删”五个动词为全课立下总纲，后续每个环节都能回扣到这张任务地图。（二）复习衔接：二叉树的定义与递归本质教师引导学生回顾上一节的定义：二叉树是n（n≥0）个结点的有限集合，当n等于0时为空二叉树，否则由一个根结点和两棵互不相交、分别称为左子树和右子树的二叉树构成。教师请学生注意这个定义的表述方式。请三位学生分别朗读定义中“由一个根结点和两棵……二叉树构成”这一句。教师提问：这个定义哪里特别？学生发现：定义二叉树的时候用到了“二叉树”自己。教师板书一句话：二叉树本身，就是“根加上两棵更小的二叉树”。并给出可视化的结构示意：二叉树=根结点+左子树（一棵二叉树）+右子树（一棵二叉树）教师强调：这棵“更小的二叉树”还可以继续往下拆，直到遇见空树为止。空树是所有递归的尽头。随后教师问：如果一个数据结构是靠“自己的缩小版”定义出来的，那么处理它的算法最可能长什么样？学生自然回答：算法也会自己调用自己，也就是递归。设计意图：先复习旧知，再把教学重心从“定义的内容”转移到“定义的形式”，让学生自己说出“递归定义呼唤递归算法”，为后续所有操作的代码实现预埋思维种子，避免把递归当作突兀的新知识灌输。（三）任务一：把树种进计算机——二叉树的创建教师抛出问题：纸上画的二叉树很好看，可Python不认识图画。我们怎么让程序里也“长”出一棵树？学生在学习单上完成一个填空式讨论：一个二叉树结点至少要记住哪三件事？小组交流后得出结论：结点要存放数据本身，要记住左孩子在哪，要记住右孩子在哪。这与链表中“数据域加指针域”的经验一脉相承，只是指针从一个变成了两个。教师展示结点类的代码：classNode:def__init__(self,data):self.data=dataself.left=Noneself.right=None随后教师用磁贴在黑板上搭建一棵含五个结点的二叉树，演示代码中“a.left=b”“a.right=c”这两条赋值语句的含义：就是让结点a的左手牵住结点b，右手牵住结点c。学生在半成品代码上补全连线，运行后用一个简单的打印语句验证根结点的左右孩子确实指向了正确的对象。教师进一步提出延伸问题：如果结点很多，一个个手工连线太麻烦，有没有办法一次性把整棵树“说”给程序听？教师介绍按层次输入的建树思想：以“”表示空结点，按某种约定次序读入数据，递归地把子树接好。教师给出按先序序列建树的示意：输入序列：ABD程序读到一个字母就建一个结点，读到“”就把这个位置接成空树。学生不必当堂完整实现，但要在学习单上画出该序列对应的树的形状，为遍历环节埋下素材。设计意图：建树环节从学生已有的链表经验出发迁移，降低陌生感；“磁贴连线”把抽象的指针赋值变成可触摸的动作；分层处理，基础学生掌握逐结点链接，学有余力的学生接触序列化建树，满足不同层次需求。（四）任务二：走遍整棵树——三种遍历操作这是本课的核心环节。教师先给遍历下操作化定义：按照某种次序访问树中每个结点，每个结点恰好访问一次。访问可以是打印、统计、修改，关键是“次序”。第一步，手工遍历。黑板上画出刚才那棵五结点二叉树，根为A，A的左孩子为B、右孩子为C，B的左孩子为D、右孩子为E。教师给出约定：所谓“先左后右”，即面对任何子树都先看左边再看右边；三种遍历的区别只在于“什么时候访问根”。教师给出三条规则，师生共同手工推演：先序遍历：根—左子树—右子树，结果为ABDEC。中序遍历：左子树—根—右子树，结果为DBEAC。后序遍历：左子树—右子树—根，结果为DEBCA。学生在学习单上独立完成后交换批改，教师请两名学生上台讲解推理过程，要求使用统一的句式：“先走到……然后……当左边为空时……”。统一的口语表述是后续翻译成代码的桥梁。第二步，可视化演示。教师运行动画程序，屏幕上递归函数每进入一层，调用栈就增加一格；每访问一个结点，该结点变色；函数返回时栈格弹出。学生观察后回答两个问题：为什么访问D之后程序会“回到”B？为什么根结点A在三个序列里出现的位置会变？通过动画学生看到：递归调用像下楼梯，返回像爬楼梯，三种遍历只是“在楼梯的不同位置停下来办事”。第三步，代码实现。教师展示先序遍历代码：defpreorder(root):ifrootisNone:returnprint(root.data)preorder(root.left)preorder(root.right)学生惊讶于代码只有五行。教师引导对照：第一行是“空树什么事都不做”，对应递归尽头；打印语句对应“访问根”；后两行对应“处理左、右子树”。教师请学生把打印语句挪到两个递归调用之间得到中序遍历，挪到两个递归调用之后得到后序遍历。学生在电脑上修改、运行、比对输出，亲自验证“一句话的位置决定遍历次序”。第四步，概念辨析。教师在黑板上画出一棵形态特殊的树：每个结点都只有右孩子。提问：此时先序和中序结果一样吗？这棵树“退化”成了什么结构？学生发现退化的二叉树等价于链表，进而理解：二叉树的效率优势依赖形态，形态越接近平衡，操作越高效，这为后续学习埋下伏笔。设计意图：遍历教学按照“手工推演—口语表达—动画观察—代码实现—辨析深化”五步推进，让多种表征相互印证。代码的简洁性给学生带来冲击，促使他们体会递归定义与递归算法之间的完美对应，这是本课最想传递的思维美感。（五）任务三：在树里找人——查找操作教师回到开课情境：现在架构图已经在计算机里建成了一棵二叉树，请找出“编程社”是否存在，若存在，报告它的上级，也就是它双亲的数据。学生分小组设计算法。多数组能提出方案：从根开始看，是当前结点就报告，不是就去左子树找，左子树找不到再去右子树找。教师追问：这个“再去左子树找”的办法，和我们查找整棵树的办法是不是同一个办法？学生意识到这正是递归。学生尝试写出查找函数：defsearch(root,key):ifrootisNone:returnNoneifroot.data==key:returnrootresult=search(root.left,key)ifresultisNone:result=search(root.right,key)returnresult教师组织代码走查：口头模拟查找“E”和查找“F”两个案例，全班一起跟踪每一次函数调用的返回值，重点体会“空树返回空”“找到立即上传”这两条消息传递规则。教师补充拓展：如果这棵树恰好每个结点的左孩子都比自己小、右孩子都比自己大，查找还需不需要两边都找？学生直觉地回答“不用”，教师说明这便是二叉搜索树的思想，查找效率可以从“每个结点都看一遍”提升到“每层只看一个结点”，为后续章节留下接口，但本节不作硬性要求。设计意图：查找是递归思想的第二次应用，学生独立设计、教师点拨难点，实现从“模仿遍历”到“自主构造递归算法”的跨越；走查活动训练学生追踪递归执行过程，直指本课难点。（六）任务四：让树长大——结点的插入教师提出问题：新成立了一个“天文社”，想挂到“科技部”名下，怎么办？学生很快给出方案：先查找“科技部”这个结点，再把新结点接到它的空手上。教师板书操作流程：查找定位—判断空位—接入新结点。学生在已有查找函数的基础上补全插入函数并上机验证：插入前中序遍历一次，插入后再遍历一次，对比输出确认新结点出现在正确位置。教师抛出辨析题：如果“科技部”两只手上都已经挂了社团，新结点挂哪里？学生分组讨论，提出“再往下找空位”“报错提示”“换规则”等不同策略。教师肯定各种答案都有其适用场景，强调一句话：插入的规则由应用决定，算法必须先把规则说清楚，代码才有依据。规则不同，插入方式就不同；这也正是数据结构服务于实际问题的体现。设计意图：插入操作是查找与指针赋值的组合运用，起到承上启下作用；开放性讨论让学生明白算法不是唯一答案，而是规则的形式化表达，培养严谨定义需求的习惯。（七）任务五：安全地告别——结点的删除教师设置情境：某个社团撤销了，要从架构中移除。删除一个结点，会出现哪些不同的情况？学生在学习单上画树讨论，教师巡视并收集典型画法，最后师生共同归纳出三种情形：情形一：删除叶子结点。它没有孩子，直接摘掉，让双亲对应的手指向空即可。情形二：删除只有一个孩子的结点。摘掉它会造成“断链”，需要让它的孩子顶替它的位置，即双亲的手绕过它直接拉住孩子。情形三：删除有两个孩子的结点。这是难点。教师先不给答案，而是让学生用磁贴在黑板上尝试“移走根结点”，观察剩下两棵子树无处安放的窘境。教师提示思路：找一个“替身”顶上来，这个替身必须能在新位置上服众。在二叉搜索树的语境下，替身取自被删结点中序序列的直接后继，习惯于取右子树中最小的结点；把替身的值复制到被删位置，再递归地删除替身结点。替身要么就是叶子，要么只有一个孩子，于是复杂情形被归约为前两种已经会处理的情形。教师用四步图示（定位—找替身—换值—删替身）在黑板上完整演示一遍，学生在学习单上补全每一步对应的指针变化，并口述删除算法。代码实现安排在提高任务中，由学有余力的学生课后完成，课堂只要求人人能用图示说清三种情形的处理办法。设计意图：删除是五种操作中思维含量最高的，采用“情境分类—磁贴试错—替身策略—归约转化”的路径，让学生亲历“把未知问题转化为已知问题”这一计算思维的核心过程。分层要求控制课堂容量，避免基础薄弱学生被代码细节淹没。（八）归纳提升：一张共同的思维地图教师带领学生回看五个操作，在学习单上共同填写对照表：每个操作都能分成“空树怎么办”和“非空怎么办”两部分；非空时，几乎所有操作都可拆成“处理根、处理左子树、处理右子树”三块，区别只在于处理的时机与组合方式。教师板书总结句：二叉树是递归定义的，所以它的每一个操作都是递归生长的；抓住“空树为基、根与两子树分工”这两条，就能自己长出求高度、数结点等其他操作的算法。教师当堂布置两分钟小挑战：模仿遍历函数，写出“统计叶子结点数”的递归函数框架。多数学生能写出：空树返回零；左右都空返回一；否则等于左子树的叶子数加右子树的叶子数。教师点评：这就是递归思想迁移成功的标志。随后布置分层作业：基础层完成三种遍历的手工推演与代码默写；提高层实现删除操作的完整代码并提交在线评测；探究层借助网络搜索了解