2025 高中信息技术数据结构树的节点插入与删除操作课件

一、教学背景与目标定位演讲人目录01.教学背景与目标定位07.实践演练：操作能力的迁移与提升03.抽丝剥茧：节点插入操作详解05.攻坚克难：节点删除操作深度解析02.知识筑基：树结构的核心概念回顾04.returnroot06.returnroot08.总结升华：树操作的本质与价值2025高中信息技术数据结构树的节点插入与删除操作课件作为深耕高中信息技术教学十余年的一线教师，我始终认为，数据结构是培养学生逻辑思维与问题解决能力的核心载体。而树结构作为非线性数据结构的典型代表，其节点插入与删除操作不仅是教材的重点内容，更是学生理解"结构-操作-效率"关系的关键突破口。今天，我们将围绕这一主题展开系统学习，从基础概念到操作细节，从理论推导到实践演练，逐步揭开树结构动态维护的奥秘。01教学背景与目标定位1课程标准与学情分析《普通高中信息技术课程标准（2017年版2020年修订）》在"数据结构与算法"模块明确要求：学生需理解树的基本概念，掌握二叉树的插入、删除等操作，能运用树结构解决简单问题。结合高一学生已掌握线性表（数组、链表）的操作经验，他们对数据结构的"增删改查"已有初步认知，但对非线性结构的动态维护缺乏直观理解，尤其容易混淆不同类型树结构的操作差异。2教学目标设计基于课程标准与学情，本次课的三维目标设定如下：知识目标：掌握树、二叉树、二叉搜索树（BST）的核心定义；理解插入与删除操作对树结构的影响机制；能准确描述不同场景下插入/删除的操作步骤。能力目标：能根据给定序列手动构建二叉搜索树；能正确完成叶子节点、单分支节点、双分支节点的删除操作；能通过伪代码或流程图表示插入/删除逻辑。素养目标：体会树结构"分层存储"的设计思想，感悟数据结构选择对操作效率的影响；通过合作探究培养结构化思维与问题分解能力。3教学重难点重点：二叉搜索树的插入操作逻辑；删除操作的三种典型场景处理。难点：双分支节点删除时前驱/后继节点的定位与替换；操作后保持树结构性质的方法。02知识筑基：树结构的核心概念回顾知识筑基：树结构的核心概念回顾要掌握节点的插入与删除，必须先明确操作的"舞台"——树结构的基本特征。我们以最常用的二叉搜索树（BST）为例展开，因其天然的有序性为插入删除提供了明确的规则导向。1树的基础术语21为避免后续操作描述的歧义，首先统一关键术语：根节点：树中唯一没有父节点的节点，是所有操作的起点。路径与深度：从根到某节点的边数称为该节点的深度；树的深度是所有节点深度的最大值。节点：树的基本存储单元，包含数据域与指针域（指向子节点）。子节点与父节点：若节点A的指针指向节点B，则A是B的父节点，B是A的子节点。叶子节点：没有子节点的节点（指针域为空）。43652二叉树的特殊形态0504020301二叉树是每个节点最多有2个子节点的树结构，其常见形态对操作有直接影响：满二叉树：所有叶子节点都在同一层，且非叶子节点都有2个子节点（如深度为3的满二叉树共有7个节点）。完全二叉树：除最后一层外，其他层节点数达到最大，最后一层节点依次从左到右填充（满二叉树是完全二叉树的特例）。二叉搜索树（BST）：对任意节点，其左子树所有节点值＜该节点值，右子树所有节点值＞该节点值（等于情况可根据需求约定，本课程默认不重复）。关键提示：BST的有序性是插入删除的核心依据。例如插入值5时，只需从根开始比较：若根值＞5则转左子树，若根值＜5则转右子树，直到找到合适的叶子位置。03抽丝剥茧：节点插入操作详解抽丝剥茧：节点插入操作详解插入操作的本质是在保持树结构性质的前提下，为新节点找到正确的位置。我们以BST为例，分步骤解析其操作逻辑。1插入操作的核心步骤215无论采用递归还是迭代实现，BST插入的核心步骤可归纳为：定位插入位置：从根节点开始，比较新节点值与当前节点值：若当前节点为空（到达叶子节点下的空指针），此处即为插入位置。4若新值＞当前节点值，转向右子节点；3若新值＜当前节点值，转向左子节点；6创建并连接节点：在定位的位置创建新节点，将其父节点的对应指针（左或右）指向该新节点。2示例演示与易错点分析以序列{10,5,15,3,7,12,18}构建BST，再插入值9为例：初始树结构：根为10，左子5（左子3，右子7），右子15（左子12，右子18）。插入9时，从根10开始：9＜10→转左子5；9＞5→转右子7；9＞7→转右子（原7的右子为空），因此将9插入到7的右子位置。最终树结构：7的右指针指向9，其他节点关系不变。学生常见错误：未严格遵循BST的大小比较规则，误将新节点插入到错误的子树（如将9插入到5的左子树）；忽略空指针的判断，在非叶子节点位置错误插入（如试图将9插入到10与5之间）。3递归与迭代实现对比为帮助学生理解不同实现方式的逻辑差异，我们对比两种方法：递归实现：利用函数调用栈自动回溯，代码简洁但需注意终止条件（当前节点为空时返回新节点）。伪代码示例：definsert(root,value):ifrootisNone:returnTreeNode(value)#创建新节点ifvalueroot.value:root.left=insert(root.left,value)#递归插入左子树else:3递归与迭代实现对比root.right=insert(root.right,value)#递归插入右子树04returnrootreturnroot迭代实现：通过循环遍历树结构，需记录父节点以连接新节点。伪代码示例：1new_node=TreeNode(value)2ifrootisNone:3returnnew_node4current=root5parent=None6whilecurrentisnotNone:7parent=current8ifvaluecurrent.value:9definsert(root,value):10returnrootcurrent=current.leftelse:current=current.right#此时parent是最后一个非空节点ifvalueparent.value:parent.left=new_nodeelse:parent.right=new_nodereturnroot教学建议：递归法更符合BST的递归定义，适合初期理解；迭代法更贴近计算机底层实现，适合深入掌握指针操作。05攻坚克难：节点删除操作深度解析攻坚克难：节点删除操作深度解析删除操作比插入复杂得多，因为删除一个节点可能破坏树的连接关系，需根据被删节点的子节点数量采取不同策略。1删除操作的三种典型场景根据被删节点的子节点数量，可分为以下三种情况（假设被删节点为D）：4.1.1场景一：D是叶子节点（无子节点）操作逻辑：直接删除D，将其父节点指向D的指针置空即可。示例：在之前的BST中删除节点3（叶子节点），只需将5的左指针置空。4.1.2场景二：D有一个子节点（左或右子节点）操作逻辑：用D的子节点替换D的位置，即让D的父节点直接指向D的子节点。示例：删除节点12（只有右子节点吗？假设原树中12是叶子节点，若修改为12有左子节点11），则删除12时，将15的左指针指向11。1删除操作的三种典型场景4.1.3场景三：D有两个子节点（最复杂情况）操作逻辑：需找到D的"替代者"，使得替换后仍保持BST的有序性。替代者有两种选择：前驱节点：D的左子树中的最大值（左子树的最右节点）；后继节点：D的右子树中的最小值（右子树的最左节点）。操作步骤：找到前驱/后继节点S；将S的值复制到D的位置；删除S（此时S必为叶子节点或仅有一个子节点，转化为前两种场景）。关键原理：前驱是左子树中最大的数（小于D且最接近D），后继是右子树中最小的数（大于D且最接近D），二者都能保证替换后仍满足BST的大小关系。2示例演示与逻辑验证以删除之前BST中的根节点10（有左右子节点）为例：寻找前驱：左子树（根为5）的最大值是7（5→7，7的右子为空，故7是左子树最大值）；或寻找后继：右子树（根为15）的最小值是12（15→12，12的左子为空，故12是右子树最小值）；假设选择后继12，将10的值替换为12；然后删除原12节点（此时12是叶子节点，直接删除，将15的左指针置空）；最终树结构：根节点值变为12，左子树为5（左3，右7），右子树为15（原右子18，左子置空）。学生常见困惑：2示例演示与逻辑验证为何必须用前驱或后继？能否用其他节点替换？（不能，其他节点会破坏BST的有序性）；替换后是否需要调整原前驱/后继的父节点？（需要，例如删除前驱时，若前驱有左子节点，需将其父节点的右指针指向该左子节点）。3伪代码实现与细节处理以删除有两个子节点的情况为例，伪代码需包含前驱查找与替换逻辑：defdelete_node(root,key):ifrootisNone:06returnrootreturnroot#先定位要删除的节点1ifkeyroot.value:2root.left=delete_node(root.left,key)3elifkeyroot.value:4root.right=delete_node(root.right,key)5else:#找到要删除的节点6#情况1：无子节点或只有一个子节点7ifroot.leftisNone:8returnroot.right9returnrootelifroot.rightisNone:returnroot.left#情况2：有两个子节点，找后继（右子树最小值）min_node=find_min(root.right)root.value=min_node.value#删除右子树中的最小值节点root.right=delete_node(root.right,min_node.value)returnrootdeffind_min(node):returnrootcurrent=nodewhilecurrent.leftisnotNone:current=current.leftreturncurrent代码说明：find_min函数通过不断向左遍历找到右子树的最小值（后继）；删除原节点时，先复制值，再递归删除后继节点（此时后继节点必为叶子或单分支节点）。07实践演练：操作能力的迁移与提升实践演练：操作能力的迁移与提升理论的价值在于应用。为帮助学生将知识转化为能力，我们设计以下分层实践活动。1基础演练：手动模拟操作任务：给定初始序列{8,3,10,1,6,14,4,7,13}，完成以下操作：构建对应的BST；插入值5；删除值10（双分支节点）；删除值1（叶子节点）。操作提示：构建树时注意每次插入的路径（如插入5时，从8→3→6→4，因5＞4且4的右子为空，故插入到4的右子）；删除10时，找到其右子树最小值13（或左子树最大值7），替换后删除原13（或7）。2进阶挑战：代码调试与优化任务：以Python为工具，实现BST的插入与删除函数，并用测试用例验证。01测试用例1：插入[5,3,7]，检查树结构是否符合BST性质；02测试用例2：删除7（叶子节点），检查父节点指针是否正确；03测试用例3：删除3（有左子节点1），检查父节点是否指向1。04常见调试问题：05插入时忽略根节点为空的情况（返回None而不是新节点）；06删除双分支节点时未正确更新父节点指针（导致子树丢失）。073拓展思考：操作对树性能的影响问题：频繁的插入删除操作可能导致BST退化为链表（如插入序列为1,2,3,4），此时查找效率从O(logn)降至O(n)。如何解决这一问题？引导方向：引出平衡二叉树（如AVL树、红黑树）的概念，简要说明其通过旋转操作保持平衡的思想，为后续学习埋下伏笔。08总结升华：树操作的本质与价值1核心知识回顾插入操作的关键是"按值定位，有序连接"，利用BST的大小关系找到正确位置；01删除操作的难点是"分类处理，保持有序"，根据子节点数量选择直接删除、替换或寻找前驱/后继；02所有操作的最终目标是维护树结构的核心性质（如BST的有序性），确保后续操作（查找、遍历）的效率。032思维方法提炼结构化思维：将复杂问题分解为叶子节点、单分支、双分支等子问题，逐一解决；01.递归思想：利用树结构的自相似性，通过递归简化插入删除的逻辑描述；02.效率意识：理解操作对树结构的影响，为后续