2025 高中信息技术数据结构树的节点 Morris 遍历算法课件

一、从传统遍历到Morris遍历：问题的提出与算法背景演讲人01从传统遍历到Morris遍历：问题的提出与算法背景02Morris遍历的核心原理与实现步骤03Morris遍历与传统遍历的对比分析04高中信息技术教学中的Morris遍历教学设计05总结：Morris遍历的思想价值与学习启示目录2025高中信息技术数据结构树的节点Morris遍历算法课件作为一名深耕高中信息技术教学十余年的教师，我始终关注着数据结构教学中的难点与创新。在二叉树遍历这一核心知识点上，传统的递归与迭代方法虽经典，却常因空间复杂度问题让学生困惑——尤其是面对大规模树结构时，递归的栈溢出风险与迭代栈的空间消耗，成为了学生理解“高效遍历”的一道坎。直到接触Morris遍历算法，我意识到这是一把打开“常数空间遍历”之门的钥匙。今天，我将以“Morris遍历算法”为核心，从原理到实践，为同学们展开一场清晰、深入的讲解。01从传统遍历到Morris遍历：问题的提出与算法背景1传统二叉树遍历的局限性在正式学习Morris遍历前，我们需要先回顾二叉树遍历的三种经典方式：前序（根左右）、中序（左根右）、后序（左右根）。无论是递归实现还是基于栈的迭代实现，其核心逻辑都是通过“回溯”来访问节点——递归隐式依赖系统栈，迭代则显式使用栈结构存储待访问的节点。以中序遍历为例，递归实现的代码如下（伪代码）：definorder(root):ifrootisNone:1传统二叉树遍历的局限性returninorder(root.left)visit(root)inorder(root.right)其空间复杂度为O(h)（h为树的高度），最坏情况下（如退化为链表的树）达到O(n)。这在处理大规模树结构（如百万级节点的文件系统树）时，会导致栈溢出或内存占用过高的问题。2Morris遍历的核心价值：常数空间的突破1979年，美国计算机科学家JamesH.Morris提出了一种无需递归与栈的二叉树遍历算法——Morris遍历。其核心思想是利用二叉树中大量空闲的右指针（即叶子节点或单孩子节点的右空指针），临时构建“线索”，指向当前节点的后继节点，从而在遍历过程中通过线索回溯，避免额外空间存储。这一设计将空间复杂度降至O(1)，同时保持时间复杂度为O(n)（每个节点最多被访问两次），完美解决了传统遍历的空间瓶颈。记得我第一次向学生展示Morris遍历的演示动画时，有位学生惊叹：“原来空指针还能这么用！”这正是算法的精妙之处——它不依赖任何额外数据结构，而是“就地取材”，利用树本身的结构完成遍历。02Morris遍历的核心原理与实现步骤1关键概念：前驱节点与线索化要理解Morris遍历，必须先明确两个概念：前驱节点（Predecessor）：在中序遍历中，当前节点的前驱是其左子树中最右的节点（即左子树中“最后一个被访问的节点”）。例如，对于根节点A，若其左子树的最右节点是B，则B是A的前驱。线索化（Threading）：将前驱节点的右指针（原本为空）临时指向当前节点，形成一条“线索”，使得遍历到前驱节点时，可以通过该线索回到当前节点，完成回溯。2中序遍历的Morris实现步骤（重点）以中序遍历为例，Morris算法的具体步骤可分为以下6步（结合图1演示，此处假设树结构为：根节点1，左孩子2，右孩子3；节点2左孩子4，右孩子5；节点4无孩子，节点5无孩子）：2中序遍历的Morris实现步骤（重点）初始化当前节点设当前节点（current）为根节点（如节点1）。步骤2：判断当前节点的左子树是否存在若左子树不存在（current.left==None）：直接访问当前节点，然后将current移动到右子节点（current=current.right），进入下一步循环。若左子树存在（current.left!=None）：找到左子树的前驱节点（predecessor），即左子树中最右的节点（predecessor=current.left；循环直到predecessor.right==None或predecessor.right==current）。2中序遍历的Morris实现步骤（重点）初始化当前节点步骤3：处理前驱节点的右指针若前驱节点的右指针为空（predecessor.right==None）：将其右指针指向当前节点（predecessor.right=current），完成线索化；然后将current移动到左子节点（current=current.left），继续处理左子树。若前驱节点的右指针指向当前节点（predecessor.right==current）：说明左子树已遍历完毕，此时需要：恢复前驱节点的右指针（predecessor.right=None）；访问当前节点；将current移动到右子节点（current=current.right）。2中序遍历的Morris实现步骤（重点）初始化当前节点步骤4：循环直至current为None重复步骤2-3，直到current指向空，遍历结束。以图1为例，具体遍历过程如下：初始current=1，左子树存在（节点2）。找到前驱（节点2的最右节点是5），5.right为空，故5.right=1，current移动到2。current=2，左子树存在（节点4）。找到前驱（节点4的最右节点是4自身），4.right为空，故4.right=2，current移动到4。current=4，左子树不存在，访问4；current移动到4.right（即2）。2中序遍历的Morris实现步骤（重点）初始化当前节点current=2，再次检查左子树，找到前驱4，此时4.right=2（已线索化），故恢复4.right=None，访问2；current移动到2.right（即5）。current=5，左子树不存在，访问5；current移动到5.right（即1）。current=1，左子树已处理（前驱5的right=1），恢复5.right=None，访问1；current移动到1.right（即3）。current=3，左子树不存在，访问3；current移动到3.right（空），遍历结束。最终访问顺序为：4→2→5→1→3，符合中序遍历的预期。3前序与后序遍历的Morris适配Morris遍历的核心逻辑可扩展至前序与后序遍历，关键在于调整“访问节点”的时机：前序遍历：在第一次访问当前节点时（即线索化之前）进行访问，因为前序遍历要求“根→左→右”，此时左子树尚未处理，当前节点是最先被访问的。后序遍历：需要额外处理“右路径逆序访问”，因为后序遍历的“左右根”顺序要求在左右子树处理完毕后访问根节点。此时需利用线索化过程中形成的路径，逆序访问从当前节点左子树的最右节点到前驱节点的路径。03Morris遍历与传统遍历的对比分析1空间复杂度：O(1)vsO(h)传统递归与迭代遍历的空间复杂度为O(h)（h为树高），而Morris遍历仅使用有限的临时变量（如current、predecessor），空间复杂度严格为O(1)。这一优势在处理大规模树结构（如数据库索引树、操作系统文件树）时尤为显著，可避免内存溢出风险。3.2时间复杂度：均为O(n)，但常数因子不同虽然两者时间复杂度均为O(n)，但Morris遍历中每个节点最多被访问两次（一次线索化，一次遍历），而传统遍历每个节点仅被访问一次。因此，Morris遍历的实际运行时间略长于传统方法，但在空间敏感场景中，这种时间换空间的策略是可接受的。3适用场景的选择传统遍历：适用于小规模树结构或对时间效率要求高的场景，代码简洁易实现（尤其是递归）。Morris遍历：适用于内存受限的环境（如嵌入式系统、大规模数据处理），或需要避免栈溢出的场景（如深度极大的树）。我曾带领学生用两种方法遍历一个深度为10000的单链表树（退化为链表的二叉树），递归方法直接抛出“栈溢出异常”，迭代方法占用了约80KB的栈空间，而Morris遍历仅用了几个变量，内存占用几乎可以忽略——这正是Morris遍历的实践价值。04高中信息技术教学中的Morris遍历教学设计1教学目标的分层设定能力目标：能对比分析Morris遍历与传统遍历的优劣，能在具体问题中选择合适的遍历方法。03素养目标：通过算法优化的探索，培养“计算思维”中的“抽象与建模”能力，体会空间与时间的权衡思想。04根据《普通高中信息技术课程标准（2017年版2020年修订）》对“数据结构”模块的要求，结合Morris遍历的特点，教学目标可分为：01知识目标：理解Morris遍历的核心思想（线索化与前驱节点），掌握中序遍历的Morris实现步骤。022教学过程的阶梯式设计环节1：温故知新——传统遍历的复习与问题导入（10分钟）通过提问与代码回顾，引导学生总结传统遍历的空间复杂度问题。例如：“递归遍历的‘隐形开销’是什么？”“当树的高度达到10万层时，递归会出现什么问题？”通过具体案例（如处理社交媒体关系树）引发认知冲突，自然引出“能否用O(1)空间完成遍历？”的问题。环节2：抽丝剥茧——Morris遍历原理的探究（25分钟）动画演示：用可视化工具（如VisuAlgo）展示Morris中序遍历的过程，重点标注线索的建立与断开。手动模拟：分发树结构卡片（如节点1-5的二叉树），让学生分组模拟遍历过程，记录每一步current的移动与线索的变化。2教学过程的阶梯式设计环节1：温故知新——传统遍历的复习与问题导入（10分钟）关键提问：“为什么选择前驱节点的右指针作为线索？”“线索断开的意义是什么？”通过追问推动学生理解算法的“自修正”特性。环节3：代码实现——从原理到代码的转化（15分钟）提供伪代码框架，引导学生填充关键步骤（如寻找前驱、线索化判断）。例如：defmorris_inorder(root):current=rootwhilecurrentisnotNone:ifcurrent.leftisNone:visit(current)current=current.right2教学过程的阶梯式设计环节1：温故知新——传统遍历的复习与问题导入（10分钟）else:predecessor=current.left#寻找前驱：左子树的最右节点whilepredecessor.rightisnotNoneandpredecessor.right!=current:predecessor=predecessor.rightifpredecessor.rightisNone:predecessor.right=current#建立线索current=current.leftelse:2教学过程的阶梯式设计环节1：温故知新——传统遍历的复习与问题导入（10分钟）predecessor.right=None#恢复线索visit(current)current=current.right强调“predecessor.right的双重含义”（空表示未线索化，指向current表示已线索化），这是学生最易混淆的点。环节4：对比与拓展——深化理解（10分钟）通过表格对比三种遍历方法的空间、时间复杂度及适用场景，鼓励学生讨论：“在编程竞赛中，Morris遍历是否值得推广？”“如何用Morris遍历实现后序？”通过开放性问题激发思维，为有余力的学生提供拓展方向。3常见误区与突破策略误区1：认为线索化会破坏原树结构。实际上，Morris遍历在遍历完成后会恢复所有被修改的右指针（仅临时修改），因此原树结构保持不变。01误区2：前驱节点的寻找错误。需强调“前驱是左子树的最右节点”，即从current.left出发，一直向右走直到无法继续（predecessor.right为None或current）。02突破策略：通过“找朋友”游戏强化前驱概念（每个节点的“中序前一个朋友”是其左子树的最右节点），用彩色粉笔在黑板上标注线索的建立与断开过程，增强直观性。0305总结：Morris遍历的思想价值与学习启示总结：Morris遍历的思想价值与学习启示回顾Morris遍历的学习过程，我们不仅掌握了一种高效的遍历算法，更重要的是体会到了“就地取材”的算法设计智慧——它没有引入复杂的数据结构，而是深入挖掘问题本身的特性（二叉树的空指针资源），通过巧妙的线索化实现了空间复杂度的突破。对于同学们而言，学习Morris遍历的意义远不止于应对考试。它提醒我们：在解决问题时，不要局限于已有的工具（如栈、递归），而应回到问题本质，思考“是否有更高效的资源利用方式”。正如计算机科学家Dijkstra所说：“算法设计的核心是对问题