高中信息技术（必选1）X1-09-02二叉树的基本操作知识点

高中信息技术（必选1）X1-09-02二叉树的基本操作知识点整理本课程聚焦二叉树的基本操作，是高中信息技术（必选1）数据结构模块的核心内容之一。通过学习，需掌握二叉树的遍历、节点的插入与删除、深度/高度计算等核心操作，理解各操作的原理、实现逻辑及适用场景，为后续复杂数据结构的学习奠定基础。以下是课程主要知识点梳理，每个知识点配套2-5个练习题及详细解析。一、核心知识点梳理知识点1：二叉树的遍历（重点）二叉树的遍历是指按照一定的规则访问二叉树中的所有节点，且每个节点仅访问一次。常用的遍历方式有4种，核心区别在于访问根节点、左子树、右子树的顺序不同：前序遍历（根-左-右）：先访问根节点，再递归遍历左子树，最后递归遍历右子树；中序遍历（左-根-右）：先递归遍历左子树，再访问根节点，最后递归遍历右子树；后序遍历（左-右-根）：先递归遍历左子树，再递归遍历右子树，最后访问根节点；层序遍历（按层访问）：从根节点开始，按从上到下、从左到右的顺序依次访问每一层的节点。关键要点：遍历的核心是“递归思想”（前/中/后序常用）和“队列辅助”（层序常用）；已知前序+中序或中序+后序可唯一确定一棵二叉树，前序+后序无法唯一确定。练习题及答案解析题1：已知某二叉树的根节点为A，左子树节点为B、D、F，右子树节点为C、E、G，且结构为：A的左孩子是B，右孩子是C；B的左孩子是D，右孩子是F；C的右孩子是E；E的左孩子是G。请写出该二叉树的前序、中序、后序遍历序列。答案：前序：ABDFCEG；中序：DBFACGE；后序：DFBGECA解析：前序按“根-左-右”，先访问A，再遍历A的左子树（B为根，先B，再B的左子树D，再B的右子树F），最后遍历A的右子树（C为根，先C，C左子树为空，再C的右子树E，E的左子树G，E右子树为空）；中序按“左-根-右”，先遍历A左子树（D的左空→访问D→D右空；再访问B→B右子树F的左空→访问F→F右空），再访问A，最后遍历A右子树（C的左空→访问C→C右子树E的左子树G→访问G→访问E→E右空）；后序按“左-右-根”，先遍历A左子树（D→F→B），再遍历A右子树（G→E→C），最后访问A。题2：已知某二叉树的中序遍历序列为“左-根-右”对应“4251637”，前序遍历序列为“1245367”，请确定该二叉树的结构，并写出后序遍历序列。答案：二叉树结构：根节点1；1的左孩子2，右孩子3；2的左孩子4，右孩子5；3的左孩子6，右孩子7；后序遍历序列：4526731解析：前序遍历第一个节点为根节点，即1；中序序列中1左侧“425”为左子树节点，右侧“637”为右子树节点。前序序列中1之后的节点“245”为左子树的前序遍历，第一个节点2为左子树的根；中序序列中2左侧“4”为2的左子树，右侧“5”为2的右子树。前序序列中左子树之后的“367”为右子树的前序遍历，第一个节点3为右子树的根；中序序列中3左侧“6”为3的左子树，右侧“7”为3的右子树。据此构建二叉树后，按后序“左-右-根”遍历即可得到序列。题3：下列关于二叉树遍历的说法，正确的是（）A.前序遍历和后序遍历结果相同的二叉树一定是空树B.中序遍历结果为“abc”的二叉树，其根节点一定是bC.层序遍历需要借助队列实现D.已知前序和后序遍历序列，可唯一确定二叉树结构答案：C解析：A选项错误，单节点二叉树的前序和后序遍历结果均为该节点，非空树；B选项错误，中序遍历为“abc”的二叉树，根节点可能是b（左a右c）、c（左子树中序ab，根c）或a（右子树中序bc，根a）；C选项正确，层序遍历按层访问，需用队列存储当前层节点，依次出队并将其左右孩子入队；D选项错误，前序+后序无法唯一确定，例如根节点A，左孩子B和根节点A，右孩子B，两者前序均为AB，后序均为BA，但结构不同。知识点2：二叉树节点的插入（基础）二叉树节点的插入需遵循“不破坏二叉树结构特性”的原则，常用场景为“二叉排序树（BST）的插入”（课程核心插入场景），二叉排序树的特性：左子树所有节点值＜根节点值，右子树所有节点值＞根节点值，左右子树均为二叉排序树。插入步骤：1.若二叉树为空，新节点作为根节点；2.若二叉树非空，将新节点值与根节点值比较：①若新值＜根值，递归插入到左子树；②若新值＞根值，递归插入到右子树；③若新值与根值相等，一般不插入（避免重复节点）。关键要点：插入位置唯一（二叉排序树中）；插入操作的时间复杂度与二叉树高度相关，理想平衡状态下为O(log₂n)，最坏（单支树）为O(n)。练习题及答案解析题1：已知一棵二叉排序树的节点值依次为5、3、7、2、4、6、8，若插入新节点值为5.5，请问新节点将作为哪个节点的子节点？是左孩子还是右孩子？答案：新节点作为6的左孩子。解析：二叉排序树插入需按值比较：①新值5.5与根节点5比较，5.5＞5，进入右子树；②右子树根节点为7，5.5＜7，进入左子树；③左子树根节点为6，5.5＜6，进入左子树；④6的左子树为空，因此新节点作为6的左孩子插入。题2：若对空二叉树依次插入节点值3、1、4、2、5，得到的二叉排序树的前序遍历序列是什么？答案：前序遍历序列：31245解析：插入过程：①插入3，树为根3；②插入1，1＜3，作为3的左孩子；③插入4，4＞3，作为3的右孩子；④插入2，2＞1且2＜3，进入1的右子树，1的右子树为空，作为1的右孩子；⑤插入5，5＞4且5＞3，进入4的右子树，4的右子树为空，作为4的右孩子。构建后的树结构：根3，左孩子1（右孩子2），右孩子4（右孩子5），前序按“根-左-右”遍历为31245。题3：下列关于二叉排序树插入的说法，错误的是（）A.插入后仍满足二叉排序树的特性B.插入的新节点一定是叶子节点C.若插入值已存在，可直接覆盖原节点值D.空树插入第一个节点后，该节点为根节点答案：C解析：A选项正确，插入的核心原则是保持二叉排序树特性；B选项正确，插入时仅在空的位置插入，因此新节点必为叶子节点；C选项错误，二叉排序树一般不允许重复节点，插入值已存在时通常不插入，而非覆盖；D选项正确，空树插入第一个节点，自然成为根节点。知识点3：二叉树节点的删除（难点）节点删除是二叉树操作的难点，核心仍以“二叉排序树的删除”为重点，需兼顾“删除节点后仍保持二叉排序树特性”，删除分为三种情况：1.待删除节点为叶子节点（无左右子树）：直接删除该节点，将其双亲节点对应的子树指针置空；2.待删除节点仅有一棵子树（左或右）：用该节点的子树替代其位置，即让双亲节点指向该节点的子树；3.待删除节点有两棵子树（左和右均非空）：采用“前驱替代”或“后继替代”策略：①前驱替代：找到待删除节点左子树中的最大值节点（前驱），用前驱节点值替换待删除节点值，再删除前驱节点（前驱节点必为叶子节点或仅有左子树，按前两种情况处理）；②后继替代：找到待删除节点右子树中的最小值节点（后继），用后继节点值替换待删除节点值，再删除后继节点。关键要点：删除后需保证二叉排序树特性不变；有两棵子树时的替代策略是核心，需理解前驱和后继的定义。练习题及答案解析题1：已知二叉排序树结构为：根5，左孩子3（左2、右4），右孩子7（左6、右8）。若删除节点3，删除后树的结构如何？答案：删除后，节点4替代节点3的位置，成为5的左孩子；节点2仍为4的左孩子。树结构：根5，左孩子4（左2），右孩子7（左6、右8）。解析：待删除节点3有一棵右子树（节点4），属于“仅有一棵子树”的情况。按规则，用其右子树（节点4）替代节点3的位置，即双亲节点5的左指针从指向3改为指向4，节点4的左指针保持指向2，右指针为空，删除后仍满足二叉排序树特性（2＜4＜5＜6＜7＜8）。题2：承接题1的原始二叉排序树，若删除根节点5，采用“后继替代”策略，删除后根节点的值是什么？被删除的后继节点是哪个？答案：删除后根节点值为6；被删除的后继节点是6。解析：待删除节点5有两棵子树，采用“后继替代”：①找后继节点：待删除节点右子树（根7）中的最小值节点，即6；②用6替换5的节点值，此时根节点值变为6；③删除后继节点6（6为叶子节点，直接删除，将其双亲节点7的左指针置空）。删除后树结构：根6，左孩子3（左2、右4），右孩子7（右8），满足二叉排序树特性。题3：下列关于二叉排序树节点删除的说法，正确的是（）A.删除有两棵子树的节点时，只能用前驱节点替代B.删除叶子节点时，只需直接删除，无需修改双亲节点指针C.删除仅有左子树的节点时，用其左子树替代该节点位置D.删除后二叉排序树的特性一定会被破坏答案：C解析：A选项错误，有两棵子树时可采用前驱或后继替代，两种策略均可；B选项错误，删除叶子节点后，需将其双亲节点对应的左/右指针置空，否则会出现悬空指针；C选项正确，仅有一棵子树（左或右）时，直接用该子树替代节点位置，保持特性；D选项错误，删除操作的核心就是保证删除后仍满足二叉排序树特性，只要遵循规则就不会破坏。知识点4：二叉树的深度与高度计算（基础）课程中对二叉树深度和高度的定义（统一口径）：①深度：从根节点到该节点的路径上的节点数（根节点深度为1）；②高度：从该节点到最远叶子节点的路径上的节点数（叶子节点高度为1）；③二叉树的深度=根节点的高度。计算方法（递归）：1.若二叉树为空，深度/高度为0；2.若二叉树非空，二叉树的高度=1+max(左子树高度,右子树高度)（1为当前节点本身）。关键要点：递归思想的应用；区分节点的深度和高度，避免混淆；空树的深度和高度均为0。练习题及答案解析题1：已知二叉树结构：根A，左孩子B（左孩子D、右孩子E），右孩子C（右孩子F）。请计算该二叉树的深度（即根节点A的高度），以及节点E的深度和高度。答案：二叉树深度为3；节点E的深度为3，高度为1。解析：①二叉树深度（A的高度）：左子树B的高度=1+max(D的高度,E的高度)=1+max(1,1)=2；右子树C的高度=1+max(0,F的高度)=1+1=2；因此A的高度=1+max(2,2)=3，即二叉树深度为3。②节点E的深度：从根A到E的路径为A→B→E，共3个节点，深度为3。③节点E的高度：E是叶子节点，高度为1。题2：计算空树、单节点二叉树、单支左子树（根A→B→C→D，均为左孩子）的深度和高度。答案：①空树：深度0，高度0；②单节点二叉树：深度1，高度1；③单支左子树：深度4，高度4。解析：①空树无节点，深度和高度均为0；②单节点二叉树，根节点深度为1，高度为1（自身为叶子节点）；③单支左子树（A→B→C→D）：根A的深度为1，B为2，C为3，D为4；高度计算：D高度1，C高度=1+1=2，B高度=1+2=3，A高度=1+3=4，因此二叉树深度和高度均为4。题3：若一棵二叉树的左子树高度为3，右子树高度为4，则该二叉树的高度为（）A.3B.4