求:含999个结点的完全二叉树的深度
发布网友
发布时间:2022-04-24 23:44
我来回答
共1个回答
热心网友
时间:2023-10-15 01:04
k层完全二叉树,其k-1层是满二叉树,
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.