logic - 证明具有n个叶子的二叉树的高度至少为log n

Question

我已经能够创建一个证明，证明一棵树中的最大节点总数等于n = 2 ^(h + 1)-1，从逻辑上讲，我知道二叉树的高度为log n(可以画出它)但我无法构造正式的证据来证明一棵有n个叶子的树的高度至少为log n。我遇到或能够组合在一起的每一个证明总是可以处理完美的二叉树，但是在任何情况下我都需要一些东西。有什么提示可以引导我朝正确的方向发展吗？

Answer 1

引理:高度为h的树中的叶子数不超过2^h。

证明:证明是通过对h进行归纳得出的。

基本情况:对于h = 0，树仅包含一个根节点，该根节点也是一个叶；在这里，n = 1 = 2^0 = 2^h，根据需要。

归纳假设:假定所有k或以下高度的树的叶子少于2^k的树。

归纳步骤:我们必须证明k+1高度的树的叶子不超过2^(k+1)的叶子。考虑根的左和右子树。这些树的高度不超过k，小于整个树的高度一棵。因此，根据归纳假设，每个最多有2^k叶。由于叶子的总数仅是根的子树的叶子总数的总和，因此我们根据需要设置了n = 2^k + 2^k = 2^(k+1)。这证明了要求。

定理:具有n叶子的二叉树的高度至少为log(n)。

在引理中我们已经注意到，仅由根节点组成的树具有一个叶，高度为零，因此在这种情况下该主张是正确的。对于具有更多节点的树，证明是矛盾的。

让n = 2^a + b为0 < b <= 2^a。现在，假设树的高度小于a + 1，这与我们打算证明的定理相反。然后，高度最大为a。通过引理，高度为a的树中的最大叶子数为2^a。但是我们的树有n = 2^a + b > 2^a树叶，因为0 < b;矛盾。因此，高度小于a+1的假设一定是不正确的。这证明了要求。