CSP-J 2019 第一轮 第 8 题：二叉树顺序存储的最大下标

题目

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

选项

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

答案

C

题解

答案是 C．15。

按题目规则，从根结点开始编号：左孩子的下标是父结点的 2 倍，右孩子是父结点的 2 倍加 1。

图中各结点的下标为：

``text 1 / \ 2 3 / \ 6 7 \ 15 ``

最下方的结点是下标为 \(7\) 的结点的右孩子，所以下标为 \[ 2\times 7+1=15。 \]

因此，数组的最大下标至少为 15。注意：虽然只有 6 个结点，但顺序存储中空缺的位置也要保留，不能把结点紧挨着编号。