问答题 如果一棵树有n1个度为1的结点,有n2个度为2的结点……有nm个度为m的结点,试问有多少个度为0的结点?试推导。
【正确答案】设树中总结点数为n=n0+n1+n2+…+nm,总分支数为e=n-1,则
e=n0+n1+n2+…+nm-1=m×nm+(m-1)×nnm-1+…+2×n2+n1
[*]

n0=n2+2n3+…+(m-1)nm
例如,在一棵度为4的树中,有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树中度为0的叶结点个数为
n0=(2-1)×1+(3-1)×10+(4-1)×20=1+20+60=81
【答案解析】