作业帮 > 数学 > 作业

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

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/09 03:24:56
数据结构中数的叶子结点计算问题
一棵树有n个度为1的结点,n2个度为2的结点,.,nm个度为m的结点,则该树共有多少个叶子结点?
//是不是n1+2n2+.+m*nm?
如果在问叶子结点,则是n1个.
叶子结点不就是最外面的结点嘛,当然度数为1啰.
如果问所有的结点数,则是(n1+2n2+.+m*nm) / 2+1个.
括号里计算的是总度数.
解决这个问题可以用数学归纳法.在只有1个结点的时候,总度数显然为0;由于是颗树,所以往后每再加一个结点,总度数都会再加2(新加的结点和它连结的结点度数各加1).
所以,总度数除以2就是后面加入的结点数,再加1就是总结点数.