CSP-J 入门级 · CSP 2019 入门级第一轮 第 8 题

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

这题考二叉树顺序存储的下标规律。拿到图别数节点，要顺着最右那条线往下找，算出最底下那个节点的编号，那才是数组最大下标。

学生最容易把最大下标当成节点总数，数数一共几个圈就选哪个，这是大错特错，因为顺序存储中间有空位。还有人会误以为根是0号，或者只盯着最左边的叶子看，忽略了顺序存储是严格按编号排布的，编号最大的那个位置才决定数组长度。

考点与概念：本题核心是二叉树顺序存储的下标映射规则——根节点下标为1，若节点下标为i，则其左孩子下标为2i，右孩子下标为2i+1。顺序存储的本质是“编号即位置”，不管有没有孩子，编号必须连续占位，所以有缺失节点时，数组长度远大于实际节点数。命题人常在此挖坑：让学生数节点总数或只看最左路径，从而误选较小下标。思考心法是“追最右”：从根出发，只要当前节点有右孩子，就一路往右走；若没有右孩子但有左孩子，则往左走；若既无左也无右，就停下。最终停下的那个节点的编号，就是顺序存储数组所需的最大下标。避坑提醒：下标从1开始（不是0），中间空缺也要预留位置，深度为h的二叉树最坏需要2^h-1个下标。考频趋势：二叉树基础是高频考点，题库共考过220题，覆盖8个考试级别；逐年分布显示2023年20题、2024年60题、2025年67题，近年热度持续攀升；分赛事看，GESP六级100题、七级56题、八级19题，NOIP普及组初赛14题、提高组初赛9题，CSP入门级8题、提高级8题，可见顺序存储与编号规则在各级别均被反复考查。预测：基于2024-2025年数据，此类题目未来仍会高频出现，命题人可能继续用“最右路径编号”作为陷阱，或结合层序遍历、数组大小计算综合考查，暂无足够依据预测具体变式。综上，正确思路是沿最右路径找到编号最大的节点，该编号即为数组最大下标，故本题选C。