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

Question

我知道高度二叉树中的叶子数h最多为2^h，并且我也知道如何使用归纳法来证明这一点。我从这里去哪里？

我发现了这个先前回答的问题，但这对我来说没有任何意义，因为我不明白定理部分中的矛盾证明与二叉树的高度至少有什么关系log(n)。我原以为他会谈论log(n)与叶子数量和高度之间的关系，但他却继续谈论如何使用n = 2^a + b.

谁能帮我理解我们如何证明一个有 n 片叶子的 BT 的高度至少是 log n？

标签： binary-treeproof

Answer 1

考虑一棵二叉树，让它h的高度和n叶子的数量。

根据你的第一句话，n <= 2^h。在两边取一个以 2 为底的对数（因为对数是单调的，所以保持不等式），我们有log(n) <= h. 这立即给了你你想要的东西：高度至少是 ，叶子的数量log(n)在哪里。n