证明具有 n 个叶子的二叉树的高度至少为 log n
Prove that a binary tree with n leaves has a height of at least log n
我知道一棵高度为h的二叉树的叶子数最多可以是2^h，我也知道如何用归纳法证明这一点。我从这里去哪里？
我找到了 this 之前回答的问题，但这对我来说没有任何意义，因为我不明白定理部分的反证法与二叉树的高度有什么关系至少 log(n)。我原以为他会谈论 log(n) 如何与叶子的数量和高度相关，但他却继续谈论如何使用 n = 2^a + b.
通过反证法进行证明
谁能帮我理解我们如何证明有 n 个叶子的 BT 的高度至少为 log n？
考虑一棵二叉树，让 h 是它的高度，n 是它的叶子数。
根据你的第一句话，n <= 2^h。在两边取一个以 2 为底的对数（这保留了不等式，因为对数是单调的），我们有 log(n) <= h。这立即给了你你想要的：高度至少是 log(n)，其中 n 是叶子的数量。
所以你知道你的二叉树具有以下属性：
n <= 2^h
现在你可以在两边都使用对数，因为它们都是正的，从数学的角度来看就是这样。
为了更好地理解它，您可以执行以下操作：
如果你有一棵未满的树，你可以用 2 个可能的叶子换取一个实际的叶子（因为可能有 2 children）。因此，任何给定高度的最大叶子数是一棵完整的树，它有 2^h 个叶子或 log (n) 高度。
我知道一棵高度为h的二叉树的叶子数最多可以是2^h，我也知道如何用归纳法证明这一点。我从这里去哪里？
我找到了 this 之前回答的问题，但这对我来说没有任何意义，因为我不明白定理部分的反证法与二叉树的高度有什么关系至少 log(n)。我原以为他会谈论 log(n) 如何与叶子的数量和高度相关，但他却继续谈论如何使用 n = 2^a + b.
谁能帮我理解我们如何证明有 n 个叶子的 BT 的高度至少为 log n？
考虑一棵二叉树，让 h 是它的高度，n 是它的叶子数。
根据你的第一句话，n <= 2^h。在两边取一个以 2 为底的对数（这保留了不等式，因为对数是单调的），我们有 log(n) <= h。这立即给了你你想要的：高度至少是 log(n)，其中 n 是叶子的数量。
所以你知道你的二叉树具有以下属性：
n <= 2^h
现在你可以在两边都使用对数，因为它们都是正的，从数学的角度来看就是这样。
为了更好地理解它，您可以执行以下操作： 如果你有一棵未满的树，你可以用 2 个可能的叶子换取一个实际的叶子（因为可能有 2 children）。因此，任何给定高度的最大叶子数是一棵完整的树，它有 2^h 个叶子或 log (n) 高度。