我已经能够创建一个证明，显示树中的最大总节点数等于 n = 2^(h+1) - 1 并且从逻辑上我知道二叉树的高度是 log n （可以绘制它出来看看）但我很难构建一个正式的证明来证明一棵有 n 片叶子的树“至少”有 log n 。我遇到或能够组合在一起的每个证明都涉及完美的二叉树，但我需要适合任何情况的东西。有什么建议可以引导我走向正确的方向吗？
Lemma：一棵树高度的叶子数量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)， 按要求。这证明了这一说法。
Theorem：二叉树n叶子至少有高度log(n).
我们已经在引理中注意到，仅由根节点组成的树有一个叶子且高度为零，因此在这种情况下该声明是正确的。对于具有更多节点的树，可以通过反证法来证明。
Let n = 2^a + b where 0 < b <= 2^a。现在，假设树的高度小于a + 1，与我们想要证明的定理相反。那么高度最多为a。根据引理，一棵树的最大叶子数a is 2^a。但我们的树有n = 2^a + b > 2^a离开，因为0 < b;矛盾。因此，假设高度小于a+1一定是不正确的。这证明了这一说法。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
