【题目】

一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为 \(i\) ，则其左孩子位于下标 \(2i\) 处、右孩子位于下标 \(2i+l\) 处），则该数组的最大下标至少为（）。

     o
    / \
   o   o
      / \
     o   o
        / \
       o   o

A. 6
B. 10
C. 15
D. 12

【考点】

二叉树（重点）

高度

结点数量

叶子节点数量

下一层数量是上一层的2倍

每层的数量：\(2(i−1)\)

总数量：\(2^i−1\)

完美二叉树（满二叉树）

完全二叉树：完美二叉树从右往左去掉一些叶子结点

【解析（2）】

堆式编号。

最大值是最深的那层最靠右侧的节点。

总共4层，从题目中给定的算式：

第1层：根节点，根结点的下标为1
第2层：右孩子位于下标 \(2i+l\) ，即 \((1*2+1)\)
第3层：右孩子位于下标 \(2i+l\) ，即 \([(1*2+1)*2+1]\)
第4层：右孩子位于下标 \(2i+l\) ，即 \(\{[(1*2+1)*2+1]*2+1\}\)

\(ans=\{[(1*2+1)*2+1]*2+1\}=15\)

【解析（2）】

\(ans=2^4−1=15\)