NOIP 普及 2010 第一轮 第 5 题：n 层二叉树的最大结点数

题目

如果树根算第 $1$ 层，那么一棵 $n$ 层的二叉树最多有（   ）个结点。

选项

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

答案

A

题解

考点定位

本题考「二叉树结点数上界」,对应大纲 3.2.2 二叉树（难度【1】）。

解题过程

n 层二叉树每层最多 2ⁱ⁻¹ 个，总数：

$$1+2+4+\cdots+2^{n-1}=2^n-1$$

选 A。

易错提醒

① 等比数列求和公式：2ⁿ−1；② 对照：完全二叉树 n 层至少 2ⁿ⁻¹ 个结点。