题目

对于任意一棵高度为 且有 个结点的二叉树，若采用顺序存储结构保存，每个结点占 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是( )。

错因

B

误把 当成答案。可能是把"高度 "算成 个位置，少算了一层；或者把"高度"和"层数"理解成了不同的东西。要点：高度为 的二叉树最大编号是 ，不是 。

C

算出 ，本质是把高度 当成 来算（少了一层）。可能因为把"高度"定义成了"边数"而不是"层数"——但 408 教材里"高度"就是层数，根所在层为 ，所以高度 的二叉树最深可以到第 层，最大编号 。

D

直接拿结点数 当存储单元数。错在没理解顺序存储的核心机制：顺序存储是按完全二叉树的层序编号给每个结点分配位置——树里实际有 个结点不重要，关键是这 个结点在树中的编号最大可以到多少。

总解析

核心机制：二叉树顺序存储是把树"按完全二叉树层序编号"嵌入数组——根编号为 ，编号为 的结点其左孩子编号 、右孩子编号 。即使中间有空缺位置，也要在数组里留出来。

"任意"的含义：题目说"对于任意一棵高度为 且有 个结点的二叉树"，意思是要保证能存下所有可能的形态（共 个结点的二叉树有许多种形态），所以要按最坏情况预留空间。

最坏情况：单分支链。

考虑一棵每层只有一个结点、且最右下角有一支的二叉树（即从根开始一直右斜下去，外加几个其他位置的孤立结点）：

层	1	2	3	4	5
最右下角结点的编号	1	3	7	15	31

如果某棵高度 的二叉树存在第 层最右位置上的结点，它的编号就是 ，那么数组至少要有 个单元才能放下它。

为什么不能更小？ 比如考虑右单链 （5 层全靠最右），五个结点的编号依次是 ，再加上 5 个其他位置的结点，凑成 10 个。这棵树合法且高度为 ，但第 5 层第 31 号位置必须存在——所以无论你怎么存，至少要 个单元。

最大编号 。

最终答案是 A（31）。

顺序存储的本质：用空间（编号占位）换取通过下标算父子关系的便利。它并不省空间，对于稀疏树（如本题）反而非常浪费——这也是顺序存储一般只用于完全二叉树的原因。