假设我们有一个长度为 n=7 的数组，树的高度应为 2。我不会通过行数来计算高度，而是通过它们之间的连接来计算高度。
(我认为因为在堆排序算法中，Siftdown 方法表示最后一行可以移动 0 的高度，而之前的行可以移动 1 的高度，所以树中的 2 行将允许高度 1 移动。)
因此，为了获得高度，我将计算 log2(allNodesInTheBottomRow)，即 (n+1)/2。
log2((n+1)/2)正确吗？
这里是一个例子:
最佳答案
一般来说，二叉树的高度O(log n)是不正确的。请注意，在下图中，这两棵树都是有效的二叉树:
请注意，右侧的树满足右子节点大于根的属性，并且本身就是二叉树的根。
我认为你的意思是平衡二叉树的高度O(log n)。请注意，平衡二叉树的规范定义是给定元素集上的二叉树，其中高度最小(或者在许多情况下，接近最小 - 一个常数因子)。很容易直观地观察到，当每行完全饱和时(即树完整或几乎完整)，就会发生这种情况。
请注意，当树完全饱和时，第一行有 1 元素，第二行有 2 元素，第 ith< 元素行有 2^(i-1) 元素。因此，如果有 n 个元素，则 n = 2^(log n)。这意味着需要有 O(log n) 行。
如果您正在寻找一个精确的函数来计算高度，而不仅仅是一个 O(log n) 界限，您只需将 n 向上舍入到最接近的幂2 然后计算其对数。例如，如果 n=7，则 2 最接近的幂为 8，且 log(8) = 3如所须。您可以根据您对高度的定义在末尾减去 1。
关于algorithm - 是二叉树的高度log2(n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62174984/