数据结构中数的叶子结点计算问题

Question

一棵树有n个度为1的结点，n2个度为2的结点，......，nm个度为m的结点，则该树共有多少个叶子结点？
//是不是n1+2n2+......+m*nm?

Answer 1

如果在问叶子结点，则是n1个。
叶子结点不就是最外面的结点嘛，当然度数为1啰。

如果问所有的结点数，则是(n1+2n2+......+m*nm) / 2+1个。
括号里计算的是总度数。
解决这个问题可以用数学归纳法。在只有1个结点的时候，总度数显然为0；由于是颗树，所以往后每再加一个结点，总度数都会再加2（新加的结点和它连结的结点度数各加1）。
所以，总度数除以2就是后面加入的结点数，再加1就是总结点数。