我已经能够创建一个证明，显示树中的最大总节点数等于 n = 2^(h+1( - 1，从逻辑上讲，我知道二叉树的高度是log n(可以把它画出来看(，但我很难构建一个正式的证明来证明一棵有 n 片叶子的树"至少"有 log n。我遇到或能够组合在一起的每一个证明总是涉及完美的二叉树，但我需要一些东西来应对任何情况。有什么提示可以引导我走向正确的方向吗？
引理：高度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 + b0 < b <= 2^a的地方.现在，假设树的高度小于a + 1，这与我们打算证明的定理相反。那么高度最多是a.根据引理，高度a的树中的最大叶子数为2^a。但是我们的树有n = 2^a + b > 2^a叶子，自0 < b年以来;一个矛盾。因此，高度小于a+1的假设一定是不正确的。这证明了这一说法。