algorithm - 二叉树的实现

Question

以下文字摘自算法书。

我们可以使用链表惯用的矩形框来绘制二叉树，但树通常被绘制为由线连接的圆圈，因为它们实际上是图。在引用树时，我们也没有显式绘制 NULL 链接，因为每个具有 N 个节点的二叉树都需要 N+1 个 NULL 链接。

我的问题是作者的意思是什么意思是每个具有 N 个节点的二叉树都需要 N+1 个空链接？作者是如何获得 N+1 号的？

Answer 1

如果您有 1 个节点的树，则有 2 个空链接（根节点的左侧和右侧）。如果你在左边或右边添加一个节点，你已经填充了 1 个 null 并添加了 2 个。这将无限期地继续下去，因此对于每个节点，您都添加了 1 个额外的空叶。

Answer 2

你可以用数学归纳法证明这一点。

基本情况

1 个节点有 2 个 NULL 链接 - 满足该属性。

感应步骤

现在假设所有具有 n-1 个节点的树都有 n 个 NULL 链接。然后我们希望表明，所有具有 n 个节点的树都有 n+1 个 NULL 链接。

取任何具有 n 个节点的树，并选择其中一个叶子。去掉这片叶子。根据我们的假设，我们现在有一个具有 n 个 NULL 链接的树。如果我们再次添加叶子，我们会失去一个 NULL 链接，但会获得两个。因此，我们在具有 n 个节点的树上有 n - 1 + 2 = n+1 NULL 链接。

Answer 3

观察：每条边都充当链接。N 个节点的 N-1 条边。

完全链接：2N。

空链接：2N - (N-1) = N+1。