Question

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

Answer 1

每条边对应一个节点,只有根节点没有相应的边.

所以

（节点个数）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个叶子节点