> 其他 >
证明具有n个结点的二叉树,其深度至少为[log2n]+1,
人气:133 ℃ 时间:2020-08-31 12:29:46
解答
深度为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,
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版