【经验分享】数据结构——求树的叶子结点个数计算方法

一道题就可以学会

在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）

A、41

B、82

C、122

D、其他

这种题做法固定，记住两个公式即可

①n = 20 10 1 10 x

②n-1 = 20*4 10*3 1*2 10*1 x*0

联立①、②得：

x(叶子结点)=82

解惑：

1、为什么n=20 10 1 10 x？

答：结点总数=所有结点数的和

2、为什么是n-1=20*4 10*3 1*2 10*1 x*0？

答：对于任意树，如果树中有 n 个节点，则树中有 n−1 条边。

边数=节点数−1

边数=该结点*该结点的度 该结点*该结点的度 ... 该结点*该结点的度

注：参照上面的表和式子理解这个公式，很好理解的。