满二叉树即完全二叉树吗?满二叉树是指一个父节点上就有2个子节点吗,还是最多有2个子节点?”完全二叉树度为1的结点不是0就是1“什么意思?
孙欣蕾 正式会员 2016-02-12 16:55:11
2147 2 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。

共 2 个回答

    青栀如初 资深大师 3423天前

    亲爱哒,不好意思刚刚才看到问题。满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。 完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。 对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。 完全二叉树具有以下两个性质: 性质5:具有n个结点的完全二叉树的深度为[log2n]+1。 性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论: ①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。 ②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。 ③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。 满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。

    青栀如初 资深大师 3423天前

    【1】完全二叉树,除最后一层可能不满以外,其他各层都达到该层节点的最大数,最后一层如果不满,该层所有节点都全部靠左排 满二叉树,所有层的节点数都达到最大 【2】 一棵深度为k且有2的k次方减1个结点的二叉树是满二叉树。 深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。 可见,满二叉树是结点数最多的完全二叉树。亲爱哒“望采纳哟!”如果以后还有什么不懂哒问题我们还可以一起讨论哟,相信我们一定会把问题解决哒。亲爱哒“新年快乐哟!祝你在新的一年里开开心心乐常在,健康快乐永相随!”么么哒亲爱哒*^_^**^_^**^_^*

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

  • 0

    点赞

  • 扫一扫分享朋友圈

    二维码

  • 分享

相关问题