全部问题 > 当前问题

满二叉树的全部节点数应该是个奇数吧?比如深度是2的满二叉树共(2^n)-1=3个节点,第二层有2^(n-1)=2个节点,为什么题目里的满二叉树总结点数会出现256呢?

1.pic.jpg

Crystal 2016-3-21 17:46:30

共 5 个回答

青栀如初 2016-3-21 17:48:41

亲爱哒

  不好意思,刚刚才看到问题

  亲爱哒,你记一个完全二叉树的总节点树与二叉树深度的关系式就可以了

  亲爱哒,对于一个深度为:n的二叉树来说,它的总节点树为【2的(n-1)次方】

  比如:深度为:3的二叉树,它的总节点树就为:【2的(n-1)次方=2的(3-1)次方=2的2次方=4】

  如果给了我们总节点树我们也是可以推出:二叉树的深度的

  比如这道题告了我们总节点树为:256,那么由公式我们可以知道:【2的(n-1)次方=256】

  我们又知道:2的8次方=256,所以与公式相对应也就是:【2的(n-1)次方=2的8次方=256】

  我们可以推出:n-1=8也就是说:n=8+1=9

  所以我们说:完全二叉树的节点数为:256,那么它的深度为:9

  所以根据我们刚刚的推理:我们选择C选项就可以了

  亲爱哒“望采纳哟!”如果以后还有什么不懂哒问题我们还可以一起讨论哟,相信我们一定会把问题解决哒,么么哒亲爱哒(❁´◡`❁)*✲゚*

懒猫 2016-3-21 17:50:44

所以我才说这个题目存在一定的错误或者歧义,如果你用我刚才的一的话,那就存在余数,余数是不可能存在二叉树中,换位二的话,则刚好与256对等,且不存在余数,故选择第二种

Crystal 2016-3-21 17:50:48

回复 青栀如初:可是你画一个深度是3的看看,总共不应该是7个节点吗,4个是第三层这一层的节点数啊

Crystal 2016-3-21 17:52:12

回复 懒猫:刚才的?我没有懂,什么是“换位二的话”

最佳答案

懒猫 2016-3-21 17:54:38

这道题我觉得存在一个错误,

一,如果是题目中完全二叉树的总结点为256个,则算法应该是根据总结点=(2^n)-1,结果n约等于8,余数为1.

二,如果按解析中显示的,则它是将256作为第i层的总结点,则算法应该是根据第i层结点数=2^(i-1),结果i=9

因为一中存在余数,不可能存在二叉树中,故应该按二来理解。

懂了吗?


问题来自: 二叉树的计算