Question

用二叉链表存储包含N个结点的二叉树，结点的2N个指针域中有N+1个空指针

求详解

Answer 1

首先
二叉树的节点都有2个指针。每个节点有0个、1个或2个空指针。对应的有2个、1个、0个非空指针。非空指针的总数就是二叉树的边的个数。
设一个二叉树x个节点含有0个空指针，y个节点有1个空指针，z个节点有2个空指针
有如下等式
1、 x+y+z=N 节点总数为N，题目叙述
2、 y+2*z=N+1空指针个数为N+1，题目叙述
3、 2*x+y= N-1 二叉树的边数。树的边数=树的节点数-1
解以上方程组就可得出树的几种类型的节点数了。你就可以构造这个二叉树了。如果方程组有解
一般可以构造的二叉树是很多的。

Answer 2

除根节点外，每个节点都有且仅有一个射向自己的分支（在二叉链表中即为指针），所以N个节点的二叉树，需要N-1个指针域，空余N+1个

Answer 3

还是 假定有三个结点 头结点和两个子节点， 头结点 的两个指针域为左右结点的地址 而左节点的左右指针域都为NULL， 这就是有两个了， 在就是右结点的左右指针域也为NULL， 所以 现在一共有 三个结点 六个指针域，和 两个非空指针域，最后还有四个空指针，符合 2N个结点有N+1个空指针...

希望您能明白。

Answer 4

将空指针看做叶子节点，则树中原有的所有节点都成了双分支节点。