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

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

假设完全二叉树深度为k，则第k层至多有2^(k -1)个结点。最少是2^(k -2) +1(这里k>1)
那么深度为k的完全二叉树 结点总数最多有 1 + 2 + 4 + ... + 2^(k -1) = 2^k - 1
深度为k的完全二叉树结点总数关系式是： 2^(k-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） ）