高中信息技息技术选修一《树与二叉树》教学设计

高中信息技息技术选修一《树与二叉树》教学设计一、教材分析《树与二叉树》是浙教版高中信息技术选修一《数据结构与算法》模块的第四章首节，承接前三章线性表、栈、队列的线性结构认知，开启非线性结构的系统教学。教材以“家谱整理”情境切入，引导学生从生活经验抽象出树形结构，进而聚焦二叉树的定义、性质、存储与遍历。该节内容在知识体系中具有承上启下作用：向上奠定图、查找、排序等后续章节的结构基础；向下关联初中信息技术“数据编码与压缩”中的哈夫曼树应用。教材编排遵循“概念—性质—存储—操作—应用”逻辑链，核心在于建立递归思维与分治策略的认知模型。考虑到新高考背景下“计算思维”核心素养的考查导向，教学不能停留在语法记忆，而要突出抽象建模、算法推演、程序实现的完整链条。二、学情分析目标学习者为高二年级选修信息技术学生，已完成Python基础语法、函数递归、面向对象基础及线性结构学习。普遍具备顺序、分支、循环程序设计能力，理解列表、字典等内置结构操作。但非线性结构的拓扑认知存在认知鸿沟：多数学生习惯线性索引思维，难以直观掌握“左子树、右子树”递归分解；指针引用机制在Python隐式引用语境下易形成“变量即对象”误区；遍历算法的递归调用栈与显式栈模拟的等价转换是高阶难点。问卷调查显示，65%学生对递归终止条件把握不稳，72%未建立存储结构与算法效率的关联意识。教学需搭建从具象图形到抽象代码、从静态结构到动态执行的多层脚手架。三、教学目标1.信息意识：能结合家谱、组织架构、文件目录等场景识别树形特征，理解数据组织形式对检索效率的决定性影响，树立“结构服务于问题”观念。2.计算思维：掌握二叉树五条核心性质推导逻辑，熟练应用递归分治完成遍历、求深度、判断相似等算法设计，体会栈与递归的内在等价性。3.数字化学习与创新：基于Python实现二叉链表存储与四种遍历算法，利用可视化工具动态演示执行流程，完成表达式树构建与后缀表达式求值综合案例。4.信息社会责任：规范代码注释与变量命名，体会算法确定性与可验证性，培养严谨逻辑与工程规范意识。四、教学重难点重点：二叉链表存储表示、递归遍历算法实现、树与森林转换为二叉树规则。难点：非递归遍历算法中栈的状态维护、由遍历序列还原二叉树唯一性判断、哈夫曼树构建贪心策略理解。五、教学策略与环境准备采用“情境导入—模型构建—算法推演—工程实践—迁移拓展”五阶段教学模式。引入Python可视化库`graphviz`与在线平台`VisuAlgo`辅助动态演示，准备“家谱卡片”“遍历序列磁贴”实物教具。预设“表达式求值器”项目式学习任务，贯穿两课时教学。配备分层练习册：基础题巩固概念，进阶题强化代码阅读，挑战题引导算法优化。六、教学过程（一）情境导入：从家谱到抽象模型（10分钟）教师投影展示某家族五代家谱局部截图，提问：“若要用程序记录‘某人所有祖辈’‘某人所有同辈堂兄弟’‘某家族总人数’，用列表如何存储？检索复杂度如何？”学生分组讨论3分钟。预期回答：列表需额外字段记录父子关系，查找祖辈需多次遍历，时间复杂度$O(n^2)$。教师引导：“线性结构难以直接表达‘一对多’层级关系。”引入树定义：$n(n\ge0)$个节点的有限集，$n=0$为空树，否则存在唯一根节点，其余节点分为$m(m\ge0)$个互不相交的子树。强调“互不相交”“递归定义”两个关键词。现场分发家谱卡片，每生一张，按“长辈在前、同辈左右”站位，全班形成一棵有序树。提问：“根是谁？叶子有几个？第3层节点数最多几个？”引出度、层次、深度术语。板书树的基本术语表，要求学生现场标注自家卡片位置。（二）概念建模：二叉树特殊性与核心性质（20分钟）聚焦二叉树定义：每个节点度$\le2$，左右子树有序不可随意颠倒。对比有序树与二叉树区别：普通树节点度不限，二叉树严格二叉。演示“满二叉树”“完全二叉树”“斜树”极端形态。重点攻克五条性质：性质1：第$i$层至多$2^{i1}$个节点。数学归纳法证明：$i=1$根节点1个成立，假设第$k$层最多$2^{k1}$，第$k+1$层每个节点最多2个孩子，故$\le2\times2^{k1}=2^k$。性质2：深度$k$的二叉树至多$2^k1$个节点。等比数列求和$S=\sum_{i=1}^k2^{i1}=2^k1$。性质3：$n_0=n_2+1$。度为0节点数等于度为2节点数加1。证明：设总节点数$n=n_0+n_1+n_2$。边数$B=n1$（根无入边）。又$B=0\timesn_0+1\timesn_1+2\timesn_2$。联立消元得$n_0=n_2+1$。此性质是推导完全二叉树节点编号规律、哈夫曼树构建的理论基石。性质4：深度$k$且有$n$个节点的完全二叉树，按层序编号时，任一节点$i(1\lei\len)$满足：父节点$\lfloori/2\rfloor$（$i>1$），左孩子$2i$（$2i\len$），右孩子$2i+1$（$2i+1\len$）。现场演练：已知完全二叉树15节点，求第10节点父节点、孩子节点编号。性质5：具有$n$个节点的完全二叉树深度$\lfloor\log_2n\rfloor+1$。由性质2逆推：$2^{k1}\len<2^k\Rightarrowk1\le\log_2n<k\Rightarrowk=\lfloor\log_2n\rfloor+1$。课堂练习：判断命题。“深度为4的二叉树至少4个节点”“有100个节点的完全二叉树，度为1的节点最多1个”。学生举手响应，教师追问理由，强化逻辑推演。（三）存储结构：从图形到内存映射（15分钟）展示二叉链表节点类设计：```pythonclassBiTNode:def__init__(self,data):self.data=dataself.lchild=Noneself.ltag=0线索标志，后续线索二叉树用self.rchild=Noneself.rtag=0```对比顺序存储：仅适用完全二叉树，一般二叉树需补齐空位浪费空间，稀疏矩阵类比加深理解。重点讲解Python引用语义：`node.lchild=BiTNode(5)`实质是将新对象地址赋给引用字段。现场编码构建一棵三层树：```pythonroot=BiTNode('A')root.lchild=BiTNode('B')root.rchild=BiTNode('C')root.lchild.lchild=BiTNode('D')root.lchild.rchild=BiTNode('E')```利用`id()`函数打印对象地址，验证`root.lchild`与`root.rchild`指向不同对象。引入“空树用None表示”约定。演示`graphviz`生成DOT语言脚本，渲染树形图，让学生直观对应代码结构与图形拓扑。布置微任务：修改代码构建右斜树，观察内存链式分布变化。（四）算法核心：遍历策略的递归与非递归实现（30分钟）遍历是二叉树操作的原子动作。定义：按根节点访问时机分先序(NLR)、中序(LNR)、后序(LRN)，加上层次遍历共四类。1.递归实现（核心框架）：```pythondefpre_order(node):ifnodeisNone:returnprint(node.data,end='')访问根pre_order(node.lchild)遍历左pre_order(node.rchild)遍历右```讲解“递归三要素”：终止条件`nodeisNone`、处理逻辑`print`、缩小规模`node.lchild/rchild`。现场演示调用栈变化：`pre_order(A)`>`pre_order(B)`>`pre_order(D)`>`None`返回>`pre_order(E)`...学生在纸上画调用栈帧图，标注参数、返回地址、局部变量。2.非递归先序（显式栈模拟）：核心思想：向左走到底，沿途入栈；无法向左时出栈，转向右。```pythondefpre_order_iter(root):stack=[]node=rootwhilenodeorstack:whilenode:print(node.data,end='')stack.append(node)node=node.lchildnode=stack.pop()node=node.rchild```重点剖析`whilenode:`内层循环与`node=node.rchild`外层衔接。易错点：出栈后必须处理右子树，而非直接循环。邀请学生上台扮演“指针node”与“栈stack”，物理演绎入栈出栈动作。3.非递归中序（区别仅在访问时机）：```pythondefin_order_iter(root):stack=[]node=rootwhilenodeorstack:whilenode:stack.append(node)node=node.lchildnode=stack.pop()print(node.data,end='')出栈时访问node=node.rchild```对比先序：访问语句前移至出栈后。引导学生总结“模板套路”：入栈左链、出栈访问、转向右链。4.非递归后序（双栈法/单栈带标记法）：采用单栈带访问标记法，贴近工程实践：```pythondefpost_order_iter(root):stack=[(root,False)]whilestack:node,visited=stack.pop()ifnodeisNone:continueifvisited:print(node.data,end='')else:stack.append((node,True))stack.append((node.rchild,False))stack.append((node.lchild,False))```讲解“后进先出”反转顺序：压入顺序根(标记True)、右、左，出栈顺序左、右、根。类比先序压栈顺序根、右、左，出栈根、左、右，揭示遍历本质是栈对递归顺序的重排。5.层次遍历（队列实现）：```pythonfromcollectionsimportdequedeflevel_order(root):ifnotroot:returnq=deque([root])whileq:node=q.popleft()print(node.data,end='')ifnode.lchild:q.append(node.lchild)ifnode.rchild:q.append(node.rchild)```强调队列先进先出保证层层推进。对比栈的深度优先与队列的广度优先，引出图遍历DFS/BFS统一视角。课堂对练：给定先序`ABDG`表空），学生分组在白板还原树形，写出中序、后序、层次序列。教师巡视纠正“中序根节点位置”“后序根节点最后”常见错误。（五）工程实践：表达式树构建与求值器开发（35分钟）项目驱动：开发一个支持`+/^()`的中缀表达式计算器，核心流程：中缀转后缀>构建表达式树>后序遍历求值。步骤1：中缀转后缀（调度场算法简化版）。```pythondefinfix_to_postfix(tokens):prec={'+':1,'':1,'':2,'/':2,'^':3}op_stack=[]output=[]fortokenintokens:iftoken.isdigit():output.append(token)eliftoken=='(':op_stack.append(token)eliftoken==')':whileop_stack[1]!='(':output.append(op_stack.pop())op_stack.pop()弹出左括号else:whileop_stackandop_stack[1]!='('andprec[op_stack[1]]>=prec[token]:output.append(op_stack.pop())op_stack.append(token)whileop_stack:output.append(op_stack.pop())returnoutput```讲解运算符优先级与结合性处理，`^`右结合特殊判断略过简化版。步骤2：后缀表达式构建表达式树。```pythondefbuild_exp_tree(postfix):stack=[]fortokeninpostfix:iftoken.isdigit():stack.append(BiTNode(token))else:right=stack.pop()left=stack.pop()node=BiTNode(token)node.lchild=leftnode.rchild=rightstack.append(node)returnstack[0]```演示`34+2`构建过程：数字入栈成叶子，遇运算符弹两棵树合成新树压回。最终栈顶即根节点``。步骤3：后序遍历求值（后序天然适合后缀计算）。```pythondefevaluate(node):ifnode.lchildisNoneandnode.rchildisNone:returnint(node.data)left_val=evaluate(node.lchild)right_val=evaluate(node.rchild)op=node.dataifop=='+':returnleft_val+right_valifop=='':returnleft_valright_valifop=='':returnleft_valright_valifop=='/':returnleft_val/right_valifop=='^':returnleft_valright_val```完整测试用例：`(3+4)25^2`>后缀`34+252^`>树构建>结果`11`。学生分组完成代码集成调试，教师巡视指导异常处理（除零、非法字符）。（六）拓展深化：树森林转换与哈夫曼编码预习（15分钟）6.树/森林与二叉树互转规则：树转二叉树：“左孩子右兄弟”法。连线：同一父节点下兄弟相连；去线：保留父指向长子，删其余；层次调整：以根为轴顺时针旋转45°。演示多叉树转二叉树动画，强调“第一个孩子做左孩子，兄弟做右孩子”口诀。森林转二叉树：各树转二叉树，第一棵树根为二叉树根，其余树根作为前一棵树根的右孩子链接。二叉树转树：“左孩子右兄弟”逆操作。若节点是左孩子，其右链均为兄弟；若是右孩子，无左孩子。7.哈夫曼树引入：问题：给定$n$权值$\{w_1,w_2,...,w_n\}$，构建带权路径长度$WPL=\sumw_il_i$最小的二叉树。贪心策略：每次选取权值最小的两棵树合并。现场演算$\{5,29,7,8,14,23,3,11\}$构建过程，利用最小堆优化选择复杂度$O(n\logn)$。展示编码结果：权值小编码长，权值大编码短，前缀码特性保证唯一解码。关联初中“数据压缩”课程，预告下节课哈夫曼编码程序实现。（七）总结提升与