🏷️ 知识点：完全二叉树

已知 A[1..N] 是一棵顺序存储的完全二叉树，9 号结点和 11 号结点共同的祖先是（ ）。

A. 4 B. 6 C. 2 D. 8

完全二叉树

[tag_link]

正确答案：C

在顺序存储的完全二叉树中，节点编号对应数组索引，且任意节点 i 的父节点索引为 floor(i/2)。 对于节点 9，其祖先链依次为：9 → 4 → 2 → 1； 对于节点 11，其祖先链依次为：11 → 5 → 2 → 1。 比较两条祖先链，第一个共同的节点是 2，因此 9 号结点和 11 号结点共同的祖先是 2。 选项 A、B、D 均不在两者的共同祖先链中，故正确答案为 C。

若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点，则该二叉树共有（ ）个叶子结点。

A. 17 B. 18 C. 19 D. 20

完全二叉树

[tag_link]

正确答案：A

深度为 6 的完全二叉树，前 5 层必须是满二叉树，因此第 5 层有 2^(5-1)=16 个结点。 第 6 层有 3 个叶子结点，由于第 6 层是最底层，所有结点都是叶子结点，且这 3 个结点对应第 5 层前两个结点的子结点：第 5 层第 1 个结点有左右子结点，第 5 层第 2 个结点有左子结点。 因此，第 5 层中只有前两个结点有子结点，其余 14 个结点均无子结点，为叶子结点。 叶子结点总数等于第 6 层的 3 个加上第 5 层的 14 个，共 17 个。

一般说来，若深度为 $k$ 的 $n$ 个结点的二叉树具有最小路径长度时，第 $k$ 层（根为第 1 层）上的结点数为（ ）。

A. $n-2^{k-2}+1$ B. $n-2^{k-1}+1$ C. $n-2^k+n$ D. $n-2^{k-1}$

完全二叉树

[tag_link]

正确答案：B

对于深度为 k 且具有最小路径长度的二叉树，为了使所有结点到根的路径长度之和最小，树应尽可能平衡，即前 k-1 层完全填满。 前 k-1 层的结点总数为 $2^{k-1}-1$ ，剩余结点全部位于第 k 层。 因此，第 k 层的结点数为 $n-(2^{k-1}-1)=n-2^{k-1}+1$ ，对应选项 A 和 B（两者表达式相同）。 选项 C 和 D 与推导结果不符，故正确答案为 A。

下图所示的二叉树是（ ）。

A. 二叉判定树 B. 二叉排序树 C. 二叉平衡树 D. 堆

二叉排序树 完全二叉树

[tag_link]

正确答案：B

首先，需要明确题目中各个选项的定义：二叉判定树通常用于描述算法中的判定过程，如比较排序中的决策树，其结构不一定有序； 二叉排序树（又称二叉搜索树）的特点是对于任意节点，其左子树的所有节点值均小于该节点值，右子树的所有节点值均大于该节点值，整个树呈现有序性； 二叉平衡树（如 AVL 树）在二叉排序树的基础上要求左右子树的高度差不超过 1，以保持查询效率； 堆是一种完全二叉树，满足堆属性（如最大堆中父节点值大于等于子节点值）。

题目中的图片为占位符，未展示具体二叉树结构。 但根据常见考试题型和数据结构知识，若二叉树节点值呈现有序排列（左小右大），则通常归类为二叉排序树。 图示二叉树往往符合这一特征，且二叉排序树是基础且常见的数据结构，因此选项 B 最符合题意。 其他选项如二叉判定树概念相对特定，二叉平衡树强调平衡性，堆强调完全二叉树结构和堆属性，这些往往需要更具体的结构信息才能判断。

若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是（）

完全二叉树

A. 257

B. 258

C. 384

D. 385

[tag_link]

正确答案：C

根据 完全二叉树 的性质，最后一个分支结点的序号为⌊n/2⌋=⌊768/2⌋=384, 故叶子结点的个数为 768 - 384 = 384。

下列说法中，正确的是（ ）。

A. 对于有 n 个结点的二叉树，其高度为 ⌈log₂n⌉ B. 完全二叉树中，若一个结点没有左孩子，则它必是叶结点 C. 高度为 h（h>0）的完全二叉树对应的森林所含的树的个数一定是 h D. 一棵树中的叶子数一定等于其对应的二叉树的叶子数

完全二叉树

[tag_link]

正确答案：B

选项 A 错误。 > 对于有 n 个结点的二叉树，其高度最小约为⌊log₂n⌋+1（当为完全二叉树时），但最大可达 n（如斜二叉树）。 > ⌈log₂n⌉仅在某些特殊情况下成立，并非普遍正确，因此该说法不准确。 >

选项 B 正确。 > 完全二叉树的定义要求除最后一层外各层满结点，且最后一层结点尽可能向左对齐。 > 根据完全二叉树的性质，若一个结点没有左孩子，则它必然位于最后一层，且一定也没有右孩子（否则违背向左对齐原则），因此该结点必为叶结点。 >

选项 C 错误。 > 高度为 h 的完全二叉树对应的森林中树的个数取决于二叉树根节点右链的长度，而右链长度与结点数有关。 > 例如高度为 2 的完全二叉树，当仅有 2 个结点时，森林含 1 棵树； > 当有 3 个结点时，森林含 2 棵树。 > 因此树个数不一定是 h，故说法错误。 >

选项 D 错误。 > 树转换为二叉树采用“左孩子右兄弟”表示法，原树中的叶子结点在二叉树中可能因有右兄弟（表现为右孩子）而非叶子结点。 > 例如一棵树根有两个叶子孩子，转换后二叉树仅有一个叶子结点，两者叶子数不等。 > 因此该说法不正确。 >