具有n个结点的平衡二叉树的深度一定不小于log2n

2024-11-30 12:28:55
推荐回答(1个)
回答1:

深度为k的二叉树的节点总数最多为1+2+4+..+2^(k-1)=2^k-1
则设n个节点的二叉树深度为m,2^m-1>=n
m>=log2(n+1)>log(2n),由于m是整数
m>=[log2n]+1,