具有N个节点的完整二叉树的高度是多少？

Question

具有N个节点的完整二叉树的高度是多少？我正在寻找一个确切的答案,无论是楼层还是天花板价值.

Answer 1

它的 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.

Answer 2

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

对于COMPLETE二叉树,答案很简单:FLOOR(log2(n))

• 1个节点给出0
• 2个节点给出1
• 3个节点给出1
• 4个节点给出2
• 5个节点给出2
• 6个节点给出2
• 7个节点给出2
• 8个节点给出3
• ...
• 15个节点给出3
• 16个节点给出4个
• ...