题目

数据结构中数的叶子结点计算问题
一棵树有n个度为1的结点,n2个度为2的结点,.,nm个度为m的结点,则该树共有多少个叶子结点?
//是不是n1+2n2+.+m*nm?

提问时间：2021-04-04

答案

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