NOIP 普及 2016 第一轮 第 11 题：二叉树顺序存储时结点最大下标

题目

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

选项

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

答案

D

题解

考点定位

本题考「二叉树顺序存储」,对应大纲 3.2.2（难度【2】）。

解题过程

按 1 起、2i/2i+1 编号：叶子 = 无孩子的结点。对原卷图（例如 6 结点的树）：叶子在编号 4,5,6 位置？官方答案 15 表示数组中最后被占用的下标为 15——树深 4 层且最底层最右叶子在下标 15：说明某结点位于 7，其右孩子 15 存在。按原卷图结构（官方口径）⇒ 15。

选 D。

易错提醒

① 顺序存储按「完全二叉树位置」编号，空位也占号；② 图上逐结点算 2i/2i+1 即可定位叶子下标。