为什么 完全二叉树度为1的结点不是0就是1?
Batty 资深达人 2016-02-16 15:28:51
3527 4 0
问题来自: 二叉树的计算
一棵完全二叉树共有360个结点,则在该二叉树中度为1的结点个数为( )
A. 0
B. 1
C. 180
D. 181
答案:B
解析:总结点数=叶子结点数+度为1的结点数+度为2的结点数。叶子结点数=度为2的结点数+1=[总结点数/2](完全二叉树度为1的结点不是0就是1),[]表示向上取整。根据以上公式得出叶子结点为180,度为2的结点数为179,则度为1的结点数为1。所以选择B。

共 4 个回答

    青栀如初 资深大师 3419天前

    亲爱哒

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

      亲爱哒我们应该先审题,明确定义,然后再去做题就好做多了

    满二叉树:除最后一层外,每一层上的所有结点都有两个子节点。在满二叉树中,每一层上的节点数都达到最大值。

    完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干节点。

    为什么完全二叉树度为1的节点不是0就是1?这是根据完全二叉树的定义得出的,完全二叉树左右子树的深度之差不大于1,所以要么只有一个度为1的节点,要么没有。

    对于这道题,设叶子节点数为x,则度为2的节点数为x-1

    那么根据总节点数公式,可以列出 360=x+x-1+度为1的节点数 。

    移项得 361-度为1的节点数=2x,完全二叉树度为1的节点不是0就是1,且x得是整数吧,所以嘞x=180,度为1的节点数为1 ,所以我们选择B选项就可以了

      亲爱哒,望采纳哟,如果以后还有什么不懂哒地方我们还可以一起讨论哟,么么哒亲爱哒!


     

    Batty 资深达人 3419天前

    回复 青栀如初:亲爱的,我想象不出来这两种有什么不同。如果可以的话,能够给我发个图形形象的看看吗?不好意思啊,脑子转不过来啦.....

    最佳答案

    青栀如初 资深大师 3419天前

    亲爱哒

       我们说:对于一个完全二叉树来说,度为一的结点树,只有0,或者1,两种可能。

      公式一:叶子结点树=度为2的结点树+1.=总结点数/2

       公式二:总结点树=度为1的结点树+度为2的结点树+叶子结点树

     由题我们可以知道:完全二叉树的总结点数为:360

     所以由公式一可知:叶子结点数=总结点数/2=360/2=180

     又因为公式一中:叶子结点树=度为2的结点树+1——我们可以推出:度为2的结点树=叶子结点树-1=180-1=179

      由公式二我们可以推出:度为1的结点树=总结点树-度为2的结点树-叶子结点树=360-179=1

      亲爱哒,所以由公式推导我们可以知道:该二叉树中度为1的结点个数为1,所以我们选择B选项就可以了

       亲爱哒,“望采纳哟!”如果还有什么不懂哒问题我们还可以一起讨论哟,相信我们一定会把问题解决哒,么么哒亲爱哒!

        亲爱哒:“新年快乐哟!”祝你在新哒一年里开开心心乐常在,健康幸福永相随,么么哒亲爱哒*^_^**^_^**^_^*

    青栀如初 资深大师 3419天前

    回复 Batty:亲爱哒,最后一步公式推导写错了,应该为:

    由公式二我们可以推出:度为1的结点树=总结点树-度为2的结点树-叶子结点树=360-179-180=1就对了

您还没有登录,所以不能回复该问题
我要回复

  • 0

    点赞

  • 扫一扫分享朋友圈

    二维码

  • 分享

相关问题