完全二叉树的高度为什么是对lgN向下取整

完全二叉树的高度为什么是对lgN向下取整

完全二叉树的高度为什么是对lgN向下取整呢？

说明一下这里的高度：只有根节点的树高度是0。

设一棵完全二叉树节点个数为N，高度为h。

所以总节点个数N满足以下不等式：

1 + 21 + 22 +……+ 2h-1 < N <= 1 + 21 + 22 +……+ 2h 即 2h - 1 < N <= 2h+1 - 1，所以 2h < N+1 <= 2h+1，两边同取以2为底的对数得 h < log2(N+1) <= h+1。

---

若 N+1 = 2k ，此时完全二叉树为满二叉树，解上述不等式得 h < k <= h+1，所以 k-1 <= h < k，所以 h = k-1。

而 log2N = log2(2k -1)，又因为比 2k -1 小且离其最近的2的幂是 2k-1 ，

所以 log2N> log2(2k-1) = k-1，因此对 log2N 向下取整即为 k-1，即二叉树的高度等于对 log2N 向下取整。

---

若 N+1 不等于2的幂，设2k-1 < N+1 < 2k，所以 k-1 < log2(N+1) < k，所以 k-2 < h < k，所以 h = k-1。

设此时对应的满二叉树节点数为N0，所以 k-1 = 对log2N0向下取整，

h = k-1 也等于对log2N0向下取整。

因为 N > 2k-1 -1，即 N >= 2k-1，N0 <= 2k -1，所以对log2N0向下取整等于对 log2N 向下取整。

所以二叉树的高度等于对 log2N 向下取整。

---

证毕。