基于向量的二叉树空间最坏情况疑问：2ⁿ-1是否应为2ʰ-1？

你完全正确，《Data Structures and Algorithmn in C++ 2nd Ed》中此处的表述存在笔误，最坏情况空间占用的正确表述应为2ʰ - 1（h为树的高度），而非2ⁿ - 1（n为节点总数），具体解析如下：

核心原理回顾 #

这种实现通过层序编号映射节点到向量：

• 根节点编号为1
• 任意节点u的左子节点编号为2*u，右子节点为2*u+1
• 向量大小由最大节点编号fM决定，为fM + 1（因向量索引从0开始，需覆盖到编号fM的位置）

最坏情况空间的正确推导 #

最坏情况对应斜树结构（所有节点仅存在左孩子或右孩子）：

• 当树有n个节点时，斜树的高度h = n
• 第h层的节点编号为2^(h-1)，此时向量需分配2^(h-1) + 1的空间，量级为O(2^h)
• 若以满二叉树为例（高度h的满二叉树节点数n = 2^h - 1），此时最大节点编号恰好是2^h - 1，向量大小为2^h，和2^h - 1属于同一量级——这也是书中表述混淆的根源：把满二叉树的节点数（2^h - 1）错写成了基于节点数n的2^n - 1

实例验证 #

以15节点的满二叉树为例：

• 树的高度h = 4（因为2^4 - 1 = 15）
• 最大节点编号为15，向量大小为16，对应空间占用量级为2^h，和2^h - 1（15）匹配
• 若按书中错误表述2^n - 1计算，得到32767，完全不符合实际空间需求，进一步证明了笔误的存在

内容的提问来源于stack exchange，提问作者yapkm01