关于 具有n个结点的完全二叉树的深度为「log2n」+1的证明

Answer 1

可用数学归纳法。
当n=1=2^1-1时显然。
假设当n<=2^k-1时具有n个结点的完全二叉树的深度为「log2n」+1，则
当n=2^k（以及2^k+1,...,2^(k+1)-1）时，由归纳假设知前2^k-1个结点构成深度为「log2n」+1的树，再由完全二叉树的定义知剩余的1（或2,...,2^k)个结点均填在第「log2n」+2层上（作为“叶子”），故深度刚好增加了1。
故n<=2^(k+1)-1时命题成立。证毕。
（首先最好能先从直观上理解：完全二叉树中：
第1层有1个结点；
第2层有2个结点；
第3层有4个结点；
……
第k层有2^(k-1)个结点；（前k层共有(2^k)-1个结点，故前面深度刚好是「log2（2^k-1)」+1=k-1+1=k）
第k+1层是剩余的结点。 ）