CSP-S 2021 第一轮 第8题：令根结点的高度为1，则一棵含有2021个结点的二叉树的高度至少为（）。

题目

令根结点的高度为 $1$，则一棵含有 $2021$ 个结点的二叉树的高度至少为（ ）。

选项

• A. 10
• B. 11
• C. 12
• D. 2021

答案

B

题解

答案是 B. 11。

二叉树每个结点最多有两个子结点，因此第 \(i\) 层最多有 \(2^{i-1}\) 个结点。高度为 \(h\) 时，最多有 \[ 1+2+4+\cdots+2^{h-1}=2^h-1 \] 个结点。

比较可得：

• 高度为 \(10\)：最多 \(2^{10}-1=1023\) 个，不够。
• 高度为 \(11\)：最多 \(2^{11}-1=2047\) 个，可以容纳 \(2021\) 个。

所以高度至少为 \(11\)。