NOIP 普及组初赛 · NOIP 2016 普及组初赛试题 第 11 题

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

这题就是考顺序存储的编号规则。拿到图先别急着数个数，直接按'根是1，左乘2，右乘2+1'往下推，哪一层最右下那个节点算出来是几，答案就是几。

最容易掉进两个坑：一是把'顺序存储'当成'按实际节点数连续编号'，以为只要数出树里只有12个节点就选12，完全忽略了空位也要占下标；二是看图看走眼，把某个缺失的左孩子当成存在，或者把最右下的节点看成了3层的节点。记住，顺序存储的编号是固定的，跟树里有没有节点没关系，位置到了编号就必须有。

这道题考查的是二叉树的顺序存储结构，核心规则就三条：根节点下标为1；若某节点下标为i，则其左孩子下标为2i，右孩子下标为2i+1。命题人最喜欢挖的坑就是让学生误以为顺序存储是'紧凑'的，看到图里只有12个节点就机械地选12，或者把编号当成'实际节点数+1'来算。其实顺序存储的本质是'按完全二叉树的位置预占'，哪怕某个位置是空的，它的下标也是存在的，只是没有存数据而已。所以解题心法是：拿到图先别数节点，直接按规则从根往下推导，哪一层最右下那个节点算出来是几，答案就是几。具体到本题，我们逐层推：第一层根是1；第二层左2、右3；第三层左4、5、6、7；第四层从8开始，依次是8（1的左左）、9（1的左右）、10（2的左左）、11（2的左右）、12（3的左左）、13（3的左右）、14（4的左左）、15（4的左右）。图中最右下的节点正好落在第四层第7个位置，也就是下标15。验证一下：如果是满的4层完全二叉树，第4层确实有8个节点，编号8~15，最大就是15，跟选项D吻合。这里要特别提醒，很多同学会纠结'图里是不是真的画了15个节点'，其实顺序存储不关心图里画没画，只关心'如果这棵树补成完全二叉树，最右下那个位置编号是多少'。所以哪怕图里缺了左孩子，只要右孩子在，它的编号依然按2i+1算。这就是顺序存储的'刚性'：位置决定编号，编号决定位置，中间不能有空档。