NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 7 题

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

别急着数图里画出来的空叉叉，那会数漏。抓住核心：二叉链表的空指针数只跟结点个数有关，跟树长什么样没关系。记住那个万能公式：空指针数等于结点数加一。

学生最容易犯的错就是盯着图看，数数图里画出来的空指针。比如根节点左孩子空、右孩子空，数了2个；第二层有的空了没数，有的没空数了，最后加起来可能数成6个或者12个。还有个坑是有人会想当然觉得空指针数等于叶子节点数之类的，完全跑偏。其实不管树怎么弯弯曲曲，只要结点总数是n，空指针就铁定是n+1个，这是二叉链表存储结构的固有性质。

这道题考查的是二叉链表存储结构中，空指针（NULL指针）的数目计算。这是一个非常经典且容易掉进陷阱的知识点，命题人特别喜欢挖“数数”这个坑，让你去图里一个个点数，结果往往数错。

首先，我们要把概念讲清楚。二叉链表里，每个结点都有两个指针域：一个指向左孩子，一个指向右孩子。所以，如果有n个结点，那么整个链表里一共有2n个指针域。这2n个指针域里，有多少是空的，有多少是连着其他结点的呢？

这里有个关键逻辑：每一个非空的指针，都代表了一条边，连接父结点和子结点。一棵树，如果有n个结点，那么它一定只有n-1条边（除了根结点，每个结点都有一条来自父结点的边）。这意味着，非空的指针域正好就是n-1个。

那么，空指针的数目自然就出来了：总指针域数减去非空指针数，也就是2n - (n-1) = n + 1。这个结论太重要了，它告诉我们：二叉链表中的空指针数目，只跟结点的总数有关，跟树的形状、深度、叶子节点数统统没关系！

回到题目，我们数一下图里的结点。根结点1个，第二层2个，第三层3个，一共是6个结点（n=6）。直接套公式，空指针数 = 6 + 1 = 7。

最后，避个坑。如果你去图里数，会发现根节点左右都空（2个），第二层有的空有的不空，第三层也有空的。很多人会数成6个或者12个，那是因为你被图骗了，去数具体的空叉叉。记住，不用数图，数结点个数加一就行。这道题答案选B。