数据结构 树 空链域

Question

空链域 这个概念是什么意思？
书上有句话说对一个二叉树来说，含有n个结点的二叉链表中有n+1个空链域到底指什么呢？？？？？

Answer 1

很简单，因为每一个节点有左右两个指针，n个节点共有2n个链域，
而n个节点只需用n-1个指针就可互连（因为连接n个点只需n-1条直线），
所以还剩下2n-(n-1)=n+1个。

Answer 2

一共n个节点，除头节点没有前驱剩下的每一个节点都有前驱，有一个前驱就会占据一个指针域，即用掉n-1个指针域，剩下的n+1个指针域就空了下了没有被利用。