求:含999个结点的完全二叉树的深度
发布网友
发布时间：2022-04-24 23:44
共1个回答
热心网友
时间：2023-10-15 01:04
k-1层满二叉树，其结点总数是：
2^0+2^1+...2^(k-1)=2^(k-1)-1
第k层至多有2*(k-1)个结点（k-1层每一个结点都有俩孩子的情况），
也就是说，
2^(k-1)-1
<
n
<=
2^k-1
或者：
2^(k-1)
<=
n
<
2^k
求以2为底的对数，即k=「log2n」+1
==========================
└log2n┘的意思，如果结果是整数，就是它自身，比如log2(8)=3，如果有小数，比如log2(10)=3.1，则取比3.1小的最大整数，即3。
由于2^10=1024,2^9=512,可以推测9<log2(999)<10,则
└log2n┘＝9.
