Question

各位大侠帮我个忙，这个java题选啥？为什么？

设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，若采用二叉链表作为该二叉树的存储结构，则该二叉树的存储结构，则该二叉树中共有（）个空指针域。
A．N0+N1
B. N0+1
C. 2N0+N1
D. N0-1

Answer 1

首先要明确度数为0的是叶子节点，度数为1的是只有一侧子树。
因此，度数为0的每个节点都有两个空指针域用于表示没有左右子树，而度数为一的节点就必须有一个空指针域表示某一侧没有子树。
因此总的空指针域就是2N0+N1

Answer 2

2N0+N1