高中信息技术选择性必修1第13课树与二叉树教学设计-从家族图谱到高效查找之路

高中信息技术选择性必修1第13课树与二叉树教学设计——从家族图谱到高效查找之路【教材与学情分析】本课选自浙教版（2019）高中信息技术选择性必修1《数据与数据结构》模块，是“数据结构与算法”核心内容链中的关键一环。在课程标准中，本模块要求学生“理解树结构的逻辑特征，掌握二叉树的基本概念与遍历方法，能结合生活实例分析树结构的应用价值”。学生此前已经学习了数组、链表、栈、队列等线性数据结构，建立了“结构决定操作方式”的初步认识。线性结构强调元素之间的前后关系，而现实中大量的数据关系——家族谱系、行政区划、图书分类、赛事淘汰、表达式求值、文件目录——呈现出明显的层次性和分支性，这正是树结构登上课堂舞台的现实依据。高二学生的抽象逻辑思维已趋于成熟，但“递归”这一思想仍是认知难点。学生能够直观理解“树像一棵倒立的树”，却容易在“先序、中序、后序遍历为什么是这样一种次序”上产生混淆，也往往把二叉树的性质当作孤立结论死记硬背。本课设计的核心策略是：以真实情境引入概念，以递归视角统辖定义与遍历，以编程实践固化理解，以查找效率对比展现应用价值，让学生在“为什么需要树”“树如何组织数据”“树能带来什么好处”三个递进问题上形成完整闭环。【教学目标】一、信息意识。学生能从家谱、组织结构图、文件夹系统等生活实例中识别层次关系，意识到选择合理的数据结构是高效解决问题的前提。二、计算思维。学生理解树与二叉树的递归定义方式，能将“整棵树的处理”分解为“根结点处理＋子树处理”，绘制二叉树的逻辑结构图，完成三种深度优先遍历的次序推导，并能用递归代码实现遍历。三、数字化学习与创新。学生借助Python程序对给定二叉树进行建立、遍历与结点查找，通过修改数据观察输出变化，形成“编码—运行—验证—反思”的探究习惯。四、信息社会责任。学生在讨论族谱数据、组织架构数据的管理时，初步意识到层次化数据管理中权限与隐私保护的必要性。【教学重点与难点】重点：树的基本术语与二叉树的性质；二叉树三种遍历次序的推导与递归实现。难点：递归思想在树结构中的迁移运用；遍历次序的逻辑推导而非机械记忆。【教学方法】情境驱动法、任务驱动法、对比实验法、小组协作探究法。教学环境为配备Python环境的多媒体机房，配套学习单一份、探究程序半成品代码一份。【教学过程】一、情境导入：一张族谱引发的疑问（约5分钟）大屏幕展示某家族的一份族谱截图：最上方是始迁祖，向下分支出若干房系，每房再分出下一代。教师提出三个连环问题：这份族谱里，每个人的“位置”是由什么决定的？如果用我们学过的线性表来存储这份族谱，查找某人的父亲和儿子方便吗？如果数据量扩大到十万人，还顺手可查吗？学生讨论后普遍感到：线性表只能表达“排排队”的关系，无法自然表达“一人之下多支分叉”的关系。教师顺势板书课题：树与二叉树。指出本节课的学习主线——认识树、解剖二叉树、学会遍历、看清价值。设计意图：以学生有真实体验的族谱切入，制造“已学结构不够用”的认知冲突，让新知识的出现具备必要性而非强加性。二、概念建构：从生活之树到数据结构之树（约10分钟）教师引导学生观察族谱图，共同提炼术语。整份族谱对应一棵树；最顶端的始迁祖是根结点；没有后代记录的结点称为叶子结点（或终端结点）；每一个有后代的人与其子女之间构成父子关系，相连的两个人之间是一条边。教师即时追问：一个结点可以有几个父亲？学生结合图观察得出结论：树中除根之外，每个结点有且仅有一个前驱（父结点），但可以有零个或多个后继（子结点）。这正是树形结构与线性结构的本质区别，也是它与“图”的区别所在——树中不存在环，任意两个结点之间的路径唯一。接下来给出形式化描述：树是n（n≥0）个结点构成的有限集合，当n为0时称为空树；当n大于0时，有且仅有一个根结点，其余结点可分为m个互不相交的集合，每个集合本身又是一棵树，称为根的子树。教师特别提示学生注意这个定义的句式：“子树本身又是一棵树”——定义中出现了自己，这就是递归定义。一棵树可以拆成根加若干子树，每棵子树还能继续这样拆，直到拆成单结点。这为后续的递归遍历埋下伏笔。随后补充一组可量化的术语：结点拥有的子树个数称为结点的度；树中各结点度的最大值称为树的度；从根到某结点所经路径的长度体现为层次，根在第1层；树中结点的最大层次数即树的高度（深度）。教师用那张族谱指名提问：这房支系的度是多少？整份族谱高度是多少？学生在具体对象上完成术语的首次应用。教师再举三例巩固判别：学校“校长—处室—年级组—班级”的组织结构是树；计算机中“盘符—文件夹—子文件夹—文件”的目录体系是树；而城市公交换乘网不是树，因为存在多条到达同一站点的路径，存在环。通过正反例对照，学生对树的判定标准形成清晰边界。三、聚焦二叉树：限制带来力量（约12分钟）教师提出新的问题情境：树中每个结点的子结点数目不定，程序中很难统一处理；如果我们约定每个结点最多只有两个孩子，并且明确区分“左孩子”和“右孩子”，会不会让结构变得规整而易于编程？由此引出二叉树的定义：二叉树是n个结点的有限集合，或为空，或由一个根结点和两棵互不相交、分别称为左子树和右子树的二叉树构成。注意，二叉树同样是递归定义的，而且左右子树有次序，左右颠倒就是另一棵二叉树——教师用两个三结点的例子进行现场对比，让学生直观看到“有序”是二叉树区别于度为2的普通树的关键。接着探究二叉树的形态谱系。教师布置学习任务单第一题：画出所有不同形态的三结点二叉树。学生动手后发现共有5种，而不是3种，再次印证左右子树有序这一规定。随后介绍两种特殊形态：满二叉树，即每一层的结点数都达到该层最大值的二叉树，外观上整齐饱满；完全二叉树，即除最后一层外各层均被填满、且最后一层结点连续靠左排列的二叉树。教师展示两幅图让学生判断类别，并点明完全二叉树在后续堆结构、哈夫曼树中的基础地位。然后是性质的探究式推导，而非灌输。教师给出一棵绘有层号和结点编号的满二叉树挂图，提出四问。第一问：第i层最多有多少个结点？学生逐层计数，1、2、4、8……归纳出第i层至多有2的i减1次方个结点，即2(i1)，用文字表述就是“顶层为1，逐层翻番”。第二问：高度为h的二叉树最多有多少个结点？把各层最大值累加，是首项1、公比2的等比数列前h项和，结果为2h1。第三问：任意一棵二叉树中，叶子结点数n0与度为2的结点数n2有何关系？教师引导学生从“边”的角度入手：树中n个结点共有n1条边；换个角度看，边由度为1和度为2的结点向下发出，总数为n1+2×n2。两式相等得n1=n1+2×n2，即n0+n1+n21=n1+2×n2，化简得n0=n2+1。这个结论“叶子总比双分支结点多一个”令不少学生感到意外，教师让各组用几棵自画的树验证，全部成立。第四问留作思考：具有n个结点的完全二叉树，其高度是多少？提示学生对2(h1)≤n≤2h1取对数分析，下节课结合数组存储再展开。设计意图：性质的获得全部经由观察、猜想、验证、证明的路径完成，学生记住的不只是结论本身，更是结论背后的推理方法。四、核心攻坚：二叉树的遍历（约15分钟）教师设置问题：树建好之后，如何做到“一个不漏、一个不重”地访问所有结点？线性结构从头走到尾即可，树有分支，必须人为规定访问规则。由此引出遍历的概念，并明确本课聚焦三种深度优先次序。教师先在黑板上画出本课“样例树”：根为A，A的左孩子为B、右孩子为C；B的左孩子为D、右孩子为E；C的左孩子为F。约定用符号D表示“访问根结点数据”，L表示“遍历左子树”，R表示“遍历右子树”。那么先序遍历的规则是D、L、R的次序反复执行；中序遍历是L、D、R；后序遍历是L、R、D。教师带领学生用“递归展开法”推导先序遍历。看整棵树：先访问根A；再处理A的左子树（以B为根）：访问B，处理B的左子树得D，处理B的右子树得E；左子树完成后处理A的右子树：访问C，再访问其左孩子F。于是先序结果为A、B、D、E、C、F。教师强调推导口诀：“遇到结点先记下，左子走完走右子”。接着由学生分组独立完成中序与后序的推导，教师巡视点拨。中序推导要点是“先沉到最左，访问后再看右”，结果为D、B、E、A、F、C；后序“左右都尽再回首”，结果为D、E、B、F、C、A。各组代表上台板演并讲解，全班互评纠错。为了突破“次序易混”的难点，教师补充一种形象学法——环绕描线法：从根结点左侧起笔，贴着整棵二叉树的外轮廓逆时针绕行一周，每个结点会被路线经过三次；第一次经过时记下即先序，第二次经过时记下即中序，第三次（从右侧离开）时记下即后序。学生在学习单上动手描线验证，先前推导的三组序列全部吻合。抽象规则由此获得空间直觉的支撑。教师进一步引导抽象：三种遍历的区别只在“根在什么时候被访问”，而左子树恒先于右子树；且无论哪种次序，处理子树的方式与处理整棵树的方式完全相同——这正是递归的天然用武之地。教师板书三者函数结构的对照：先序是“访问根→遍历左→遍历右”，中序是“遍历左→访问根→遍历右”，后序是“遍历左→遍历右→访问根”，函数体只有三行核心语句，三行语句的排列组合产生三种遍历。五、编程实践：让遍历在机器上跑起来（约13分钟）学生打开教师事先下发的半成品程序。程序采用“结点类＋链接存储”的方式构造样例树：classNode:定义结点类，含data、left、right三个属性，初始化时左右指针指向None。随后按样例树手工创建六个结点并连接：A.left=B，A.right=C，B.left=D，B.right=E，C.left=F。学生任务一：补全先序遍历函数preorder(root)：若root为None则返回；否则输出root.data，递归调用preorder(root.left)，再递归调用preorder(root.right)。运行程序，核对输出是否与手工推导的A、B、D、E、C、F一致。学生任务二：以先序函数为模板，只调整三行语句的顺序，得到中序与后序函数，运行验证。学生在这一刻会真切体会到“递归代码之简洁与手工推导之繁琐”之间的张力，从而理解递归表达的价值。学生任务三（拓展）：统计叶子结点个数。教师提示思路——若结点为None返回0；若结点无左无右返回1；否则返回左子树叶子数加右子树叶子数。能力较强的学生很快写出代码并用样例树验证：叶子为D、E、F共3个，同时用n0=n2+1交叉验证：样例树中度为2的结点是A和B共2个，2+1=3，两法吻合，课堂出现一个小高潮。教师巡视过程中收集典型错误：有的学生忘记判断空结点导致程序报错，有的把三种次序的输出语句放错位置。教师选择一例投影剖析，强调“递归函数必须设置终止条件，终止条件就是空树”。六、价值透视：树结构为何高效（约5分钟）教师组织一次对比实验。程序中准备一个含一百万个已排序整数的列表，分别用“顺序查找”和“二分查找”查找某个数值，计时对比，后者快出几个数量级。教师点拨：二分查找的每一次决策过程——向左走还是向右走——恰好就是一棵二叉树的行进路径，这正是二叉排序树（二叉搜索树）的思想雏形：左子树中所有值小于根，右子树中所有值大于根，查找时逐层排除一半数据，查找次数从百万级降到约20次（因为220已超百万）。教师补充：本届赛事的对阵淘汰、哈夫曼编码压缩文件、编译器处理算术表达式、操作系统的文件目录，背后都是树结构在支撑。树不是教科书里的装饰，而是信息世界的骨架之一。七、课堂小结与分层作业（约5分钟）教师以三个问题收束全课：树与线性结构的本质差异是什么？二叉树三种遍历的统一逻辑是什么？递归为什么特别适合处理树？学生口述，教师提炼板书：结构层面——一对多的层次关系；方法层面——遍历即“根的访问时机”之变化；思想层面——递归定义催生递归算法。分层作业。基础层：补全学习单上另一棵二叉树的三种遍历序列，并数出其高度与叶子数。提高层：编写程序，输入按先序给出的结点信息构造二叉树并输出后序序列。挑战层：查阅资料了解哈夫曼树的基本思想，尝试说明“为什么高频字