computer-science - 高度为 n 的归纳二叉树证明有 2^(n+1)-1 个节点

Question

有人将如何通过归纳来证明高度为 n 的二叉树有 2^(n+1)-1 个节点？

Answer 1

首先，我有数学学士学位，所以这是对如何通过归纳进行证明的一般描述。

首先，证明如果 n = 1 则有 m 个节点，如果 n = 2 则有 k 个节点。由此确定在 n = 1 和 2 时有效的 m, k 公式（即在您的情况下为 2^(n+1) - 1。

接下来，假设相同的公式适用于 n 作为任意值。最后，证明该公式适用于 (n+1) 的高度。即 n 意味着 n+1（单步增量）。这最后一步通常是最困难的，但如有必要，您可以使用 n、1 和 2 的结果。

这个想法是，您可以看到对于 n = 1 和 2，当 n 增加 1 时，该公式有效。然后，如果 n 为真，则通过证明 n+1 为真，勤奋的人可以明确计算n = 1、2，然后是 3、4，等等。所有到 n，然后到 n+1，以单步递增。