induction - 通过归纳证明每个高度为 h 的非空树包含少于 2^n+1 个节点

Question

我被困在一个问题的归纳案例上。

问题：

将树的高度定义为根与任何叶子之间的最大边数。我们认为一棵空树的高度为 -1，由单个节点组成的树的高度为 0。通过归纳证明每个高度为 h 的非空二叉树包含少于 2 ^(h+1)节点。

So I started:

Base case: h = 0 (Since a non-empty tree consists of a single node 
or 
more, the first case would be an empty node)

= 2 ⁽⁰⁺¹⁾ = 2 ⁽¹⁾ = 2 当高度为 0 时，树由单个节点组成，所以是的，1 个节点小于 2 个节点。归纳步长 = h 小于或大于 0 这就是我卡住的地方...我知道这句话是正确的，因为高度总是比节点数小 1，我只是不知道如何证明它代数。

提前致谢。

Answer 1

假设你有一棵树，高度为 n+1。

它的左子树和右子树的高度都以 n 为界。通过归纳，每个子树有少于 2^(n+1) 个节点，这意味着最多 2^(n+1) - 1 个节点。

由于我们有两个子树，我们最多有 2 * (2^(n+1) - 1 ) = 2^(n+2) - 2。为根添加一个，高度为 n+1 的树有最多 2^(n+2) - 1，根据需要小于 2^(n+2)。