我要招人

去企业版

首页 > 试题广场 >

设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2

[单选题]

设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为()

```
5
```
```
6
```
```
7
```
```
8
```

查看正确选项

登登gogo

节点数=分叉树+1

8+x = 4+4+3+4+1

求x即可

发表于 2016-08-10 12:47:35 回复(0)

NotFear

学过离散数学的大家应该知道，m(边数）=n(顶点数）-1；

m=1*4+2*2+3*1+4*1=15；所以，n=16。

所以，叶子节点个数=16-4-2-1-1=8

发表于 2018-12-25 20:37:17 回复(0)

菘青

一个结点有几个子树(即边)就是多少度，于是树T共有 1*4+2*2+3*1+4*1 = 15（条边）

一颗树的边数=结点数-1 故T有16个结点

显然，总的结点数目-去非0度的结点数=叶子数

于是对于树T有 16-4-2-1-1 = 8

发表于 2015-08-09 13:51:59 回复(0)

Aesthetic92

答案：选D

一棵含有n个结点的树，有n-1个分支，即 n = 1*4 + 2*2 + 3*1 + 4*1 + 1 = 16;

又由于 n = n₀ + n₁ + n₂+ n₃+ n₄ = n₀ + 8;

n₀ + 8 = 16，所有叶子结点个数为8

编辑于 2021-01-12 11:49:59 回复(5)

程序猿Go师傅

感觉别的答案都没有讲的很清楚，我这个证明方法是比较清晰的，大家可以参考下。

因为二叉树中所有结点的度数均不大于4，所以结点总数(记为n)="0度结点数(n0)" + "1度结点数(n1)" + "2度结点数(n2)"+“3度结点数（n3）”+“4度结点数（n4）”。由此，得到等式一。
(等式一) n=n0+n1+n2+n3+n4

0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2+3n3+4n4。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2*n2+3*n3+4*n4+1

由等式1，2可以得出，n0=n2+2n3+3n4+1=2+2+3+1=8

n0即叶子结点。

编辑于 2019-10-21 17:04:22 回复(0)

叶子杉

对于度为m的数，其叶子节点的个数n₀=1+n₂+2n₃+3n₄+......+(m-1)n_m。

_{所以本题叶子节点个数} n ₀=1+2+2*1+3*1=8

发表于 2016-05-23 21:59:14 回复(1)

明如月

直接根据题目画出示意图就可以看出来~

图片说明

发表于 2017-07-26 16:16:36 回复(0)

一个锤子

设一棵树的结点总数为N，度为1,2,3,4和叶子结点的个数分别为n₁,n₂,n₃,n₄,n₀

那么有 N=n0+n1+n2+n3+n4+n5

再根据每一个结点的出度可以得出 N=n1+2n2+3n3+4n4+1（最后加1表示根节点，它不是任何结点的子结点）

两式相减可得 n0=n2+2n3+3n4+1=2+2*1+3*1+1=8

发表于 2018-12-19 20:21:13 回复(0)

wcz2023

发表于 2018-11-15 00:07:12 回复(0)

Ronin20180903233660

结点数=度数+1

算一下就可以

发表于 2018-10-10 18:20:11 回复(0)

wxl_1605

一共的度数为边数，边数+1为节点数，树的度为4，则存在0、1、2、3、4五种度，叶子数是0度节点，所以是16-4-2-1-1=8

发表于 2018-09-10 22:39:20 回复(0)

lilinl

树T的边数=1*4+2*2+3*1+4=15

则树的总的节点数=树T的边数+1=16

叶子结点=度为0的节点=16-4-2-1-1=8

发表于 2018-07-31 21:34:38 回复(0)

xxxxxxxxxxxxxxxa

通过边和节点数的关系推导吧 0 1 2 3 4

x 4 2 1 1

1*4+2*2+3*1+4*1+1=x+4+2+1+1

x=8

有些题需要树的空域关系推导，n个节点的2叉树的空域为n+1，其他m阶树，同理。

发表于 2018-06-16 14:40:34 回复(0)

てんდちん

总结一个公式，设度为n个节点的树有n-1个分支，由于总节点数为N = 1*n₁ + 2*n₂ + .... +n * n_n + 1再者还有总结点数为N = n₀ + n₁ + n₂ +...+ n_n,两个公式结合，就可以得到
n0 = n₂ + 2* n₃ + ....+ （n-1）* n_n+1
以后就可以用这个公式直接就是求n₀。
该题目 n0 = 2 + 2* 1 + 3* 1 + 1 = 8

发表于 2018-04-07 13:18:26 回复(0)

keyu88888

每条边对应一个节点，只有根节点没有相应的边。
所以
 （节点个数）m=（边数）n+1
  一个度为4的节点对应有4条出边，
一个度为3的节点对应有3条出边，
一个度为2的节点对应有2条出边，
一个度为1的节点对应有条出边， 叶子节点没有出边。
所以
（边数）n=1*4+2*2+3*1+4*1（所有节点的度之和）=15
根据（节点个数）m=（边数）n+1
所以
（节点个数）m=16
除去度为1，2，3，和4的结点
剩下的就是叶子节点 8个叶子节点

发表于 2016-11-01 15:02:57 回复(0)

小份比昂比昂面

在二叉树中，叶子节点的个数=度为2的结点个数 + 1，这个证明就不用说了吧。学过数据结构的话，书上都有相应的证明的。

在树种，是二叉树的一个推广：

叶子节点的个数= n2 + 2*n3 + 3*n4 + …… + (n-1)*nn + 1

n2表示度为2的结点个数，n3表示度为3的结点个数

在本题中：

n0 = n2 + 2*n3 + 3*n4 + 1

2 + 2*1 + 3*1 + 1 = 8

发表于 2016-09-23 17:39:26 回复(0)

细雨湿身

一棵含有n个结点的树，有n-1个分支，即 n = 1*4 + 2*2 + 3*1 + 4*1 + 1 = 16;

又由于 n = n0 + n1 + n2 + n3 + n4 = n0 + 8;

n0 + 8 = 16，所有叶子结点个数为8

发表于 2016-09-12 19:28:59 回复(0)

huixieqingchun

一棵有n个结点的树，含有n-1条边，每一条边代表一个度；故n-1=15;

所以根据结点的个数可以求得叶子结点的个数。

发表于 2016-05-07 20:25:55 回复(0)

阳光依旧smile

度为有几条边边数在计算节点数时很有作用…

发表于 2016-04-14 10:16:31 回复(0)

ryl

0 0 0 0 0 000 00 00 剩下的度为1的四个结点随意在上边树的四个叶子上接就行数数几个？

发表于 2016-03-27 21:17:04 回复(0)

提交观点

问题信息

树

难度：

20条回答 379收藏 26166浏览

设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2

问题信息

热门推荐

相关试题