全部问题 > 当前问题

满二叉树的求法2的n次方减一怎么来的


王新 2016-1-22 15:57:06

共 4 个回答

王新 2016-1-22 15:57:27

主要是数列没学好,忘记了

费腾 2016-1-22 16:00:52

满二叉树 1 2 4 8好像是这样排的吧,就是等比的求和公式 Sn=a1(1-q^n)/(1-q)  =1*(1-2^n)除以(1-2)=(1-2^n)的负数或者或相反数,也就是2^n-1

zy 2016-1-22 16:03:18

根据等比数列求和公式,q是2,a1=1

360截图20160122155905491.jpg

最佳答案

青栀如初 2016-1-22 16:09:40

  新新同学,你好:

  

完全二叉树看是几层的,比如3层完全二叉树,就有7个结点,结点总数是(2的3次方)减1个;叶子结点数是2的(3减1次方)个,就是4个。

如果是n层完全二叉树,结点总数是(2的n次方)减1个;叶子结点数是2的(n减1次方)个;会了就非常简单。

完全二叉树的第N层,都会是2的N-1次幂个结点,而上一层,则是N-2次幂个结点,所以总节点数应该是2N次幂减1,700不是一个这样的数,所以不会有700个结点。

如果是

两层,那应该是4-1=3个结点,

三层,是8-1=7个结点

四层,是16-1=15个结点

五层,是32-1=31个结点

六层,是64-1=63个结点

七层,是128-1=127个结点

八层,是256-1=255个结点

九层,是512-1=511个结点

十层,是1024-1=1023个结点

。。。。

也就是:深度为N,节点数为(2^N)-1,叶子节点为2^(N-1),2^N表示2的N次方。

如果还是不太懂,我建议你可以把满二叉树哒公式记一下,(也可以拿一个小本把一下常考哒公式总结一下),考计算机二级是一般都会给你一个题让你自己算,所以公式是一定要熟悉哒,而推倒,只是为了帮助理解记忆。

  希望我哒解释能对你哒学习有所帮助哟,我们一起努力吧,加油!

问题来自: 二叉树的计算