第09讲 树的操作（复习讲义）（浙江专用）2027年高考信息技术一轮复习讲练测

第09讲 树的操作 内容导航 01 命题透视·考情前瞻 对标素养，研判高考命题趋势 02 思维建模·脉络梳理 搭建知识框架，构建系统思维 03 考点精讲·靶向突破 拆解核心考点，归纳解题范式 考点一 树的概念和性质 知识解构 知识点 树的基本概念、结点、度、层次、深度等术语 考向破译 考向 根据树的相关术语，计算结点数、结点的度、树的深度 考点二 二叉树 知识解构 知识点1 二叉树的概念、性质、满二叉树、完全二叉树 知识点2 二叉树的建立 知识点3 二叉树的遍历 考向破译 考向1 利用二叉树性质计算结点数量；完全二叉树父子结点编号换算 考向2 根据遍历序列还原二叉树，推导未知遍历序列 考点三 二叉排序树 知识解构 知识点 二叉排序树 考向破译 考向 二叉排序树排序 04 真题溯源·考向感知 溯源真题逻辑，感知高考考向 命题透视·考情前瞻 ——对标素养，研判高考命题趋势 考点要求 考查形式 2026年 2025年 2024年 树与二叉树基本概念、性质与遍历推演 选择题 非选择题 浙江卷1月卷 T9，2 分；浙江卷6月卷 T9，2 分 浙江卷 1 月卷 T9，2 分；浙江卷 6 月卷 T8，2 分 浙江卷 6月卷 T8，2 分 二叉排序树相关综合分析 选择题 非选择题 无 无 浙江卷 6月卷 T15，9 分 考情分析 1. 浙江选考对树、二叉树的考查，重在树形推演、遍历序列转换、完全二叉树性质计算。选择题高频考查二叉树三种遍历互推、结点增减后遍历结果判断、完全二叉树结点位置计算；综合题（非选择题）仅在部分试卷借助 Python 代码考查二叉排序树的构造、查找逻辑，侧重结点插入顺序、查找路径分析。 2. 从命题思路上看： （1）二叉树命题思路：聚焦前序、中序、后序遍历，给定树形或者限定修改条件，判断遍历结果；完全二叉树侧重结点在不同遍历序列中的位置计算。命题不单纯考查概念，常给出树形图，手动模拟遍历过程判断结果。 选择题特点：给定二叉树，修改结点后判断遍历序列；给定完全二叉树，计算根结点在不同遍历序列中的位置差值； 易错点：区分左右子树、遍历顺序；新增结点后对遍历序列的影响；根结点、叶子结点在遍历序列中的位置判断。 （2）二叉排序树命题思路：重点掌握二叉排序树的插入规则、查找路径，根据输入序列推演二叉排序树生成过程，分析查找成功的比较次数。 复习目标 1.理解树、二叉树、二叉排序树的逻辑结构特点，掌握树的相关术语、二叉树的性质； 2.熟练掌握二叉树前序、中序、后序三种遍历规则，掌握二叉排序树的插入、查找逻辑与 Python 代码实现； 3.能根据遍历序列还原二叉树，根据树形推演遍历结果，结合代码手动模拟二叉排序树插入、查找过程，推导结点比较次数、补全算法代码。 思维建模·脉络梳理 ——搭建知识框架，构建系统思维 考点精讲·靶向突破 ——拆解核心考点，归纳解题范式 考点一 树的概念和性质 知●识●解●构 知识点1 树的基本概念、结点、度、层次、深度等术语 1.基本概念 树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系（非线性结构）。当N=0时，称为空树。 树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点： （1）树的根节点没有前驱节点，除根节点以外的所有节点有且只有一个前驱节点。 （2）树中可以有零个或多个后继节点。 节点：集合中的元素。 空树：n = 0 的树。 子树：树中某个节点下面的所有节点所构成的树。 根节点：没有前驱的节点。 叶子节点：度为 0 的节点。 父节点或双亲节点：上端节点称为下端节点的父节点。 孩子节点：下端节点称为上端节点的孩子节点。 边：一颗具有 n 个节点的树有 n-1 条边。 节点的度：树的一个节点所拥有的子树个数。 树的度：最大的节点的度。 树的高度或深度：树中节点的最大层数。根的层数为1。 2.树的性质： 性质1.总分支数=1*N1+2*N2+.....+m*Nm（度为m的节点引出的m条分支） 性质2.总节点数=N0+N1+N2+......+Nm 性质3.树中的节点数等于所有节点度数+1 性质4.度为m的树中第i层上至多有mi-1个节点（i≥1） 考●向●破●译 考向 根据树的相关术语，计算结点数、结点的度、树的深度 1．树结构中，结点的度是指（   ） A．结点拥有的子树数目 B．结点所在的层次 C．树的深度 D．结点的值 2．有如图所示的树。下列说法正确的是（   ） A．该树中共有3个叶子节点 B．该树的度和深度均为3 C．该树中度为2的子节点有1个，度为1的子节点有2个 D．节点e是节点f的兄弟节点 3．一棵完全三叉树有3层，若最后一层有4个叶子节点，则该三叉树的总节点数为（   ） A．8 B．11 C．12 D．13 4．对于一棵满二叉树，第i层的节点数是第i-1层节点数的（   ）倍。 A．1 B．2 C．3 D．4 考点二 二叉树 知●识●解●构 知识点1 二叉树的概念、性质、满二叉树、完全二叉树 1.二叉树基本概念 二叉树是一个具有n（n≥0）个节点的一个有限集合，且各个节点的度小于或等于2，二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。 二叉树的特点： （1）当n=0时，为空二叉树 （2）当n>=1时，二叉树由一个根节点和两个互不相交的被称为左子树和右子树组成，左子树和右子树又分别是一棵二叉树。 2.基本形态 3.满二叉树 一棵高度为h，含有2h-1个节点的二叉树称为满二叉树，即树中的每一层都含有最多的节点。满二叉树的叶子节点都集中在二叉树的最下一层，除叶子节点以外每个节点的度数都为2。 4.完全二叉树 设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。 注意 四个判断： （1）满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 （2）空二叉树和只有根结点的二叉树，既是满二叉树，也是完全二叉树。 （3）完全二叉树可看作在满二叉树的最下一层，从右向左连续删除若干个结点后得到；这里“连续”是关键，中间不能留空。 （4）完全二叉树中，一个结点如果没有左孩子，就一定没有右孩子；否则最后一层会出现空位，违反“从左向右连续填充”。 5.二叉树的性质 性质 1 第 k 层上至多有 2^(k−1)​ 个结点（k ≥ 1）。 性质 2 深度为 k 的二叉树至多有 2^k − 1 个结点（k ≥ 1）。 性质 3 任何一棵二叉树，若叶子结点数为 n₀、度为 2 的结点数为 n₂，则 n₀ = n₂ + 1。 证明：结点总数 n = n₀ + n₁ + n₂；除根外每个结点恰有一条入边，故边数 = n − 1；而边数又等于各结点出度之和 = n₁ + 2n₂。 于是 n₁ + 2n₂ = n − 1 = n₀ + n₁ + n₂ − 1，得 n₀ = n₂ + 1。 性质 4 具有 n 个结点的完全二叉树的深度为 ⌊log₂n⌋ + 1（等价于 ⌈log₂(n+1)⌉）。 性质 5 含 n 个结点的完全二叉树按层序编号：自第 1 层起，每层从左到右，根结点编号为 1。对任一结点 i（1 ≤ i ≤ n）： 若 i = 1，则该结点是根，没有父结点；若 i > 1，则其父结点为 ⌊i/2⌋。 若 2i > n，则 i 没有左孩子；否则左孩子为 2i。 若 2i + 1 > n，则 i 没有右孩子；否则右孩子为 2i + 1。 注：性质 5 的公式以“编号从 1 开始”为前提；如果数组下标从 0 开始，父结点为 ⌊(i−1)/2⌋，左孩子为 2i+1，右孩子为 2i+2。 知识点2 二叉树的建立 1.数组实现 完全二叉树：从根开始按“自上而下、自左向右”编号，根编号为 0，其余编号 1…n−1，编号即数组下标，依次存入一维数组，不浪费空间。 非完全二叉树：先补全为完全二叉树，补上的结点用虚线或特殊值（如 #）表示；再按同一规则编号存数组。空结点也占位，单支树最坏需 2^n − 1 个存储单元。 2.链表实现 每个结点含三个域：lchild | data | rchild，分别存放左孩子指针、数据元素、右孩子指针；空指针用 NULL（或 ^）表示需要快速查找父结点时，可增设 parent 域构成三叉链表。 3.嵌套列表实现 表示规则： 用三层列表表示一个结点：[根结点, 左子树, 右子树] 根结点存放数据（值）。 左、右子树仍是同样结构的嵌套列表（递归定义）。 空树用空列表 [] 表示。 例： t = ['a', ['b', ['d'], ['e']], ['c', [], ['f']]] 对应：a 为根；左孩子 b（b 的孩子 d、e）；右孩子 c（右孩子 f）。 知识点3 二叉树的遍历 前序遍历（DLR） 首先访问根结点，其次遍历左子树，最后遍历右子树。 遍历序列：ABDHECFG 中序遍历（LDR） 首先访问左子树，其次遍历根结点，最后遍历右子树。 遍历序列：HDBEAFCG 后序遍历（LRD） 首先访问左子树，其次遍历右子树，最后遍历根结点。 遍历序列：HDEBFGCA 拓展链接 哈夫曼树（最优二叉树）特点： 1.定义与本质 哈夫曼树： 给定 n 个权值作为 n 个叶子结点，构造出的带权路径长度 WPL = Σwᵢ·lᵢ 最小的二叉树（lᵢ 为叶子到根的路径长度，即边数），又称最优二叉树。 构造方法（贪心）​： 每次从集合中取出两个权值最小的结点合并，新结点的权值为二者之和，再放回集合；重复 n₀−1 次，直到只剩一个结点。 2.四个特点 1.只有度为 0 和度为 2 的结点，没有度为 1 的结点，因此哈夫曼树是严格二叉树（正则二叉树）。 2.结点数关系：n = n₀ + n₂，由 n₀ = n₂ + 1 得 n = 2n₀ − 1 = 2n₂ + 1。其中 n₀ 为叶子数（待编码的字符数），构造时共合并 n₀ − 1 次。 3.权值较大的叶子结点离根较近，编码较短；准确地说，是权值越大，编码长度一定不会更长（权值相等时深度可能相同），不可理解为严格一一单调。 4.绘制与编码约定：合并时小数在左、大数在右；左分支记 0，右分支记 1。此约定不是强制的，左右可互换、0/1 可互换，但同一棵树内必须统一，故哈夫曼编码不唯一（码长与 WPL 最优性唯一）。 考●向●破●译 考向1 利用二叉树性质计算结点数量；完全二叉树父子结点编号换算 例1【2024 年 8 月浙江 A9 协作体高三返校联考】 一个具有 1025 个结点的二叉树，其高度最小为（）。 A.10 B.11 C.12 D. 不确定 【变式1】【2025 学年台州高二期末统考】 一棵完全二叉树共有 701 个结点，则该二叉树中的叶子结点数为（）。 A.350 B.351 C.352 D.353 【变式2】【2025天域全国名校协作体 10 月联考】 已知一棵完全二叉树按 1 起始层序编号，结点编号为 20，则它的左孩子编号是（），右孩子编号是（）。 A.40，41 B.41，42 C.10，11 D.10，无 考向2 根据遍历序列还原二叉树，推导未知遍历序列 例1【2024 学年第二学期期中杭州地区 】 二叉树某二叉树前序遍历是 ABDCEF, 中序遍历是 DBAECF, 关于此二叉树下列说法正确的是 二叉树A. 二叉树有 2 个叶子节点 二叉树B. 该树是完全二叉树 二叉树C. 度为 2 和度为 1 的节点个数相同 二叉树D. 要成为一个满二叉树，至少需要增加 1 个节点 【变式1】【2026·浙江·一模】 若某二叉树的前序遍历结果为ABDECF，后序遍历结果为DEBFCA，则该二叉树的中序遍历结果可能为（   ） A．DBAFEC B．DBEACF C．DEBACF D．BDEAFC 【变式2】【2026·浙江·一模】 某二叉树的前序遍历序列为C-F-A-？-？-E，中序遍历序列为F-D-A-C-E-B，则以下说法正确的是（   ） A．该二叉树的深度为3 B．节点A和节点E为兄弟节点 C．将该二叉树变为完全二叉树至少需要增加3个节点 D．该二叉树的后序遍历序列是DAFEBC 【变式3】 某二叉树的数组表示如图所示，下列说法正确的是（   ） 0 1 2 3 4 5 6 7 8 9 10 A B C D E F A．该二叉树是一棵完全二叉树，其高度是4 B．二叉树中度为2的节点数比叶子节点数多1 C．该二叉树的前序遍历结果为ABDEFC，中序遍历结果为BDAECF D．可用列表["A",["B",None,["D",["E",None,None],["F",None,None]]],["C",None,None]]表示该二叉树 考点三 二叉排序树 知识点 二叉排序树 1.概念 若左子树不空 → 左子树所有结点值 < 根值 若右子树不空 → 右子树所有结点值 > 根值 左右子树本身也各是一棵 BST（递归定义） 关键词：有序约束；通常无重复关键字 2.常见操作 查找：从根比大小，小往左、大往右，命中或遇空结束。 插入：同样沿大小路径走到空位放入；新结点一定是叶子。 删除：叶子直接删 / 单孩子用孩子顶替 / 双孩子用**前驱(左子树最大)或后继(右子树最小)**替换。 3.特点 中序遍历结果必为升序序列（最重要性质）。 查找效率取决于树形形态：均衡时 O(log n)，退化成"斜树"时 O(n)（与插入顺序有关）。 二叉树 VS 二叉排序树（高频对比） 考●向●破●译 考向 二叉排序树排序 例1依次插入关键字 45, 24, 67, 12, 53, 90, 38 构成二叉排序树，则结点 38 的父结点是（）。 A. 45　 B. 24　 C. 12 　D. 67 【变式】给定二叉排序树如图所示，查找关键字 40 成功时，共需比较（）次。 A. 1 B. 2　 C. 3　 D. 4 真题溯源·考向感知 1.【26.01浙江选考卷】某二叉树有 a、b、c、d四个节点，若中序遍历序列为 abcd,后序遍历序列为 dcba,则该二叉树的树形结构为 2.【25.01浙江选考卷】某二叉树如第9题图所示，若其中的一个叶子节点增加右子树(仅包含节点N),则新二叉树的中序遍历结果不可能是 A.CNBDAE B.CBDNAE C.CBDAEN D.NCBDAE 3.【24.06浙江选考卷】某完全二叉树包含5个节点,其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为xy，则 x-y的值为 A.0 B.1 C2 D.3 4.【25.06浙江选考卷】某二叉树如第8题图所示，E节点在前序遍历序列中的位置记号为x。下列二叉树中E节点在中序遍历序列中的位置序号也为x的是 5.【26.06浙江选考卷】某完全二叉树的中序遍历序列为STURV，则其根节点为 A.T B U C.R D.V 2 / 3 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $ 第09讲 树的操作 内容导航 01 命题透视·考情前瞻 对标素养，研判高考命题趋势 02 思维建模·脉络梳理 搭建知识框架，构建系统思维 03 考点精讲·靶向突破 拆解核心考点，归纳解题范式 考点一 树的概念和性质 知识解构 知识点 树的基本概念、结点、度、层次、深度等术语 考向破译 考向 根据树的相关术语，计算结点数、结点的度、树的深度 考点二 二叉树 知识解构 知识点1 二叉树的概念、性质、满二叉树、完全二叉树 知识点2 二叉树的建立 知识点3 二叉树的遍历 考向破译 考向1 利用二叉树性质计算结点数量；完全二叉树父子结点编号换算 考向2 根据遍历序列还原二叉树，推导未知遍历序列 考点三 二叉排序树 知识解构 知识点 二叉排序树 考向破译 考向 二叉排序树排序 04 真题溯源·考向感知 溯源真题逻辑，感知高考考向 命题透视·考情前瞻 ——对标素养，研判高考命题趋势 考点要求 考查形式 2026年 2025年 2024年 树与二叉树基本概念、性质与遍历推演 选择题 非选择题 浙江卷1月卷 T9，2 分；浙江卷6月卷 T9，2 分 浙江卷 1 月卷 T9，2 分；浙江卷 6 月卷 T8，2 分 浙江卷 6月卷 T8，2 分 二叉排序树相关综合分析 选择题 非选择题 无 无 浙江卷 6月卷 T15，9 分 考情分析 1. 浙江选考对树、二叉树的考查，重在树形推演、遍历序列转换、完全二叉树性质计算。选择题高频考查二叉树三种遍历互推、结点增减后遍历结果判断、完全二叉树结点位置计算；综合题（非选择题）仅在部分试卷借助 Python 代码考查二叉排序树的构造、查找逻辑，侧重结点插入顺序、查找路径分析。 2. 从命题思路上看： （1）二叉树命题思路：聚焦前序、中序、后序遍历，给定树形或者限定修改条件，判断遍历结果；完全二叉树侧重结点在不同遍历序列中的位置计算。命题不单纯考查概念，常给出树形图，手动模拟遍历过程判断结果。 选择题特点：给定二叉树，修改结点后判断遍历序列；给定完全二叉树，计算根结点在不同遍历序列中的位置差值； 易错点：区分左右子树、遍历顺序；新增结点后对遍历序列的影响；根结点、叶子结点在遍历序列中的位置判断。 （2）二叉排序树命题思路：重点掌握二叉排序树的插入规则、查找路径，根据输入序列推演二叉排序树生成过程，分析查找成功的比较次数。 复习目标 1.理解树、二叉树、二叉排序树的逻辑结构特点，掌握树的相关术语、二叉树的性质； 2.熟练掌握二叉树前序、中序、后序三种遍历规则，掌握二叉排序树的插入、查找逻辑与 Python 代码实现； 3.能根据遍历序列还原二叉树，根据树形推演遍历结果，结合代码手动模拟二叉排序树插入、查找过程，推导结点比较次数、补全算法代码。 思维建模·脉络梳理 ——搭建知识框架，构建系统思维 考点精讲·靶向突破 ——拆解核心考点，归纳解题范式 考点一 树的概念和性质 知●识●解●构 知识点1 树的基本概念、结点、度、层次、深度等术语 1.基本概念 树（Tree）可以描述为由n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系（非线性结构）。当N=0时，称为空树。 树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点： （1）树的根节点没有前驱节点，除根节点以外的所有节点有且只有一个前驱节点。 （2）树中可以有零个或多个后继节点。 节点：集合中的元素。 空树：n = 0 的树。 子树：树中某个节点下面的所有节点所构成的树。 根节点：没有前驱的节点。 叶子节点：度为 0 的节点。 父节点或双亲节点：上端节点称为下端节点的父节点。 孩子节点：下端节点称为上端节点的孩子节点。 边：一颗具有 n 个节点的树有 n-1 条边。 节点的度：树的一个节点所拥有的子树个数。 树的度：最大的节点的度。 树的高度或深度：树中节点的最大层数。根的层数为1。 2.树的性质： 性质1.总分支数=1*N1+2*N2+.....+m*Nm（度为m的节点引出的m条分支） 性质2.总节点数=N0+N1+N2+......+Nm 性质3.树中的节点数等于所有节点度数+1 性质4.度为m的树中第i层上至多有mi-1个节点（i≥1） 考●向●破●译 考向 根据树的相关术语，计算结点数、结点的度、树的深度 1．树结构中，结点的度是指（   ） A．结点拥有的子树数目 B．结点所在的层次 C．树的深度 D．结点的值 【答案】A 【详解】本题考查树结构的基本概念。在树的基础定义中，结点的度被明确规定为该结点拥有的子树数目；结点所在的层次描述结点所处的层级，树的深度是树中结点的最大层次，结点的值是结点存储的数据，这三个选项都不符合结点度的定义。故答案为：A。 2．有如图所示的树。下列说法正确的是（   ） A．该树中共有3个叶子节点 B．该树的度和深度均为3 C．该树中度为2的子节点有1个，度为1的子节点有2个 D．节点e是节点f的兄弟节点 【答案】C 【详解】本题考查树。该树中共有4个叶子节点，分别是h、e、f、g，因此A选项错误；该树的度为3，深度为4，因此B选项错误；由于节点e和节点f的父节点不是同一个，因此它们不是兄弟节点，因此D选项错误；该树中度为2的子节点有1个(b节点)，度为1的子节点有2个(d节点和c节点)，C选项正确。故答案为：C。 3．一棵完全三叉树有3层，若最后一层有4个叶子节点，则该三叉树的总节点数为（   ） A．8 B．11 C．12 D．13 【答案】A 【详解】本题考查树的结构与性质。该问题涉及一棵完全三叉树的节点计算。完全三叉树的定义是：除了最后一层外，其他层都是满的（即每个节点都有恰好三个子节点），且最后一层的节点从左到右连续填充。第1层（根层）：1个节点（必有一个节点）。第2层：由于是完全树且树有3层，第2层必须是满的，因此有3个节点（每个第1层节点最多有三个子节点，根节点必须有三个子节点以保持除最后一层外全满）。第3层（最后一层）：题目给定有4个叶子节点。在树结构中，最后一层的节点都是叶子节点（无子节点），因此最后一层有4个节点。总节点数 = 1 + 3 + 4 = 8。故答案为：A.。 4．对于一棵满二叉树，第i层的节点数是第i-1层节点数的（   ）倍。 A．1 B．2 C．3 D．4 【答案】B 【详解】本题考查树。满二叉树每增加一层，节点数翻倍，所以第i层的节点数是第i-1层的2倍。故选B。 考点二 二叉树 知●识●解●构 知识点1 二叉树的概念、性质、满二叉树、完全二叉树 1.二叉树基本概念 二叉树是一个具有n（n≥0）个节点的一个有限集合，且各个节点的度小于或等于2，二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。 二叉树的特点： （1）当n=0时，为空二叉树 （2）当n>=1时，二叉树由一个根节点和两个互不相交的被称为左子树和右子树组成，左子树和右子树又分别是一棵二叉树。 2.基本形态 3.满二叉树 基本概念： 一棵高度为h，含有2h-1个节点的二叉树称为满二叉树，即树中的每一层都含有最多的节点。满二叉树的叶子节点都集中在二叉树的最下一层，除叶子节点以外每个节点的度数都为2。 4.完全二叉树 基本概念：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。 注意 四个判断 （1）满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 （2）空二叉树和只有根结点的二叉树，既是满二叉树，也是完全二叉树。 （3）完全二叉树可看作在满二叉树的最下一层，从右向左连续删除若干个结点后得到；这里“连续”是关键，中间不能留空。 （4）完全二叉树中，一个结点如果没有左孩子，就一定没有右孩子；否则最后一层会出现空位，违反“从左向右连续填充”。 5.二叉树的性质 性质 1 第 k 层上至多有 2^(k−1)​ 个结点（k ≥ 1）。 性质 2 深度为 k 的二叉树至多有 2^k − 1 个结点（k ≥ 1）。 性质 3 任何一棵二叉树，若叶子结点数为 n₀、度为 2 的结点数为 n₂，则 n₀ = n₂ + 1。 证明：结点总数 n = n₀ + n₁ + n₂；除根外每个结点恰有一条入边，故边数 = n − 1；而边数又等于各结点出度之和 = n₁ + 2n₂。 于是 n₁ + 2n₂ = n − 1 = n₀ + n₁ + n₂ − 1，得 n₀ = n₂ + 1。 性质 4 具有 n 个结点的完全二叉树的深度为 ⌊log₂n⌋ + 1（等价于 ⌈log₂(n+1)⌉）。 性质 5 含 n 个结点的完全二叉树按层序编号：自第 1 层起，每层从左到右，根结点编号为 1。对任一结点 i（1 ≤ i ≤ n）： 若 i = 1，则该结点是根，没有父结点；若 i > 1，则其父结点为 ⌊i/2⌋。 若 2i > n，则 i 没有左孩子；否则左孩子为 2i。 若 2i + 1 > n，则 i 没有右孩子；否则右孩子为 2i + 1。 注：性质 5 的公式以“编号从 1 开始”为前提；如果数组下标从 0 开始，父结点为 ⌊(i−1)/2⌋，左孩子为 2i+1，右孩子为 2i+2。 知识点2 二叉树的建立 （1）数组实现 完全二叉树：从根开始按“自上而下、自左向右”编号，根编号为 0，其余编号 1…n−1，编号即数组下标，依次存入一维数组，不浪费空间。 非完全二叉树：先补全为完全二叉树，补上的结点用虚线或特殊值（如 #）表示；再按同一规则编号存数组。空结点也占位，单支树最坏需 2^n − 1 个存储单元。 （2）链表实现 每个结点含三个域：lchild | data | rchild，分别存放左孩子指针、数据元素、右孩子指针；空指针用 NULL（或 ^）表示需要快速查找父结点时，可增设 parent 域构成三叉链表。 （3）嵌套列表实现 表示规则： 用三层列表表示一个结点：[根结点, 左子树, 右子树] 根结点存放数据（值）。 左、右子树仍是同样结构的嵌套列表（递归定义）。 空树用空列表 [] 表示。 例： t = ['a', ['b', ['d'], ['e']], ['c', [], ['f']]] 对应：a 为根；左孩子 b（b 的孩子 d、e）；右孩子 c（右孩子 f）。 知识点3 二叉树的遍历 前序遍历（DLR） 首先访问根结点，其次遍历左子树，最后遍历右子树。 遍历序列：ABDHECFG 中序遍历（LDR） 首先访问左子树，其次遍历根结点，最后遍历右子树。 遍历序列：HDBEAFCG 后序遍历（LRD） 首先访问左子树，其次遍历右子树，最后遍历根结点。 遍历序列：HDEBFGCA 拓展链接 哈夫曼树（最优二叉树）特点： 一、定义与本质 哈夫曼树： 给定 n 个权值作为 n 个叶子结点，构造出的带权路径长度 WPL = Σwᵢ·lᵢ 最小的二叉树（lᵢ 为叶子到根的路径长度，即边数），又称最优二叉树。 构造方法（贪心）​： 每次从集合中取出两个权值最小的结点合并，新结点的权值为二者之和，再放回集合；重复 n₀−1 次，直到只剩一个结点。 二、四个特点 1.只有度为 0 和度为 2 的结点，没有度为 1 的结点，因此哈夫曼树是严格二叉树（正则二叉树）。 2.结点数关系：n = n₀ + n₂，由 n₀ = n₂ + 1 得 n = 2n₀ − 1 = 2n₂ + 1。其中 n₀ 为叶子数（待编码的字符数），构造时共合并 n₀ − 1 次。 3.权值较大的叶子结点离根较近，编码较短；准确地说，是权值越大，编码长度一定不会更长（权值相等时深度可能相同），不可理解为严格一一单调。 4.绘制与编码约定：合并时小数在左、大数在右；左分支记 0，右分支记 1。此约定不是强制的，左右可互换、0/1 可互换，但同一棵树内必须统一，故哈夫曼编码不唯一（码长与 WPL 最优性唯一）。 考●向●破●译 考向1 利用二叉树性质计算结点数量；完全二叉树父子结点编号换算 例1【2024 年 8 月浙江 A9 协作体高三返校联考】 一个具有 1025 个结点的二叉树，其高度最小为（）。 A.10 B.11 C.12 D. 不确定 答案：B 解析：结点总数固定时，完全二叉树高度最小。 【变式1】【2025 学年台州高二期末统考】 一棵完全二叉树共有 701 个结点，则该二叉树中的叶子结点数为（）。 A.350 B.351 C.352 D.353 答案：B 设叶子结点 n₀、度为1的结点 n₁、度为2的结点 n₂。 二叉树基本关系： n₀ = n₂ + 1 总结点 n = n₀ + n₁ + n₂ = 701 完全二叉树中，n₁ 只能为 0 或 1。 若 n₁ = 1：n₀ + n₂ = 700，代入 n₀ = n₂ + 1 → 2n₂ + 1 = 700 → n₂ = 349.5（不是整数，舍去） 若 n₁ = 0：n₀ + n₂ = 701 → 2n₂ + 1 = 701 → n₂ = 350，故 n₀ = 351 【变式2】【2025天域全国名校协作体 10 月联考】 已知一棵完全二叉树按 1 起始层序编号，结点编号为 20，则它的左孩子编号是（），右孩子编号是（）。 A.40，41 B.41，42 C.10，11 D.10，无 答案：A 解析：1 起始，i=20，左孩子 = 2×20=40，右孩子 = 2×20+1=41；只要 40、41≤总结点数，子结点就存在。 考向2 根据遍历序列还原二叉树，推导未知遍历序列 例1【2024 学年第二学期期中杭州地区 】 二叉树某二叉树前序遍历是 ABDCEF, 中序遍历是 DBAECF, 关于此二叉树下列说法正确的是 二叉树A. 二叉树有 2 个叶子节点 二叉树B. 该树是完全二叉树 二叉树C. 度为 2 和度为 1 的节点个数相同 二叉树D. 要成为一个满二叉树，至少需要增加 1 个节点 答案：D 解析： A：叶子 D、E、F 共 3，错误。 B：完全二叉树要求最后一层的结点全部靠左，本树 B 的右孩子位置空缺，后面 C 的两个子节点占据 3 层 3、4 号位，中间 2 号位空，节点没有靠左排布，不是完全二叉树，B 错误。 C：度为 2 节点数量 2，度为 1 节点数量 1，数量不相等，C 错误。 D：高度为 3 的满二叉树总节点 7，现有 6 个，仅需要给 B 增加 1 个右孩子节点即可得到满二叉树，至少增加 1 个，D 正确。 【变式1】【2026·浙江·一模】 若某二叉树的前序遍历结果为ABDECF，后序遍历结果为DEBFCA，则该二叉树的中序遍历结果可能为（   ） A．DBAFEC B．DBEACF C．DEBACF D．BDEAFC 【答案】B 【详解】本题考查二叉树的遍历序列推导能力。首先根据前序遍历规则（根-左-右），前序序列ABDECF的第一个元素A是整棵树的根节点；再结合后序遍历规则（左-右-根），后序序列DEBFCA的最后一个元素A也验证了根节点为A，且A的子树部分对应后序序列的前5位DEBFC。前序中A之后的元素B是A的左子树的根，对应后序序列中B的位置是倒数第二位，说明B是A左子树的根，后序中B左侧的DE属于B的子树，B右侧的F C属于A的右子树。前序中B之后的D是B的子节点，DE构成B的子树，前序后续的E、C、F对应剩余结构，推导可得该二叉树的中序遍历序列为DBEACF，匹配第二个选项。故答案为：B。 【变式2】【2026·浙江·一模】 某二叉树的前序遍历序列为C-F-A-？-？-E，中序遍历序列为F-D-A-C-E-B，则以下说法正确的是（   ） A．该二叉树的深度为3 B．节点A和节点E为兄弟节点 C．将该二叉树变为完全二叉树至少需要增加3个节点 D．该二叉树的后序遍历序列是DAFEBC 【答案】D 【详解】 A 错：路径 C→F→A→D 共 4 层，深度为 4。 B 错：A 是 F 的孩子，E 是 B 的孩子，两者父结点不同，不是兄弟。 C 错：按完全二叉树层序编号，该树 6 个结点占据 1、2、3、5、6、10 号位置； 要保留 10 号结点就必须填满 1～10 号，缺 4、7、8、9 共 4 个位置， 故至少增加 4 个结点，而非 3 个。 D 对：后序 = 左子树(DAF) + 右子树(EB) + 根(C) = D A F E B C。 【变式3】 某二叉树的数组表示如图所示，下列说法正确的是（   ） 0 1 2 3 4 5 6 7 8 9 10 A B C D E F A．该二叉树是一棵完全二叉树，其高度是4 B．二叉树中度为2的节点数比叶子节点数多1 C．该二叉树的前序遍历结果为ABDEFC，中序遍历结果为BDAECF D．可用列表["A",["B",None,["D",["E",None,None],["F",None,None]]],["C",None,None]]表示该二叉树 【答案】D 【详解】 A 错：3 号位置为空而 4 号位置有结点 D，不满足"从左向右连续填充"， 不是完全二叉树（高度为 4 是对的，但前半句错）。 B 错：度为 2 的结点是 A、D 共 2 个，叶子是 C、E、F 共 3 个； 由 n0 = n2 + 1，度为 2 的结点应比叶子结点"少 1"，不是"多 1"。 C 错：前序 ABDEFC 正确（A→B→D→E→F→C）， 但中序应为 B E D F A C（B 的左子树空，B 后接 D 的左子树 E）， "BDAECF"错误。 D 对：列表表示法为 [根, 左子树, 右子树]，逐一核对： ["A", ["B", None, ["D", ["E",None,None], ["F",None,None]]], ["C",None,None]] A 的左是 B、右是 C；B 的左是 None、右是 D；D 的左 E 右 F，与树形一致。 考点三 二叉排序树 知识点 二叉排序树 一、概念 若左子树不空 → 左子树所有结点值 < 根值 若右子树不空 → 右子树所有结点值 > 根值 左右子树本身也各是一棵 BST（递归定义） 关键词：有序约束；通常无重复关键字 二、常见操作 查找：从根比大小，小往左、大往右，命中或遇空结束。 插入：同样沿大小路径走到空位放入；新结点一定是叶子。 删除：叶子直接删 / 单孩子用孩子顶替 / 双孩子用**前驱(左子树最大)或后继(右子树最小)**替换。 三、特点 中序遍历结果必为升序序列（最重要性质）。 查找效率取决于树形形态：均衡时 O(log n)，退化成"斜树"时 O(n)（与插入顺序有关）。 二叉树 VS 二叉排序树（高频对比） 考●向●破●译 考向 二叉排序树排序 例1依次插入关键字 45, 24, 67, 12, 53, 90, 38 构成二叉排序树，则结点 38 的父结点是（）。 A. 45　 B. 24　 C. 12 　D. 67 答案：B  解析： 逐个插入（小往左、大往右）： 插入 38：38<45→左到 24；38>24→右，空位放入，故挂在 24 的右孩子。 速记： 建树就是"从根开始一路比大小下走，遇空即放"。 【变式】给定二叉排序树如图所示，查找关键字 40 成功时，共需比较（）次。 A. 1 B. 2　 C. 3　 D. 4 答案：C 解析： 比较路径 50→30→40：40<50（第1次）走左；40>30（第2次）走右；命中 40（第3次）。共 3 次。 速记： 查找成功时比较次数 = 目标结点所在层次（根在第1层）。 真题溯源·考向感知 1.【26.01浙江选考卷】某二叉树有 a、b、c、d四个节点，若中序遍历序列为 abcd,后序遍历序列为 dcba,则该二叉树的树形结构为 答案：C 解析（递归确定根，逐层剥离）​ 核心口诀：后序定根，中序分左右。 后序序列 dcba 的最后一个是根 → a 为根。 在中序 abcd 中，a 左边没有任何结点 → a 无左子树，其余 bcd 全在 a 的右子树里。 右子树的后序为 dcb，最后一个 b 是右子树的根 → b 为 a 的右孩子；中序 bcd 中 b 左边无结点 → b 无左子树。 同理，右子树 cd 的根是 c，c 无左子树，右孩子为 d。 整棵树是 a → b → c → d 的右斜单支链，对应选项 C。 2.【25.01浙江选考卷】某二叉树如第9题图所示，若其中的一个叶子节点增加右子树(仅包含节点N),则新二叉树的中序遍历结果不可能是 A.CNBDAE B.CBDNAE C.CBDAEN D.NCBDAE 答案：D 原中序：C B D A E 叶子是 C、D、E，加右孩子 N 后依次为： C 的右下 → CNBDAE（A） D 的右下 → CBDNAE（B） E 的右下 → CBDAEN（C） 加右孩时，N 只能出现在该叶子之后。D 选项 NCBDAE 里 N 排在 C 之前，相当于 C 的左孩子，违反"加右子树"，故选 D。 速判：原序列 CBDAE 相对顺序不被打乱，只有 D 破坏了顺序。 3.【24.06浙江选考卷】某完全二叉树包含5个节点,其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为xy，则 x-y的值为 A.0 B.1 C2 D.3 答案：B（1）​ 5 个节点的完全二叉树形态唯一：根 R；左孩子 L（带两个孩子 LL、LR）；右孩子 RR（叶子）。 · 中序：LL L LR R RR → 根 R 排第 4 位，y = 4 · 后序：LL LR L RR R → 根 R 排第 5 位（后序最后必是根），x = 5 所以 x − y = 5 − 4 = 1，选 B。 速判：左子树有 3 个节点，故根在中序里是第 4 个；后序永远是第 5 个，差恒为 1。 4.【25.06浙江选考卷】某二叉树如第8题图所示，E节点在前序遍历序列中的位置记号为x。下列二叉树中E节点在中序遍历序列中的位置序号也为x的是 答案 B 原题图中 E 是“左孩子的右孩子”，5 个节点： 前序：根(1) → 左孩子(2) → 左孩子的左叶(3) → E(4)​ → 右叶(5)，故 x = 4 原图中序： E 排第 3，不满足，需另找 逐项看 E 在中序中的位置（中序 = 左子树 → 根 → 右子树）： A：结构与原图相同，E 仍在第 3 位 B：E 是根，其左子树有 3 个节点 → 前三位是左子树，E 恰排第 4 位 C：E 是根的右孩子，前面有 4 个节点 → 第 5 位 D：E 是右孩子的左孩子，排第 3 位 故选 B。速判：中序中 E 的位置 = 其左子树节点数 + 1，要等于 4，E 的左子树必须有 3 个节点，只有 B（E 为根、左子树 3 节点）满足。 5.【26.06浙江选考卷】某完全二叉树的中序遍历序列为STURV，则其根节点为 A.T B U C.R D.V 答案 C​ 5 个节点的完全二叉树形态唯一：根 + 左孩子（带 2 个孩子）+ 右孩子（叶子）。 中序 = 左子树(3个) → 根 → 右叶(1个)​，所以根是中序序列的第 4 个字符。 S T U R V 第 4 个是 R，故根节点为 R，选 C。 2 / 3 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $