首页 > 试题广场 >

设一棵m叉树中度数为0的结点数为N0 ，度数为1的结点数为N

[单选题]

设一棵m叉树中度数为0的结点数为N0 ，度数为1的结点数为Nl ，……，度数为m的结点数为Nm，则N0=（）。 

  • Nl+N2+……+Nm
  • l+N2+2N3+3N4+……+(m-1)Nm
  • N2+2N3+3N4+……+(m-1)Nm
  • 2Nl+3N2+……+(m+1)Nm
查看正确选项
添加回答
不忘初心跟党走头像 不忘初心跟党走
m叉树总的指针数为N1 + 2N2 + ...+mNm
总的节点数为N 0 +N1 + N2 + ...+Nm ，需要的指针数为N 0 +N1 + N2 + ...+Nm -1
以上两式相等得出N 0 =1+ N2 + 2N3...+(m-1)Nm
编辑于 2017-06-02 23:00:00 回复(6)
收获2018头像 收获2018

感觉这种题最快的方法是将题目实例化：比如这是一棵二叉树，然后随便画一棵，统计度数为0、1、2的个数，然后对照答案，找出正确的算式。

发表于 2017-12-26 20:41:27 回复(4)
小小丽头像 小小丽
总结一下各位大佬的回答：
首先，实在理解不了算法，考场上可以将题目实例化：比如创造一棵二叉树，统计度数为0、1、2……的个数，对照答案，找出正确的算式。

再来看正确推理：

设n为树的结点总数，则n=n0+n1+···+ni。

除了根结点外，其余点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由除了叶子结点外的结点射出的，所以又有B=n1+2*n2+···+i*ni

于是n=1+n1+2*n2+···+i*ni
联合两个关系可得：

n0=1+n2+2n3+···+(n-1)ni


发表于 2020-06-07 09:33:08 回复(1)
守护之魂头像 守护之魂

由2叉树的性质引申出，对于任何一颗树T，如果其终端结点树为n0 度为i的结点数为ni，则n0=1+n2+2n3+···+(i-1)ni

推导如下：

设n为树的结点总数，则

n=n0+n1+···+ni

即度为0、1、2、···、i的结点数之和

再看树的分支数。除了根结点外，其余点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由除了叶子结点外的结点射出的，所以又有

B=n1+2*n2+···+i*ni

于是有

n=1+n1+2*n2+···+i*ni

所以结合之前的n=n0+n1+n2+···+ni可得

n0=1+n2+2n3+···+(n-1)ni



发表于 2019-04-29 20:46:11 回复(0)
zz2108828头像 zz2108828
直接推公式://类似细胞分裂一样
原理: 
    度为 n 的 1 个结点分裂为 n 个新的结点.  新增加的结点数为 n-1.
    将 N0 看做 结 完成分裂后的总数.
    N0 = 每次分裂增加的结点总数 + 1  (+1 意味着加上最开始分裂的那个结点)
例子: 一颗树 N2 = 2 , N3 = 2.
 
                 O
              /       \
            O        O    // 1个结点分裂出 2个新结点, 增加 1*(2-1)=1 个 结点,
          /  |  \    /  |  \
        O O O O O O  // 2 个结点各分裂出 3个新结点, 增加 2*(3-1) = 4 个 结点,
       /  \
    O     O                 //1个结点分裂出 2个新结点, 增加 2*(3-1) = 1 个 结点,

N0 = (1+4+1)+1 = 7



发表于 2018-05-31 00:22:25 回复(0)
柘月十七头像 柘月十七
要注意树中度数（又为边数、指针数）、结点数与叶子结点数之间的关系。
在这里，总结点数：N₀+N₁+N₂+N₃......Nм
总度数为：N₁+2N₂+3N₃......mNм;
总结点数=总度数+1
N₀+N₁+N₂+N₃......Nм = N₁+2N₂+3N₃......mNм  + 1
N₀ =  1 + N₂ + 2N₃ + (m-1)Nm
发表于 2021-03-25 16:57:54 回复(0)
卜白_头像 卜白_
我的思路是选最长的。
编辑于 2024-03-19 21:10:08 回复(0)
云云云一飞冲天头像 云云云一飞冲天
节点数=边数+1
发表于 2022-08-23 21:43:18 回复(0)
还没想好名字那头像 还没想好名字那
画个图分析
发表于 2022-03-27 13:12:00 回复(0)
梅老板头像 梅老板
答案那是1还是l呀？
发表于 2022-02-17 10:48:46 回复(0)
天尊墨宇头像 天尊墨宇
选B
m叉树总的指针数为N1 + 2N2 + ...+mNm
总的节点数为N 0 +N1 + N2 + ...+Nm ，需要的指针数为N 0 +N1 + N2 + ...+Nm -1
以上两式相等得出N 0 =1+ N2 + 2N3...+(m-1)Nm

编辑于 2020-07-06 12:49:10 回复(0)
一个锤子头像 一个锤子
在本题中
结点总数N=N0+N1+...+Nm;
N=1+N1+2N2+...+mNm;
=1+
编辑于 2018-03-29 14:20:28 回复(0)
凌梦初辰头像 凌梦初辰
之前一直不太清楚度的概念，之后查了才知道，本题目是求叶子节点的个数。度：每个节点的最大孩子的数量。
发表于 2017-08-04 20:47:22 回复(0)
提交观点

问题信息

树
上传者：阿奻_
难度：
13条回答 13911浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号