具有n个结点的完全二叉树的深度为log2n+1 证明过程是怎样的?

题目

具有n个结点的完全二叉树的深度为log2n+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）
）