高中信息技术（必选1）X1-09二叉树知识点

高中信息技术（必选1）X1-09二叉树知识点整理本课程属于高中信息技术必选1模块，聚焦二叉树这一重要的数据结构。通过学习，需理解二叉树的基本概念、结构特征，掌握二叉树的遍历方法、性质及简单应用，为后续复杂数据结构的学习奠定基础。以下是本课程核心知识点梳理，每个知识点配套练习题、答案及解析。一、核心知识点梳理知识点1：二叉树的基本概念与结构特征1.定义：二叉树是一种非线性数据结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点，且子节点有左右顺序之分（左、右子树不能随意交换）。2.基本术语：节点：二叉树中的基本元素，包含数据项和指向子节点的引用（指针）；根节点：二叉树的起始节点，没有父节点；叶子节点：没有子节点的节点（左、右子节点均为空）；父节点/子节点：若节点A有子节点B，则A是B的父节点，B是A的子节点；树的深度（高度）：从根节点到最远叶子节点的最长路径上的节点数；节点的度：节点拥有的子节点个数（二叉树中节点的度只能是0、1或2）。3.特殊二叉树：满二叉树：除叶子节点外，每个节点都有两个子节点，且所有叶子节点都在同一层；完全二叉树：除最后一层外，每一层的节点数都达到最大值，且最后一层的节点都集中在左侧，连续存在，右侧可以缺少若干节点（满二叉树是特殊的完全二叉树）。练习题1-1题目：下列关于二叉树的说法，正确的是（）A.二叉树中每个节点最多有两个子节点，因此二叉树的节点度只能是2B.左、右子树顺序无关的树就是二叉树C.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树D.叶子节点是度为1的节点答案：C解析：选项A错误，二叉树节点的度可以是0（叶子节点）、1（只有一个子节点）或2（有两个子节点）；选项B错误，二叉树的左、右子树有顺序之分，交换左、右子树后得到的是不同的二叉树；选项C正确，满二叉树满足完全二叉树的所有条件，是特殊的完全二叉树，而完全二叉树最后一层可能缺少右侧节点，不一定是满二叉树；选项D错误，叶子节点是度为0的节点。练习题1-2题目：某二叉树的根节点度为2，有3个叶子节点，请问该二叉树中节点总数最少为（）A.4B.5C.6D.7答案：B解析：要使节点总数最少，需让非叶子节点尽可能多的拥有两个子节点。根节点度为2，设根节点为A，其左子节点B、右子节点C。若B为非叶子节点，度为2，其左、右子节点D、E（均为叶子节点），C为叶子节点，此时叶子节点为D、E、C（共3个），节点总数为A、B、C、D、E，共5个。若根节点的两个子节点中有一个度为1，另一个度为2，节点总数会更多，因此最少为5个。练习题1-3题目：判断“深度为3的满二叉树，节点总数为7”这一说法是否正确，并说明理由。答案：正确解析：满二叉树的每一层节点数都达到最大值，第k层的节点数为2^(k-1)（k≥1）。深度为3的满二叉树，第1层（根节点）有2^(1-1)=1个节点，第2层有2^(2-1)=2个节点，第3层有2^(3-1)=4个节点，总节点数=1+2+4=7个，因此说法正确。知识点2：二叉树的性质1.性质1：在二叉树的第i层上，最多有2^(i-1)个节点（i≥1，i为层数）。例如第1层最多1个节点，第2层最多2个节点，第3层最多4个节点。2.性质2：深度为k的二叉树，最多有2^k-1个节点（k≥1）。该性质由性质1推导而来，总节点数为各层最多节点数之和，即1+2+4+...+2^(k-1)=2^k-1（等比数列求和）。3.性质3：对于任意一棵二叉树，若度为0的节点（叶子节点）数为n₀，度为2的节点数为n₂，则n₀=n₂+1。推导：设二叉树总节点数为N，度为1的节点数为n₁，则N=n₀+n₁+n₂；二叉树中除根节点外，每个节点都有一个父节点，因此边数为N-1，而边数也等于n₁×1+n₂×2（度为1的节点贡献1条边，度为2的节点贡献2条边），即N-1=n₁+2n₂；联立两式可得n₀=n₂+1。4.性质4：深度为k的完全二叉树，节点总数N满足2^(k-1)≤N≤2^k-1；若N为完全二叉树的节点总数，其深度k=⌊log₂N⌋+1（⌊log₂N⌋表示不大于log₂N的最大整数）。5.性质5：对于有N个节点的完全二叉树，若节点编号从根节点开始，按层序（从上到下、从左到右）编号为1~N，则对任意编号为i的节点（1≤i≤N）：若i=1，则该节点为根节点，无父节点；若i>1，则其父节点编号为⌊i/2⌋；若2i≤N，则其左子节点编号为2i；若2i>N，则该节点无左子节点；若2i+1≤N，则其右子节点编号为2i+1；若2i+1>N，则该节点无右子节点。练习题2-1题目：某二叉树中，度为0的节点数为8，度为1的节点数为2，则该二叉树中度为2的节点数为（）A.6B.7C.8D.9答案：B解析：根据二叉树性质3，度为0的节点数n₀=度为2的节点数n₂+1，即n₂=n₀-1。已知n₀=8，因此n₂=8-1=7，与度为1的节点数无关，答案选B。练习题2-2题目：深度为5的完全二叉树，节点总数最少为（），最多为（）A.16，31B.15，31C.16，32D.15，32答案：A解析：根据二叉树性质2和性质4，深度为k的完全二叉树，节点总数N满足2^(k-1)≤N≤2^k-1。当k=5时，最少节点数为2^(5-1)=16，最多节点数为2^5-1=31，答案选A。练习题2-3题目：有一棵有12个节点的完全二叉树，按层序编号为1~12，请问编号为5的节点的左、右子节点编号分别是（）A.10，11B.10，无C.9，10D.无，无答案：A解析：根据完全二叉树性质5，编号为i的节点，左子节点编号为2i，右子节点编号为2i+1。编号i=5，左子节点编号=2×5=10，右子节点编号=2×5+1=11。由于总节点数为12，10≤12、11≤12，因此该节点既有左子节点（编号10），也有右子节点（编号11），答案选A。练习题2-4题目：某完全二叉树的节点总数为18，求该二叉树的深度及度为0的节点数。答案：深度为5，度为0的节点数为9解析：①求深度：根据性质4，深度k=⌊log₂N⌋+1，N=18。log₂16=4，log₂32=5，因此⌊log₂18⌋=4，深度k=4+1=5。②求度为0的节点数：深度为5的完全二叉树，前4层为满二叉树，节点数=2^4-1=15，因此第5层有18-15=3个节点（均为叶子节点）。第4层的节点数为2^(4-1)=8个，编号为1~8，其中第5层节点的父节点编号为⌊3/2⌋=1、⌊4/2⌋=2（若有第4个节点则父节点为2，此处只有3个），即第4层中编号1、2的节点为度为2的节点，编号3~8的节点为度为0的节点（共6个）。因此总叶子节点数=第4层叶子节点数+第5层叶子节点数=6+3=9个。也可利用性质3推导：设n₀为叶子节点数，n₂为度为2的节点数，n₁为度为1的节点数，N=18=n₀+n₁+n₂，且n₀=n₂+1。完全二叉树中n₁只能是0或1，若n₁=1，则18=n₀+1+n₂=（n₂+1）+1+n₂=2n₂+2，解得n₂=8，n₀=9；若n₁=0，则18=2n₂+1，解得n₂=8.5（不符合实际），因此n₁=1，n₀=9。知识点3：二叉树的遍历二叉树的遍历是指按照一定的规则，依次访问二叉树中的所有节点，且每个节点仅访问一次。常用的遍历方式有前序遍历、中序遍历、后序遍历（均属于深度优先遍历）和层序遍历（广度优先遍历）。1.前序遍历（根-左-右）：先访问根节点，再递归遍历左子树，最后递归遍历右子树。核心规则：“根”在最前，左、右子树依次跟进。2.中序遍历（左-根-右）：先递归遍历左子树，再访问根节点，最后递归遍历右子树。核心规则：“根”在中间，左子树遍历完再访问根，最后遍历右子树。3.后序遍历（左-右-根）：先递归遍历左子树，再递归遍历右子树，最后访问根节点。核心规则：“根”在最后，左、右子树均遍历完再访问根。4.层序遍历（从上到下、从左到右）：按照二叉树的层次，从上到下、同一层从左到右依次访问每个节点。核心规则：按“层”访问，不依赖递归，常借助队列实现。关键技巧：已知前序遍历和中序遍历结果，可唯一确定一棵二叉树；已知中序遍历和后序遍历结果，可唯一确定一棵二叉树；已知前序遍历和后序遍历结果，无法唯一确定一棵二叉树（无法区分左、右子树）。练习题3-1题目：某二叉树的前序遍历序列为ABDFCEG，中序遍历序列为DFBACEG，则该二叉树的后序遍历序列为（）A.DFBGECAB.DFBGCEAC.DFBCGEAD.DFBAGCE答案：A解析：①由前序遍历“根-左-右”可知，根节点为A（前序序列第一个节点）；②由中序遍历“左-根-右”可知，中序序列中A左侧的DFB为左子树节点，右侧的CEG为右子树节点；③分析左子树：前序序列中A之后的DFB为左子树前序遍历结果，因此左子树根节点为B（前序序列左子树部分第一个节点）；中序序列中B左侧的DF为B的左子树节点，右侧无节点（B在DF之后、A之前），即B的右子树为空；④分析B的左子树：前序序列中B之后的DF为其前序遍历结果，根节点为D；中序序列中D左侧无节点，右侧为F，因此D的右子树为F，左子树为空；⑤分析右子树：前序序列中左子树之后的CEG为右子树前序遍历结果，根节点为C；中序序列中C左侧无节点，右侧为EG，因此C的左子树为空，右子树为EG；⑥分析C的右子树：前序序列中C之后的EG为其前序遍历结果，根节点为E；中序序列中E左侧无节点，右侧为G，因此E的右子树为G，左子树为空；⑦构建二叉树后，按后序遍历“左-右-根”可得序列：DFBGECA，即DFBGECA，答案选A。练习题3-2题目：已知某二叉树的中序遍历序列为ABCDE，后序遍历序列为EDCBA，则该二叉树的前序遍历序列为（）A.ABCDEB.ACBDEC.EDCBAD.BAEDC答案：A解析：①由后序遍历“左-右-根”可知，根节点为A（后序序列最后一个节点）；②由中序遍历“左-根-右”可知，中序序列中A右侧的BCDE为右子树节点，左侧无节点（A在中序序列第一个位置），即左子树为空；③分析右子树：后序序列中A之前的EDCB为右子树后序遍历结果，因此右子树根节点为B（后序序列右子树部分最后一个节点）；中序序列中B右侧的CDE为B的右子树节点，左侧无节点；④依次类推，右子树每个节点均只有右子节点，构建的二叉树为“右斜树”：A→B→C→D→E；⑤前序遍历“根-左-右”（左子树为空，仅访问根和右子树）可得序列ABCDE，答案选A。练习题3-3题目：画出前序遍历序列为ABC，中序遍历序列为BAC的二叉树，并写出其层序遍历序列。答案：二叉树结构为：根节点A，左子节点B，右子节点C；层序遍历序列为ABC解析：①前序序列第一个节点A为根节点；②中序序列中A左侧的B为左子树节点，右侧的C为右子树节点；③前序序列中A之后的B为左子树前序节点，因此左子树根节点为B（无后代）；前序序列中B之后的C为右子树前序节点，因此右子树根节点为C（无后代）；④二叉树结构：A是根，左孩子B，右孩子C；⑤层序遍历按“从上到下、从左到右”访问，序列为ABC。练习题3-4题目：下列关于二叉树遍历的说法，错误的是（）A.前序遍历和中序遍历可以唯一确定一棵二叉树B.中序遍历和后序遍历可以唯一确定一棵二叉树C.前序遍历和后序遍历可以唯一确定一棵二叉树D.层序遍历和中序遍历可以唯一确定一棵二叉树答案：C解析：选项A、B正确，这是二叉树遍历的核心结论，通过“根节点位置+中序左/右子树划分”可唯一构建二叉树；选项C错误，前序遍历（根-左-右）和后序遍历（左-右-根）仅能确定根节点，无法区分左、右子树（例如：根节点A，左子节点B和根节点A，右子节点B的前序序列均为AB，后序序列均为BA，无法区分）；选项D正确，层序遍历可确定根节点及各层节点，结合中序遍历可划分左、右子树，进而唯一确定二叉树，答案选C。知识点4：二叉树的简单应用1.二叉排序树（二叉搜索树）：一种特殊的二叉树，左子树中所有节点的值均小于根节点的值，右子树中所有节点的值均大于根节点的值，且左、右子树也分别是二叉排序树。核心作用：快速查找、插入和删除数据（平均时间复杂度为O(log₂n)）。2.哈夫曼树（最优二叉树）：给定n个权值作为n个叶子节点，构造一棵二叉树，使得该树的带权路径长度（WPL）最小。带权路径长度是指所有叶子节点的权值乘以其到根节点的路径长度之和。核心应用：哈夫曼编码，用于数据压缩（频率高的字符编码短，频率低的字符编码长，减少总编码长度）。练习题4-1题目：将序列5,3,7,2,4,6,8依次插入到空的二叉排序树中，插入完成后，该二叉树的中序遍历序列为（）A.2,3,4,5,6,7,8B.5,3,2,4,7,6,8C.8,7,6,5,4,3,2D.5,7,8,6,3,4,2答案：A解析：二叉排序树的中序遍历序列一定是升序序列，这是二叉排序树的核心特征。无论插入顺序如何，中序遍历都会得到有序序列。题目中序列的升序排列为2,3,4,5,6,7,8，因此答案选A。也可逐步构建二叉树验证：①插入5（根）；②插入3（5的左子节点）；③插入7（5的右子节点）；④插入2（3的左子节点）；⑤插入4（3的右子节点）；⑥插入6（7的左子节点）；⑦插入8（7的右子节点）；中序遍历“左-根-右”可得序列2,3,4,5,6,7,8。练习题4-2题目：已知某