一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶子结点个数是
时间: 2024-05-07 18:09:27 浏览: 139
CSP-S1提高组初赛复习3_树.pdf
设树T的叶子节点个数为x,则树T的结点总数为:
20(度为4的结点)+ 10(度为3的结点)+ 1(度为2的结点)+ 10(度为1的结点)+ x(叶子结点个数)= 41 + x
根据树的性质,树的结点总数等于叶子结点个数加上非叶子结点个数,而非叶子结点个数又等于度数之和除以2,所以有:
20(度为4的结点)+ 10(度为3的结点)+ 1(度为2的结点)+ 10(度为1的结点)+ x = (20×4+10×3+1×2+10×1)/2 + x
化简得:
x = 58
因此,树T的叶子结点个数为58个。
阅读全文