2回答

liuyubobobo

2019-08-31

已采纳

这是一个粗略的计算，关键是绿色部分等于红色+蓝色。

如果对具体的空间大小感兴趣，可以参考这个问答：https://coding.imooc.com/learn/questiondetail/58660.html

继续加油！：）

0

1

IT_god

谢谢！

2019-08-31

共1条回复

何时才能成大佬

2019-10-06

/*

* 对于满二叉树（设根节点所在的层为第1层）来说

* 第i层有 2^(i-1)个元素

* 前i层共有 2^i-1个元素

* 前i-1层共有 2^(i-1)-1个元素

* 故：第i层的元素个数=前i-1层共有的元素个数+1

* 

*假设区间里有n个元素

* 第一种情况：n=2^k (k是正整数)

* 此时开辟的满二叉树的空间大小为：n+(n-1)=2n-1

* 

*第二种情况：n≠2^k (k是正整数)

*此时假设2^p < n < 2^q  且q=p+1  (p、q都是正整数)

*此时开辟的满二叉树的空间大小为： 2^q+2^p+(2^p-1) =2^(p+1)+2^p+2^p-1

* =(2^p)*2+2^p+2^p-1

* <n*2+n+n-1

* =4n-1

* 

* 

* 因为2n-1 < 4n-1

* 所以对于n个元素,需要开辟4n-1个空间

* */

2

0