NOIP 提高 2016 第一轮 第 7 题：一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩

题目

一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（   ）。

选项

• A. 6
• B. 7
• C. 12
• D. 14

答案

B

题解

考点定位

本题考「二叉链表空指针」,对应大纲 3.2.2 二叉树（难度【2】）。

解题过程

n 结点二叉链表共 2n 个孩子指针，用掉 n−1 条（除根都有父）⇒ 空指针 = 2n−(n−1) = n+1。按原卷图 n=6 ⇒ 7 个空指针。

选 B。

易错提醒

① 公式：空指针数 = n+1（二叉链表恒成立）；② 与图的具体形态无关。