在完全二叉树中，具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 满二叉树的深度为k=log2(n+1)
证明：
假设两种极端情况
- 该树为满二叉树时，结点n1=2^k-1
此时k=log2(n1+1)
- 当该树为满二叉树附加一个结点时，n2=2^(k-1),此时k=log2n2 +1,
并且log2(n1+1)=log2n2 +1
对任意结点n的完全二叉树，n2<=n<=n1
2^(k-1)<=n<=2^k -1
log2(n+1)<=k<=log2n +1
则k向下取整log2n +1
版权声明：本文为sinat_27602945原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。