🏷️ 知识点：树的概念

共 19 道相关题目

模拟卷年第 3 题数据结构选择题

在下列遍历算法中，在遍历序列中叶结点之间的次序可能与其他算法不同的算法是（）。

A. 先序遍历算法 B. 中序遍历算法 C. 后序遍历算法 D. 层次遍历算法

[tag_link]

正确答案：D

先序、中序和后序遍历算法均属于深度优先遍历，其递归或迭代过程都遵循先处理左子树、后处理右子树的原则。因此，对于任意二叉树，这三种遍历算法访问叶结点的次序始终相同：左子树中的所有叶结点都先于右子树中的所有叶结点被访问，且左、右子树内部叶结点的相对顺序也一致。而层次遍历算法采用广度优先策略，按层次从上到下、从左到右访问节点。由于叶结点可能分布在不同层次，其访问次序取决于层次和同一层次中的左右位置，可能与深度优先遍历的叶结点次序不同。例如，对于根节点有左子节点（含两个叶结点）和右子节点（为叶结点）的二叉树，先序、中序和后序遍历的叶结点次序均为左子树中的两个叶结点先于右子叶结点，而层次遍历则先访问右子叶结点（位于第二层），再访问左子树中的叶结点（位于第三层）。因此，层次遍历算法的叶结点次序可能与其他算法不同。

2010 年第 3 题数据结构选择题

下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是()。

A B C D

[tag_link]

正确答案：D

题中所给二叉树的后序序列为 d,b,c,a。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。故选 D。

2026 年第 4 题数据结构选择题

森林 F 中有 5 颗树，其节点个数分别为 2、3、4、5、7，森林中树的次序可以任意，问 F 对应的二叉树最小高度为多少？

A. 5 B. 6 C. 8 D. 10

[tag_link]

正确答案：B

**【解析】**这是一道 森林 → 二叉树（左孩子 - 右兄弟表示法） 的经典题。**关键结论（必须掌握）**把森林转换为二叉树（左孩子 - 右兄弟）后：****二叉树的高度 = max( 第 i 棵树的高度 + (i − 1) )****其中

第i棵树是森林中从左到右的顺序；
(i−1)来自“右兄弟”链；
为了最小高度，应当把高度最大的树放在最前面。先算每棵树的最小可能高度一棵有n个结点的普通树，其最小高度为：hmin=⌈log2(n+1)⌉
结点数最小高度
7 ⌈log28⌉= 3
5 ⌈log26⌉= 3
4 ⌈log25⌉= 3
3 ⌈log24⌉= 2
2 ⌈log23⌉= 2

结点数	最小高度
7	⌈log28⌉= 3
5	⌈log26⌉= 3
4	⌈log25⌉= 3
3	⌈log24⌉= 2
2	⌈log23⌉= 2

排序（从大到小）：3, 3, 3, 2, 2计算二叉树最小高度按最优顺序依次计算：

i	树高 hi	hi+(i−1)
1	3	3
2	3	4
3	3	5
4	2	5
5	2	6

最大值 = 6

模拟卷年第 4 题数据结构选择题

设高度为 100 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数最少为（　）。

A. 100 B. 201 C. 199 D. 200

树的概念

[tag_link]

正确答案：C

首先，由题意可知，二叉树中只有度为0和度为2的结点，根据二叉树性质，有

$n_{0} = n_{2} + 1$ （其中 $n_{0}$ 为叶子结点数， $n_{2}$ 为度为2的结点数），因此总结点数 $n = n_{0} + n_{2} = 2 n_{2} + 1$ ，即 $n$ 必为奇数，排除选项A和D。

其次，考虑最小结点数的情况。高度为100通常指树的层数为100（根结点在第1层）。为了使结点数最少，树应形成一种“偏斜”形状：每个内部结点（度为2）有一个子结点为内部结点延续高度，另一个子结点为叶子结点。这样，从根到最深叶子路径上的结点均为内部结点（除最深叶子外），且每个内部结点附带一个不在该路径上的叶子结点。
具体计算：设高度为

$h$ （层数），则路径上有 $h$ 个结点，其中前 $h - 1$ 层为内部结点，第 $h$ 层为叶子结点。

内部结点数为 $h - 1$ ，每个内部结点附带一个叶子结点，故附加叶子结点数为 $h - 1$ ，加上路径上的叶子结点1个，总叶子结点数为 $h$ 。因此总结点数 $n = (h - 1) + h = 2 h - 1$ 。代入 $h = 100$ ，得 $n = 2 \times 100 - 1 = 199$ 。
若高度定义为边数，则最小结点数为

$2 h + 1 = 201$ ，但结合常见教材定义（高度指层数）及选项奇偶性，本题应取层数定义，故最小结点数为199。

模拟卷年第 4 题数据结构选择题

有关二叉树下列说法正确的是（）。

A. 二叉树的度为 2 B. 一棵二叉树的度可以小于 2 C. 二叉树中至少有一个结点的度为 2 D. 二叉树就是度为 2 的有序树

树的概念

[tag_link]

正确答案：B

二叉树是一种树形结构，其特点是每个结点最多有两个子结点，且子结点有左右之分，称为左子结点和右子结点。

树的度定义为树中所有结点的度的最大值，而结点的度是指该结点拥有的子结点数。因此，在二叉树中，结点的度可以是 0、1 或 2，这意味着整个二叉树的度可以是 0、1 或 2，即可以小于 2。选项 B 正确，因为它反映了二叉树度可以小于 2 的可能性。
选项 A 错误，因为二叉树的度不一定为 2，例如只有一个根结点的二叉树度为 0。选项 C 错误，因为二叉树中并不要求至少有一个结点的度为 2，例如所有结点度均为 0 或 1 的二叉树是存在的。选项 D 错误，因为二叉树强调每个结点最多有两个子结点且有序，但“度为 2 的有序树”可能被误解为所有结点度均为 2，而二叉树允许结点度小于 2，因此两者并不完全等价。

模拟卷年第 4 题数据结构选择题

若一棵二叉树中有 24 个叶结点，有 28 个仅有一个孩子的结点，则该二叉树的总结点数为（）。

A. 70 B. 73 C. 75 D. 77

树的概念

[tag_link]

正确答案：C

设二叉树中度为 $0$ 、 $1$ 、 $2$ 的结点数分别为 $n_{0}$ 、 $n_{1}$ 、 $n_{2}$ 。已知叶结点数 $n_{0} = 24$ ，仅有一个孩子的结点数 $n_{1} = 28$ 。由二叉树的性质： $n_{0} = n_{2} + 1$ ，可得 $n_{2} = n_{0} - 1 = 23$ 。总结点数 $n = n_{0} + n_{1} + n_{2} = 24 + 28 + 23 = 75$ 。

2013 年第 4 题数据结构选择题

已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是（）。

树的概念带权路径长度

A.27

B.46

C.54

D.56

[tag_link] 正确答案：B将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为 0 的虚叶结点，对于严格的三叉树(n0−1)%(3−1)=u=1\=0，需要添加m−u−1=3−1−1个叶结点，说明 7 个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为 0 的叶结点应离树根最远构造最小带权生成树的过程如下：最小的带权路径长度为(2+3)×3+(4+5)×2+(6+7)×1=46。

2012_Q41_1

2014 年第 4 题数据结构选择题

若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是()。

A.e、c

B.e、a

C.d、c

D.b、a

[tag_link]

正确答案：D

线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列 debxac, 中序遍历中在 x 左边和右边的字符，就是它在中序线索化的左、右线索，即 b、a, 选 D。

2022 年第 4 题数据结构选择题

若三叉树 T 中有244个结点(叶结点的高度为1),则 T 的高度至少是()。

A.8

B.7

C.6

D.5

[tag_link]

正确答案：C

高度为 n 的二叉树最多有 1 + 2 + ⋯ + 2 n − 1 = 2 n − 1 个结点，高度为 n 的三叉树最多有 f ( n ) = 1 + 3 + ⋯ + 3 n − 1 = 3 − 1 3 n − 1 − 2 3 n − 1 。f ( 5 ) = 121 f ( 6 ) = 364 因为 121 < 244 < 364 ，所以高度至少为 6。

2026 年第 5 题数据结构选择题

假设二叉树中节点权值为a=1,b=2,c=4,d=5,e=8,f=10,g=12。当带权路径长度（WPL）最小时，与节点e（权值 8）处于相同深度的节点是哪些？

A. d B. g C. d,f D. f,g

[tag_link]

正确答案：D

**【解析】**为了最小化带权路径长度（WPL），需构建哈夫曼树。节点权值依次为 1, 2, 4, 5, 8, 10, 12。构建过程如下：

合并权值 1 和 2，得到新节点 3；
合并 3 和 4，得到新节点 7；
合并 5 和 7，得到新节点 12；
合并 8 和 10，得到新节点 18；
合并原始权值 12（节点 g）与内部节点 12，得到新节点 24；
最后合并 18 和 24，得到根节点 42。由此树结构可知，节点 e（权值 8）深度为 2（路径长度），同时节点 f（权值 10）和 g（权值 12）深度也为 2，而其他节点深度均不同（d 深度为 3，c 深度为 4，a、b 深度为 5）。因此，与节点 e 处于相同深度的节点是 f 和 g。

2010 年第 5 题数据结构选择题

在一棵度数为4的树 T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树 T 的叶结点个数是()。

A.41 B.82 C.113 D.122

[tag_link]

正确答案：B

设树中度为 i（i=0,1,2,3,4）的结点数分别为 N i , 树中结点总数为 N，则树中各结点的度之和等于 N-1，即 N = 1 + N 1 + 2 N 2 + 3 N 3 + 4 N 4 = N 0 + N 1 + N 2 + N 3 + N 4 ，根据题设中的数据，即可得到 N 0 = 82 ,即树 T 的叶结点的个数是 82。

2009 年第 5 题数据结构选择题

已知一棵完全二叉树的第6层(设根为第1层)有 8 个叶结点，则该完全二叉树的结点个数最多是 ()。

A.39

B.52

C.111

D.119

[tag_link]

正确答案：C

完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7 时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 8×2=16 个叶结点，故完全二叉树的结点个数最多为 ( 2 7 − 1 ) − 16 = 111 个结点。

模拟卷年第 6 题数据结构选择题

在下列二叉树中，（）的所有非叶结点的度均为 2。 Ⅰ. 完全二叉树 Ⅱ. 满二叉树 Ⅲ. 平衡二叉树 Ⅳ. 哈夫曼树 Ⅴ. 二叉排序树

A. Ⅱ和Ⅳ B. Ⅰ和Ⅲ C. Ⅱ、Ⅳ和Ⅴ D. Ⅱ、Ⅲ和Ⅳ

树的概念哈夫曼树

[tag_link]

正确答案：A

首先，理解题意：所有非叶结点的度均为 2，意味着二叉树中每个内部节点都必须有两个子节点。

接下来逐一分析所列二叉树类型：

完全二叉树的定义是除最后一层外，其他层节点数达到最大值，且最后一层节点尽量靠左排列。 > 在这种情况下，非叶结点可能只有一个子节点（例如，当树节点数较少时），因此度可能为 1 或 2，不满足所有非叶结点度均为 2 的条件。 >

满二叉树则严格要求每个节点要么是叶子节点（度为 0），要么有两个子节点（度为 2）。 > 因此，满二叉树的所有非叶结点度均为 2，符合条件。 >

平衡二叉树（如 AVL 树）主要关注左右子树高度平衡，不限制节点的度数。 > 在平衡二叉树中，非叶结点可能只有左子节点或右子节点，即度可以为 1，所以不满足要求。 >

哈夫曼树在构建过程中，每次合并两个节点形成新的内部节点，因此每个内部节点都有两个子节点。 > 哈夫曼树的所有非叶结点度均为 2，符合条件。 >

二叉排序树中，节点度数取决于插入顺序和树的结构，非叶结点常常可能只有一个子节点（例如，在偏斜树中），因此度可能为 1 或 2，不满足所有非叶结点度均为 2 的条件。 >

综上，只有满二叉树和哈夫曼树满足所有非叶结点的度均为 2，对应选项中的Ⅱ和Ⅳ，故正确答案为 A。 >

2011 年第 6 题数据结构选择题

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是（）。

树的概念

A. 115

B. 116

C. 1895

D. 1896

[tag_link]

正确答案：D

树转化为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数＝分支结点数+1 = 2011-116+1 = 1896。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 = 2011-115 = 1896。

2009 年第 6 题数据结构选择题

将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中， u 和 v 可能具有的关系是 ( ) 。

I. 父子关系

Ⅱ.兄弟关系

Ⅲ.u 的父结点与 v 的父结点是兄弟关系

A. 只有Ⅱ

B. I 和 Ⅱ

C. I 和 Ⅲ

D. I 、Ⅱ 和 Ⅲ

[tag_link]

正确答案：B

森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形 I：若结点 V 是结点 u 的第二个孩子结点，在转换时，结点 V 就变成结点 u 第一个孩子的右孩子，符合要求。情形 II：结点 u 和 V 是兄弟结点的关系，但二者之中还有一个兄弟结点 k, 则转换后，结点 V 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩子，符合要求。情形 III: 若结点 u 的父结点与 v 的父结点是兄弟关系，则转换后，结点 u 和 v 分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。
【逆向法】由题意可知 u 是 v 的父结点的父结点，如下图所示有 4 种情况：
根据树与二叉树的转换规则，将这 4 种情况转换成树种结点的关系。(1) 在原来的树中 u 是 v 的父结点的父结点；(2) 在树中 u 是 v 的父结点；(3) 在树中 u 是 v 的父结点的兄弟；(4) 在树中 u 与 v 是兄弟关系。由此可知 I 和 II 正确。

模拟卷年第 7 题数据结构选择题

给定结点个数 n，在下面二叉树中，叶结点个数不能确定的是（）。

A. 满二叉树 B. 完全二叉树 C. 哈夫曼树 D. 二叉排序树

树的概念哈夫曼树

[tag_link]

正确答案：D

对于给定的结点个数

$n$ ，分析各选项中叶结点个数是否确定。

满二叉树若存在，则

$n$ 必须满足 $n = 2^{h} - 1$ ，此时叶结点个数为 $2^{h - 1}$ ，由 $n$ 唯一确定。

完全二叉树中，叶结点个数为

$⌈ n /2 ⌉$ ，也是确定的。

哈夫曼树中，总结点数

$n$ 与叶结点数 $m$ 满足关系 $n = 2 m - 1$ ，因此叶结点数 $m = (n + 1) /2$ ，同样由 $n$ 确定。

但在二叉排序树中，对于相同的

$n$ ，可以构造不同形态的树（如平衡树或单支树），叶结点个数会随之变化，因此不能确定。

模拟卷年第 9 题数据结构选择题

下列关于 m 阶 B-树的说法中，正确的有（）。 I. 每个结点至少有两棵非空子树 II. 非叶结点仅起索引作用，每次查找一定会查找到某个叶结点 III. 所有叶子在同一层上 IV. 插入一个数据项引起 B-树结点分裂后，树长高一层

A. I、II B. II、III C. III、IV D. III

B树树的概念

[tag_link]

正确答案：D

本题考查 B-树的性质。

m 阶 B-树根结点至少有两棵子树（这两棵子树可以是空树），其他非叶结点至少有 $⌈ \frac{m}{2} ⌉$ 棵子树，因此 I 错误。 II 是 B+ 树的性质。 B-树又称多路平衡查找树，叶结点都在同一层次上，可视为查找失败结点，因此 III 正确。结点的分裂不一定会使树高增加 1，如图 1 所示；只有当分裂传递到根结点并使根结点也分裂时，树高才会增加 1，如图 2 所示，因此 IV 错误。

2021 年第 9 题数据结构选择题

在一棵高度为 3 的 3 阶 B 树中，根为第 1 层，若第 2 层中有 4 个关键字，则该树的结点个数最多是（）。

树的概念

A. 11 B. 10 C. 9 D. 8

[tag_link]

正确答案：A

保证特性中的结点数量尽量多，然后每个结点中元素数量尽量多。 3 阶 B 树中个结点最多有两个元素，三个孩子。

2016 年第 42 题数据结构综合题

如果一棵非空k（k≥2）叉树T中每个非叶结点都有k个孩子，则称T为正则k叉树。请回答下列问题并给出推导过程。

(1) 若T有m个非叶结点，则T中的叶结点有多少个？

(2) 若T的高度为h（单结点的树h=1），则T的结点数最多为多少个？最少为多少个？

树的概念

1）根据定义，正则k叉树中仅含有两类结点；叶结点（个数记为n0）和度为k的分支结点（个数记为n1）。树T中的结点总数n=n0+nk=n0+m。树中所含的边数e=n−1，这些边均为m个度为k的结点发出的，即e=mk。整理得n0+m=mk+1，故n0=(k−1)m+1。

2）高度为h的正则k叉树T中，含最多结点的树形为：除第h层外，第1层到第h−1层的结点都是度为k的分支结点；而第h层均为叶结点，即树是“满”树。此时第j（1≤j≤h）层结点数为kj−1，结点总数M1为M1=i=0∑hkj−1=k−1kh−1含最少结点的正则K叉树的树形为：第1层只有根结点，第2层到第h−1层仅含1个分支结点和k−1个叶结点，第h层有K个叶结点。即除根外第2层到第h层中每层的结点数均为k，故T中所含结点总数M2为M2=1+(h−1)k【评分说明】①

[tag_link]

参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。②若考生仅给出结果，但没有推导过程，则 (1)、(2) 的最高得分分别是 2 分和 3 分。若推导过程或答案不完全正确，酌情给分。

← 返回真题分析