一棵有n个结点的二叉树采用二叉链存储结点，其中空指针数为（ ）。

A. n B. n+1 C. n−1 D. 2n

[tag_link]

correct answer: B

结论

二叉链共有2n个指针域，非空边n−1，空指针为2n−(n−1)=n+1。

推导

二叉链共有2n个指针域，非空边n−1，空指针为2n−(n−1)=n+1。

易错点

空指针数不是n−1，后者是非空边数。