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

第09讲 树的操作 目录 01 课标达标练 题型 树的操作对点选择 02 核心突破练 03 真题溯源练 树的操作对点选择 1．【概念辨析】 下列关于树的基本术语，说法正确的是（） A．有 n 个结点的树有 n 条边 B．叶子结点是度为 0 的结点 C．树的度就是根结点的度 D．根结点可以有多个前驱 答案：B 解析： 树有 n−1 条边，A 错；树的度是所有结点度的最大值（不一定在根），C 错；根无前驱，D 错；度为 0 即无子树，是叶子，B 对。 速记： 边数=n−1；树的度=最大度数；叶子=度0。 2．【完全二叉树计数】 一棵完全二叉树共有 50 个结点，则叶子结点个数为（） A．24　B．25　C．26　D．27 答案：B 解析： n₀=n₂+1，n=n₀+n₁+n₂=50，完全二叉树 n₁∈{0,1}。n₁=0→2n₂+1=50 不整除；n₁=1→n₀+n₂=49→2n₂+1=49→n₂=24，n₀=25。 速记： 总结点为偶数→n₁=1；为奇数→n₁=0。 3．【满/完全辨析】 下列说法正确的是（） A．完全二叉树一定是满二叉树 B．满二叉树一定是完全二叉树 C．深度相同的二叉树结点数一定相同 D．含空二叉树和仅根结点的树都不算完全二叉树 答案：B 速记： 满⊂完全；空树、仅根结点既是满也是完全。 4．【遍历写序列】 二叉树如下，其中序遍历结果是（） A / \ B C / D A．ABCD　B．BADC　C．BDAC　D．ADBC 答案：B 解析： 中序"左-根-右"：B，A，(D，C) → BADC。 速记： 中序对每个子树都"先走完左支再读根"。 5．【遍历还原互推】 某二叉树前序 A B D E C F、中序 D B E A C F，则后序为（） A．DEBFCA　B．DBEFCA　C．DEBCFA　D．BDEFCA 答案：A 解析： 根 A；左子树 B（左 D、右 E），右子树 C（右 F）。后序=左 D E 根B，右 F 根C，再 A → DEBFCA。 速记： 前序定根、中序分左右，逐层剥离。 6．【存储表示】 关于二叉树的表示，下列正确的是（） A．数组只能存储满二叉树 B．完全二叉树用一维数组顺序存储最省空间 C．嵌套列表表示法中根、左、右顺序可随意调换 D．二叉链表每个结点至少要 4 个域 答案：B 解析： 数组也能存非完全树（补空占位，浪费空间），A 错；嵌套列表 [根,左,右] 下标固定不能乱，C 错；二叉链表 3 个域（左孩子|数据|右孩子）即可，D 错。 7．【父子编号换算】 完全二叉树自根起按层序从 1 编号，编号 37 的结点其父结点编号为__，左孩子编号为__。 答案：18，74 解析： 父=⌊37/2⌋=18；左=2×37=74（右=75）。 速记： 从1起：父⌊i/2⌋、左2i、右2i+1；若下标从0起则左2i+1、右2i+2。 8．【BST判定】 判断一棵二叉树是否为二叉排序树，最简便的方法是（） A．前序是否递增　B．中序是否升序　C．后序是否递减　D．只比较根与左右孩子 答案：B 速记： BST ⇔ 中序升序；"只比父子"不够，须整棵子树都小于/大于根。 1．【遍历还原】〔新设问〕〔真题·2023浙江6月选考〕 某二叉树前序遍历为 BDEFCA，则中序遍历结果是（） A．EDCFBA　B．ECFDAB　C．BFDEAC　D．EDFCBA 答案：A 解析： 根 B，结合树形结构逐层划分左右子树，按"左-根-右"得 EDCFBA。 速记： 前序首=根；先定位根在中序位置，两侧即左右子树。 2．【前序+后序唯一性】〔新考法〕〔真题·杭州二中2024届高三选考模拟〕 已知二叉树前序 A-B-D-C-E、后序 D-B-E-C-A，则该树能否唯一确定？中序为？（） A．能，中序 B-D-A-E-C　 B．不能 C．能，中序 D-C-B-A-E　 D．不能 答案：A 解析： 前后序一般无法唯一确定，但本题结点对应单支关系可定：根 A，左子树 B（含子 D）、右子树 C（含子 E），还原得中序 B-D-A-E-C。 速记： "前序+中序"或"后序+中序"必唯一；"前序+后序"通常不唯一，本题结点少可定。 3．【表达式树·嵌套列表】〔新情境〕 用嵌套列表 [根,左,右] 表示表达式树（叶结点为 [值,None,None]，内部结点为 [运算符,左子树,右子树]）： t = ['*', ['+', ['2',None,None], ['3',None,None]], ['4',None,None]] (1) 画出对应二叉树；(2) 写出中序遍历结果；(3) 求表达式值。 答案： (1) 表达式为 (2+3)×4： * / \ + 4 / \ 2 3 (2) 中序：2 + 3 * 4（读作中缀，但树形已固定运算顺序）。 (3) 值 = (2+3)×4 = 20。 解析： 后序遍历即"后缀式/逆波兰式" 2 3 + 4 *，可无括号直接算；中序若不补括号会与原式顺序不同，体现树形消除运算歧义。 速记： 前缀式=先序、中缀式=中序、后缀式=后序；求值用后序最自然。 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。 学科网（北京）股份有限公司1 / 17 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $ 第09讲 树 目录 01 课标达标练 题型 树的操作对点选择 02 核心突破练 03 真题溯源练 树的操作对点选择 1．【概念辨析】 下列关于树的基本术语，说法正确的是（） A．有 n 个结点的树有 n 条边 B．叶子结点是度为 0 的结点 C．树的度就是根结点的度 D．根结点可以有多个前驱 2．【完全二叉树计数】 一棵完全二叉树共有 50 个结点，则叶子结点个数为（） A．24　B．25　C．26　D．27 3．【满/完全辨析】 下列说法正确的是（） A．完全二叉树一定是满二叉树 B．满二叉树一定是完全二叉树 C．深度相同的二叉树结点数一定相同 D．含空二叉树和仅根结点的树都不算完全二叉树 4．【遍历写序列】 二叉树如下，其中序遍历结果是（） A / \ B C / D A．ABCD　B．BADC　C．BDAC　D．ADBC 5．【遍历还原互推】 某二叉树前序 A B D E C F、中序 D B E A C F，则后序为（） A．DEBFCA　B．DBEFCA　C．DEBCFA　D．BDEFCA 6．【存储表示】 关于二叉树的表示，下列正确的是（） A．数组只能存储满二叉树 B．完全二叉树用一维数组顺序存储最省空间 C．嵌套列表表示法中根、左、右顺序可随意调换 D．二叉链表每个结点至少要 4 个域 7．【父子编号换算】 完全二叉树自根起按层序从 1 编号，编号 37 的结点其父结点编号为__，左孩子编号为__。 8．【BST判定】 判断一棵二叉树是否为二叉排序树，最简便的方法是（） A．前序是否递增　B．中序是否升序　C．后序是否递减　D．只比较根与左右孩子 1．【遍历还原】〔新设问〕〔真题·2023浙江6月选考〕 某二叉树前序遍历为 BDEFCA，则中序遍历结果是（） A．EDCFBA　B．ECFDAB　C．BFDEAC　D．EDFCBA 2．【前序+后序唯一性】〔新考法〕〔真题·杭州二中2024届高三选考模拟〕 已知二叉树前序 A-B-D-C-E、后序 D-B-E-C-A，则该树能否唯一确定？中序为？（） A．能，中序 B-D-A-E-C　 B．不能 C．能，中序 D-C-B-A-E　 D．不能 3．【表达式树·嵌套列表】〔新情境〕 用嵌套列表 [根,左,右] 表示表达式树（叶结点为 [值,None,None]，内部结点为 [运算符,左子树,右子树]）： t = ['*', ['+', ['2',None,None], ['3',None,None]], ['4',None,None]] （1）画出对应二叉树；(2) 写出中序遍历结果；(3) 求表达式值。 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 学科网（北京）股份有限公司1 / 17 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $