4

N个结点的完全二叉树的高度是多少？我正在寻找一个确切的答案，以及一个最低值或最高值。

4

4 回答 4

15

它是CEIL(log2(n+1))-1

  • 1 个节点给出 log2(2) = 1
  • 3 个节点给出 log2(4) = 2
  • 7 个节点给出 log2(8) = 3
  • 15 个节点给出 log2(16) = 4
    ...

编辑：根据维基百科，根节点（相当不直观？）不计入高度，因此公式为CEIL(log2(n+1))-1.

于 2013-07-28T18:55:17.427 回答
12

您不必执行 CEIL(log2(n+1))-1。

对于完整的二叉树，答案很简单：FLOOR(log2(n))

  • 1 个节点给出 0
  • 2 个节点给出 1
  • 3 个节点给出 1 个
  • 4 个节点给出 2 个
  • 5 个节点给出 2 个
  • 6 个节点给出 2 个
  • 7 个节点给出 2 个
  • 8 个节点给出 3 个
  • ...
  • 15 个节点给出 3 个
  • 16 个节点给出 4 个
  • ...
于 2015-11-17T06:27:21.860 回答
1

我想你可以使用 Joachim 提供的公式，或者简单地做 floor log(h) ......这是你可以为任何二叉树做的最好的情况......因此，如果你的树例如是满的，你将无法说这一定是真的......还要记住，在 CS 中你遇到的几乎所有日志都是以 2 为底的

于 2015-02-13T02:31:47.563 回答
0

N是节点数，h是完全二叉树的高度：
2**h <= N < 2**(h+1)
=> h <= ln2(N) < h + 1 //见楼wikipedia 中的定义
=> h = floor(ln2(N))

第一个不等式表示高度为 h 的完全二叉树的节点数优于高度为 (h - 1) 的完全二叉树的节点数这一事实) 并且同时低于高度为 h 加 1 的完整树的节点数。这是数学：
N_FULL_TREE(h - 1) = 1 + 2 + 4 + ... + 2** (h - 1) = 2**h - 1
N_FULL_TREE(h) = 1 + 2 + 4 +... + 2**h = 2**(h + 1) - 1
=> N_FULL_TREE(h - 1) < N_COMPLETE_TREE(h) <= N_FULL_TREE(h)
=> N_FULL_TREE(h - 1) + 1 <= N_COMPLETE_TREE(h) < N_FULL_TREE(h) + 1
=> 2**h - 1 + 1 <= N(h) < 2**(h + 1) - 1 + 1
=> 2**h <= N < 2**(h+1)

于 2018-12-16T22:41:17.130 回答