计算二叉树的深度 :
满二叉树的深度为k=log2(n+1)
在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。
计算完全二叉树深度公式-推导证明:
假设两种极端情况
<1>该树为满二叉树时,结点n1=2^k-1
此时k=log2(n1+1)
<2>当该树为满二叉树附加一个结点时,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