c-一个有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。

对于一个完整的二叉树，答案很简单：楼层（log2（n））

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

Answer 3

我想你可以使用Joachim提供的公式，或者简单地做地板原木（h）。。。这是你能为任何二叉树做的最好的情况。。。因此，如果你的树是满的，你就不能说这一定是真的。。。还要记住，在CS中，您遇到的几乎每个日志都是基于2的

Answer 4

N是节点数，h是完整二叉树的高度：
2**h<=N<2**（h+1）
=>h<=ln2（N）<h+1//请参阅维基百科中的楼层定义
=>h=楼层（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）