Question

数据结构中用二叉链表保存有n个结点的二叉树，则结点中有n+1个空指针域，问这个n+1是怎么出来的？

如题，问一下这个n+1是怎么出来的，我应该怎样理解这到题呢

Answer 1

n个结点的二叉树有n+1个空指针。
下面用数学归纳法证明。

证明：n=1时，1个结点的二叉树有2个空指针域，成立。
假设当n=k时成立，即k个结点的二叉树有k+1个空指针。
那么，放入第k+1个结点会占用一个空指针，然后又产生2个空指针
所以，k+1个结点有k+1-1+2=k+2个空指针，即当n=k+1时也成立。
所以假设成立。

Answer 2

因为n个节点有2n个指针
又因为n个节点中有n-1条边（除了头结点没有边，其余节点都有一个父节点，相当于都有1条边，共n-1条）
剩下的空链域就是2n-(n-1)=n+1，即n+1个空指针