满二叉树的高度

Question

如何求解包含 n 个节点的满二叉树的高度？

n=2^(h+1)-1

我得到的答案是，

             n = 2^(h+1)-1
n+(-2^(h+1)+1) = 2^(h+1)-1 + (-2^(h+1)+1)
   n-2^(h+1)+1 = 0
             h = ln(n+2)/ln(2)

这个方程求解对吗？如果不是，如何从 n = 2^(h+1)-1 方程得到 h？

Answer 1

我们使用 "Complete" 表示完整二叉树，因此它被称为完全二叉树而不是完整二叉树。
下面是h的推导公式n=2^(h+1)-1
```
    n = 2^(h+1)-1

    n + 1 = 2^(h+1)
```

两边取对数底数 2 (ln2)

        ln2(n+1) = ln2(2^(h+1))

        ln2(n+1) = h+1

        ln2(n+1) - 1 = h

或

        h = ln2(n+1) - 1

希望你做对了。宾果。

另外我觉得你对对数的性质不是很熟悉。我将在这里为您解释。 ln2(8) 被读取为 log 8 base 2。 ln2(8) 答案 3. 它是如何计算的？ 2^3 的答案是什么？是 8。所以我们可以说获取日志与获取权力相反。我们可以回答简单的日志问题，例如 ln3(9) = ? , as 3^2 = 9 所以 ln3(9) 结果 2. 另一个例子 ln10(100) = ?, 我们知道 10^2 = 100, 所以 ln10(100) = 2. 你需要知道对数的属性才能excelling在数据结构和算法的过程中。它有很大帮助。

Answer 2

对于二叉树，高度由 log2(n) 给出。

满二叉树的高度

Height of a full binary tree

height

binary-tree

nodes

equation-solving