高中信息技术选考一轮复习：树结构深度解析教学设计

高中信息技术选考一轮复习：树结构深度解析教学设计一、课程标准与考情定位本节内容对应《普通高中信息技术课程标准（2017年版2020年修订）》选择性必修1“数据与数据结构”模块中的“树与二叉树”主题。课标要求学生在理解树的基本概念、遍历方法的基础上，能够运用二叉树解决实际问题，并体会数据结构在算法设计中的价值。在浙江省选考（学业水平考试）中，本章内容通常占据约4—6分，题型集中在选择题与程序填空或读程序写结果题，重点考查二叉树的三种遍历序列互推、完全二叉树的性质运用以及哈夫曼树的构造过程。近三年试题呈现“由概念识记向算法理解过渡”的趋势，2024年1月选考中出现了基于二叉树遍历的递归程序分析题，这提示复习不能仅停留于概念复述，必须深入本质。二、学习目标与核心素养指向依据学业质量水平描述，本节复习课确立以下目标。第一，能准确描述树与二叉树的逻辑结构特征，能说出树、森林与二叉树之间的转换关系，形成抽象建模能力。第二，能手工推导二叉树的先序、中序、后序及层次遍历序列，并能由两种遍历序列唯一确定二叉树，发展计算思维中的形式化描述能力。第三，能运用完全二叉树顺序存储中父结点与子结点的序号关系（父结点编号为i，则左孩子为2i，右孩子为2i+1）解决问题，体会物理存储与逻辑结构之间的映射。第四，能依据给定权值构造哈夫曼树并计算带权路径长度，理解最优二叉树在数据压缩中的意义。三、教学重难点与突破策略重点一：二叉树三种遍历序列的相互推导。这是历年选考的必考点，也是后续递归程序阅读的基础。突破策略：采用“递归展开树”可视化方法，即手工模拟系统栈的调用过程，在每棵子树的根结点处标注“先序打印时机”“中序打印时机”“后序打印时机”。例如给定一棵小树，先序遍历时在首次访问根结点时输出，中序在访问完左子树返回根时输出，后序在访问完右子树返回根时输出。重点二：完全二叉树的性质应用。难点在于学生容易混淆满二叉树与完全二叉树的判定条件。突破策略：带领学生对比两种定义，采用“编号连续无跳跃”的判定口诀，并通过实例说明具有n个结点的完全二叉树深度为⌊log2n⌋+1。难点：由先序序列和中序序列唯一确定二叉树。学生往往知道结论但不会操作。突破策略：归纳提炼出“先序定根、中序分左右”的六字法则。通过至少三轮递进式练习（第一轮手把手示范、第二轮半独立完成、第三轮独立限时完成）实现内化。所有练习均需学生手绘递归分解图，禁止直接写出结果。四、教学过程设计（一）课堂导入：从文件系统到家族图谱的时间复杂度追问教师展示Windows资源管理器的文件夹树形结构截图，以及学校行政机构组织图。提出问题：“若用线性表存储这些层级关系，查找某一深层结点的祖先需要多少步？若改用树结构，路径查找的时间复杂度如何变化？”学生产生认知冲突——线性结构难以表达层级，而树结构天然匹配层级关系。随后教师抛出本节课的作战地图：树的概念辨析、二叉树核心性质、三种遍历与互推、完全二叉树编号规律、哈夫曼树构造。在黑板上以思维导图形式呈现，标注近五年选考对应题号与分值，使复习方向一目了然。（二）知识梳理：树与二叉树的概念辨析教师采用提问抢答形式快速过概念。树是n个结点的有限集合，n=0时为空树。非空树有且仅有一个根结点，其余结点分成m个互不相交的子树。需要特别强调：树中子树之间不能有交集，否则退化为图。教师列出对比表格：比较维度树二叉树度数限制每个结点可有任意多个孩子每个结点最多2个孩子，且分左右子树顺序无序有序空树情况可为空可为空存储结构复杂，通常用孩子兄弟表示法顺序存储或链式存储教师补充说明：尽管树看似更一般，但二叉树因左右有序而具有确定性，因此计算机中常把一般树转换为二叉树处理。转换规则为“左孩子右兄弟”，即把第一个孩子作为左子树，其余兄弟依次作为右子树。此知识点在选考中偶有出现，须结合图形记忆。（三）核心性质推导：边数与结点数的守恒关系教师引导学生推导：在一棵二叉树中，设度为0的结点数为n0，度为1的结点数为n1，度为2的结点数为n2，总结点数n=n0+n1+n2。从边的视角看，除根结点外每个结点有一条入边，故总边数为n1。同时总边数也等于n1+2n2（度为1的结点贡献1条边，度为2的结点贡献2条边）。联立两式得n0=n2+1。这个推导过程需要学生闭眼默写，而不是死记结论。教师用具体实例验证：一棵有5个度为2的结点的二叉树，叶子结点必定为6个。教师进一步延伸到深度与结点数的关系：深度为k的二叉树最多有2^k1个结点（满二叉树），第i层最多有2^(i1)个结点。这些边界值常出现在填空题的极端条件判断中。（四）遍历序列互推：先序定根、中序分左右教师先以一棵具体二叉树演示三种遍历过程。二叉树结构为：根A，A的左孩子B，B的右孩子D，A的右孩子C，C的左孩子E。先序序列：ABDCE。中序序列：BDAEC。后序序列：DBECA。教师逐步演示先序和中序互推过程。先序第一个字符A必为根。在中序序列中找到A，左侧“BD”为左子树的中序，右侧“EC”为右子树的中序。根据中序长度，先序中A之后的连续2个字符“BD”为左子树的先序。递归处理左子树：B为左子树根，中序中B左侧为空，右侧为D，故D为B的右孩子。至此左子树还原完毕。右子树同理，C为根，E为C的左孩子。教师强调，必须要求学生用完整递归框架书写过程，即每一步都要写出“当前序列范围→确定的根→左右子树序列划分”。限时训练两道变式题：已知后序与中序求二叉树，已知层序与中序求二叉树。后序遍历的根在序列末尾，层序遍历的根为第一个结点，两者的左右子树划分依然依赖中序中根的位置。（五）完全二叉树编号规律：层序连续存储的算法基础教师给出定义：深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号1至n的结点一一对应时，称为完全二叉树。教师特别强调“编号连续无跳跃”这一判定特征，并用反例说明：若某结点只有右孩子而无左孩子，则编号必然中间缺号，不符合完全二叉树定义。教师列出核心公式：（1）具有n个结点的完全二叉树深度为⌊log2n⌋+1。（2）顺序存储时，编号为i的结点（i>1），其父结点编号为⌊i/2⌋。（3）编号为i的结点，若2i≤n，则左孩子编号为2i；若2i+1≤n，则右孩子编号为2i+1；若2i>n，则无左孩子；若2i+1>n且2i≤n，则只有左孩子。（4）最后一个非叶子结点编号为⌊n/2⌋。教师通过具体习题巩固：一个完全二叉树有100个结点，求度为1的结点个数。解答：因为100为偶数，最后一个叶子结点的父结点为50号，此结点只有左孩子（编号100），没有右孩子，故度为1的结点个数为1。此类题目要求学生能灵活运用编号关系与结点总数奇偶性之间的关系。（六）哈夫曼树与哈夫曼编码教师以一段英文文本中各字母出现频率为背景，提出如何使编码总长度最短的问题。固定长度编码显然不是最优，按频率分配编码长度可以压缩数据。构造步骤强调为四个字：选小、合并、替换、重复。具体操作：在权值集合中选两个最小权值作为左右子树，合并后新结点权值为两者之和，放回集合，重复直到只剩一棵树。教师强调，构造过程中必须注意新结点与原有结点的区分，且每次必须重新选取两个最小权值的结点（包括刚生成的新结点）。带权路径长度计算：所有叶子结点的权值乘以其路径长度之和。教师展示一个计算范例：权值为2，3，4，7。先选2和3，合并为5，集合变为5，4，7。再选4和5，合并为9，集合变为9，7。最后选7和9，合并为16。树构造完成后计算WPL=2×3+3×3+4×2+7×1=30。教师指出，若左右子树交换位置，WPL不变但编码不同，这是允许的。教师补充哈夫曼编码的不等长与前缀码特性：任一编码都不是另一编码的前缀，因此解码无歧义。考试中常要求根据编码表判断是否属于前缀码，方法为将每个编码逐一与其余编码比较是否为前缀关系。（七）课堂练习与即时反馈练习1（概念辨析）：下列哪棵二叉树是满二叉树，哪棵是完全二叉树，哪棵既非满也非完全？教师呈现三幅图，学生两分钟内作答并说明理由。练习2（遍历互推）：已知先序序列为EFHIGJK，中序序列为HFIEJKG，请还原二叉树并写出后序序列。作答后同桌互批，教师投影一位学生的完整递归分解图进行讲评。练习3（编号性质）：一个完全二叉树有300个结点，问叶子结点有多少个？解答过程：因为300为偶数，所以n1=1。由n0=n2+1及n0+n1+n2=300，得n2=(2991)/2=149，n0=150。教师给出快速解法：对于完全二叉树，叶子数等于⌈n/2⌉，即150。练习4（哈夫曼）：权值集合为1，3，5，8，12，构造哈夫曼树并计算WPL。学生独立完成后，教师用交互式课件动态演示合并过程，展示标准WPL计算结果为n0=5个叶子，WPL=1×4+3×4+5×3+8×2+12×1=4+12+15+16+12=59。教师提醒若构造顺序不同但始终遵循最小两个合并，WPL唯一。（八）易错点专题总结第一，遍历序列中不能只靠记忆“左右根”之类的口诀机械执行，必须理解递归遍历时结点的访问时机。第二，由先序与后序序列不能唯一确定二叉树，因为无法区分单分支结点的左右方向。第三，完全二叉树顺序存储时，1号位对应根结点，非从0开始。第四，哈夫曼树没有度为1的结点，但不经过优化的普通构造过程中新合并结点可能成为后续最小者。第五，在求结点总数时，若n1为1，则n0与n2的关系仍满足n0=n2+1。教师将易错点整理成口诀：“先定根，中分界，后序末尾根相迎；编号从一不回头，叶子过半向上取；哈夫曼中无一度，选小合并不犹豫。”（九）布置分层作业与延伸任务A层基础题：完成教科书课后习题中的二叉树遍历、结点数计算及哈夫曼构造题。B层提升题：给定一棵二叉树的层次序列与中序序列，编程实现还原算法并输出后序序列，代码语言不限。C层挑战题：利用二叉树遍历实现表达式树的计算，给定中缀表达式建立二叉树并求值。教师说明三种层级的完成要求，鼓励学生至少完成B层。同时预告下节复习课的专题为“图的结构与遍历”，要求预习图的邻接矩阵与邻接表存储。五、教学反思与后续调整本节复习课的设计重心放在“概念结构化”与“算法操作化”。时间分配上，概念梳理约8分钟，性质推导约6分钟，遍历互推约18分钟，完全二叉树约10分钟，哈夫曼约10分钟，课堂练习与讲评约8分钟。教师需根据班级实际掌握情况动态压缩或延展某个环节，例如若哈夫曼构造错误率高，可增加一个变式练习而压缩练习3的讲解时间。在后续二轮复习中，可将树结构综合题与递归程序阅读结合，设计如“根据递归函数的栈帧变化推导输出序列”的专题微课。同时建议学生建立“树结构易错题私人订制笔记本”，记录每次错因分析，考前集中翻看。六、作业设计说明与评测方式课后作业采取线上线下混合形式。线上平台推送10道客观题，覆盖概念选择、性质判断与遍历序列互推，平台自动批改并生成正确率报告。线下书面作业包含两道综