一颗完整的二叉树共360个结点,二叉树中度为一的结点数是多少。最好有计算过程谢谢。
刘慧玲 资深达人 2016-02-04 17:38:45
2480 3 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。

共 3 个回答

    青栀如初 资深大师 3431天前

    亲爱哒

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

      我们说:完全二叉树是指:若设二叉树的深度为h,除第 h 层外,其它各层 (1h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

      完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1n的结点一一对应时称之为完全二叉树。

      若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。

      亲爱哒我们接着来看这道题:

       我们说:

    根据二叉树的性质n0 = n2 + 1以及完全二叉树中度为1的结点个数最多为1

    可以推出如下结论如果完全二叉树中结点个数n是偶数:

       度为0的结点个数n0 = n / 2

       度为1的结点个数n1 = 1

       度为2结点个数为n / 2 - 1

          如果完全二叉树中结点个数n是奇数:

       度为0的结点个数n0 = (n + 1)/ 2

       度为1的结点个数n1 = 1

       度为2结点个数为(n - 1) / 2

    那么我们再来看这道题:

      完全二叉树中度为0的结点要么1个,要么0个,由于总结点数为偶数个,所以度为1的结点只有1个;度为2的结点为k,则度为0的结点为k+1,360-k-k-1一定是奇数

      所以由于总节点数是360是偶数,而且度为1的节点只有1个,所以应该选择B选项就对了。

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



    原鑫鑫 资深达人 3431天前

    一个完全二叉树,度为一的结点树,只有0,或者1,两种可能。

    有一个公式是:叶子结点树=度为2的结点树+1.

                 总结点树=度为1的结点树+度为2的结点树+叶子结点树

    首先看第一个公式,它说明叶子结点树与度为2的结点树想加是一个奇数,那么看第二个公式,一个完整的二叉树有360个结点,偶数,说明什么?度为1的结点树是一个奇数,所以是1.


    最佳答案

    小胖咩 正式会员 3431天前

    审题!首先明确定义:

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

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

    为什么完全二叉树度为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

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

  • 0

    点赞

  • 扫一扫分享朋友圈

    二维码

  • 分享

相关问题