问题及解答

Hint: 用归纳法证明.

回忆:

一个二叉树的任意一个结点最多有两个 childs, 所以可以使用 双向链表 的结构直接链接 childs.

struct BinaryNode
{
	Object	element;	// The data in the node
	BinaryNode	*left;	// Left child
	BinaryNode	*right;	//right child
}

记 $m$ 为 NULL 链的个数.

• 当 $N=1$ 时, 只有一个根结点, 从而有两个 NULL 链, 满足 $m=2=N+1$.
• 当 $N=2$ 时, 树的结构在同构意义下只有一种, 即根结点加一个 child. 从而有三个 NULL 链, 满足 $m=3=N+1$.

假设命题对 $N=k$ 成立, 即此时有 $m=k+1$ 个 NULL 链.

现在考虑 $N=k+1$ 个结点的二叉树. 我们注意到, 任何一个 $k+1$ 个结点的二叉树都可以用某个 $k$ 个结点的二叉树再添上一个叶子结点得到.

于是, 添加上的叶子结点替代了原先 $k$-结点二叉树的某个 NULL 链, 但添上以后又多出两个 NULL 链, 因此最终多了一个 NULL 链. 即对于 $N=k+1$ 个结点的二叉树, 有 $m=k+2$ 个 NULL 链.