完全二叉树的高度

结点个数为 N 的完全二叉树的深度（高度）h(N) 等于 ?lgN?。

N=1 时，命题成立。

假设命题在 N=m 时成立，即 h(m)=?lgm?，则当 N=m+1 时：

设 N=m 时的完全二叉树的高度 h(m)=?lgm?=k。则有 2^k-1

• 当 m+1<=2^{k+2}，有 h(m+1)=h(m)=?lgm?，而 lg(2^{k+1}-1)
• 当 m+1=2^{k+1}，h(m+1)=h(m)+1=?lgm?+1=k+1=?lg(m+1)?。命题成立。

由数学归纳法，上述命题总成立。

另外一些讨论