在一颗度为n的树T中,有20个度为a的节点,有10个度为b的节点,1个度为c的结点,十个度为d的结点,则数T中的叶结点个数为多少
时间: 2024-04-01 10:33:09 浏览: 53
二叉树叶子结点个数计算.doc
5星 · 资源好评率100%
树中的叶节点数为 $n - (\text{度为}a\text{的节点数} + \text{度为}b\text{的节点数} + \text{度为}c\text{的节点数} + \text{度为}d\text{的节点数})$。
因为树中每个节点的度数之和等于 $2 \times (\text{树的边数})$,所以可以列出如下方程:
$20a + 10b + 1c + 10d = 2(n-1)$
又因为树中的节点数等于边数加一,即 $n = (20+10+1+10) + 1 = 42$,带入上式得:
$20a + 10b + 1c + 10d = 82$
又因为 $a,b,c,d$ 均为正整数,所以 $c$ 只能等于 $1$。将 $c=1$ 代入上式得:
$20a + 10b + 10d = 72$
化简得:
$2a + b + d = 7.2$
因为 $a,b,d$ 均为正整数,所以 $a$ 只能等于 $3$,此时 $b+d=1.2$,因为 $b,d$ 均为 $d$ 的倍数,所以 $d$ 只能等于 $1$,$b$ 只能等于 $0.2$,但 $b$ 必须为正整数,所以无解。
因此,树T中的叶节点数为 $42-(20+10+1+10)=1$。
阅读全文