题目
若三叉树 T 中有 244 个结点[1] ( 叶结点的高度为 1 )，则 T 的高度至少是（ ） A 8 B 7 C 6 D 5
若三叉树 T 中有 244 个结点[1] ( 叶结点的高度为 1 )，则 T 的高度至少是（ ）
A 8
B 7
C 6
D 5
题目解答
答案
设三叉树的高度为 h，根结点到叶结点的路径上有 k 个三叉子树，则叶结点数目为 
。因为在三叉树中，每个节点最多有三个子节点，所以从根节点到叶子节点的路径上只可能经过三叉子树。因此，如果知道了三叉子树的个数 k，就可以计算出叶结点的数目。
根据题目信息，叶结点的高度为 1，即叶结点是三叉树中最底层的节点，因此叶结点数目为 244。
将 244 分解为 的形式，可得 k=5。具体来说，
，所以 k 的取值为 5。
因为根结点到叶结点的路径上有 k 个三叉子树，所以三叉树的高度为 h=k+1=6。这是因为三叉树的高度定义为从根节点到最远叶子节点的距离，也就是从根节点出发，到达最底层叶子节点的最长路径上的节点数目。在三叉树中，因为每个节点最多有三个子节点，所以它的高度也就是三叉子树的个数再加上一。
因此，三叉树 T 的高度至少是 6。故答案选择C
解析
考查要点：本题主要考查三叉树的结构特性及高度计算，需要结合完全三叉树的节点数公式进行推导。
解题核心思路：
- 完全三叉树的节点数公式为 $\frac{3^h - 1}{2}$，其中 $h$ 是树的高度。
- 题目要求找到满足总节点数为244的最小高度 $h$，需通过公式反推 $h$ 的最小值。
- 通过比较 $\frac{3^h - 1}{2}$ 与244的大小关系，确定 $h$ 的取值。
破题关键点：
- 完全三叉树的节点数公式是核心工具，需明确公式中 $h$ 的定义（根到叶子的最长路径长度）。
- 通过代入不同 $h$ 值，找到满足条件的最小 $h$。
步骤1：明确完全三叉树的节点数公式
完全三叉树的总节点数公式为：
$\text{节点数} = \frac{3^h - 1}{2}$
其中 $h$ 是树的高度。
步骤2：代入公式求解最小高度
题目要求总节点数为244，需找到最小的 $h$ 使得 $\frac{3^h - 1}{2} \geq 244$。
- 当 $h=5$ 时：
$\frac{3^5 - 1}{2} = \frac{243 - 1}{2} = 121 < 244$
不满足条件。 - 当 $h=6$ 时：
$\frac{3^6 - 1}{2} = \frac{729 - 1}{2} = 364 \geq 244$
满足条件。
结论：最小高度为 $h=6$。