NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 19 题

下列有关树的叙述中，叙述正确的有（ ）。

这题考树的性质和二叉树概念辨析。拿到题先想：树的边数公式、哈夫曼树构造规则、完全与满二叉树的定义区别、前序遍历的访问顺序。从这几个核心点入手，逐个排除干扰项。

很多同学容易把‘完全二叉树’和‘满二叉树’混为一谈，认为只要层满就是满二叉树；或者看到前序中 u 在 v 前就下意识认定是祖先关系，忽略了兄弟节点、堂兄弟节点在前序中也必然满足先后顺序。这些概念混淆会导致选错 C 和 D。

考点概念：树的性质与二叉树辨析

这道题考查的是数据结构中树的性质以及二叉树相关概念的精准区分。核心知识点包括：任意树的基本边数公式、哈夫曼树的构造特性、完全二叉树与满二叉树的定义差异，以及前序遍历的访问顺序规律。

逐项分析

选项 A：在含有 $n$ 个结点的树中，边数只能是 $(n-1)$ 条

这是树的最基础性质。树是连通且无环的图。若边数等于 $n$，必然形成环；若边数少于 $n-1$，则无法连通所有结点。因此，无论树的结构如何复杂（链状、星状、平衡状），只要它是树，边数严格等于 $n-1$。此选项正确。

选项 B：在哈夫曼树中，叶结点的个数比非叶结点个数多 $1$

哈夫曼树是二叉树。对于任何二叉树，若度为 0 的结点（叶结点）数为 $n_0$，度为 2 的结点数为 $n_2$，则恒有 $n_0 = n_2 + 1$。哈夫曼树在构造过程中，每个新结点的产生都是合并两棵子树，因此不存在度为 1 的结点（即 $n_1 = 0$）。此时非叶结点总数就是 $n_2$，所以叶结点确实比非叶结点多 1。此选项正确。

选项 C：完全二叉树一定是满二叉树

这是命题人最爱挖的坑。满二叉树要求每一层都完全填满，即第 $i$ 层有 $2^{i-1}$ 个结点。完全二叉树只要求除了最后一层外，其余层都满，且最后一层的结点必须靠左排列。

举个反例：深度为 3 的满二叉树有 7 个结点；而深度为 3 的完全二叉树可以有 4 个、5 个、6 个结点（只要最后一层靠左排满即可）。显然，完全二叉树不一定是满二叉树。此选项错误。

选项 D：在二叉树的前序序列中，若结点 $u$ 在结点 $v$ 之前，则 $u$ 一定是 $v$ 的祖先

前序遍历顺序是“根→左→右”。虽然祖先肯定在子孙之前，但反过来不成立。

考虑一棵二叉树：根为 A，左孩子为 B，右孩子为 C。前序序列是 A, B, C。这里 B 在 C 之前，但 B 和 C 是兄弟关系，互不为祖先。甚至，若树更深，比如 A 有左孩子 B，B 有右孩子 C，前序是 A, B, C，C 在 B 之后，但 C 是 B 的子孙，符合；但若 C 是 B 的堂兄弟（即 B 的兄弟 D 的孩子），前序依然是 A, B, D, C，C 在 B 之后，但 C 不是 B 的祖先。因此，仅凭前序中的先后顺序无法断定祖先关系。此选项错误。