CSP-J 2023 第一轮 第 5 题：2023 个节点的三叉树最小高度

题目

根节点的高度为 $1$，一棵拥有 $2023$个节点的三叉树高度至少为（）。

选项

• A. 6
• B. 7
• C. 8
• D. 9

答案

C

题解

选 C，8。

要让树的高度尽量小，就要让每层尽可能多地放节点。三叉树的每个节点最多有 3 个子节点，所以：

• 第 1 层最多有 \(1\) 个节点；
• 第 2 层最多有 \(3\) 个节点；
• 第 \(h\) 层最多有 \(3^{h-1}\) 个节点。

因此，高度为 \(h\) 的三叉树，最多有 \[ 1+3+3^2+\cdots+3^{h-1}=\frac{3^h-1}{2} \] 个节点。

比较可得： \[ h=7:\quad \frac{3^7-1}{2}=1093<2023， \] \[ h=8:\quad \frac{3^8-1}{2}=3280\ge2023。 \]

7 层放不下，8 层可以放下，所以最小高度为 8。