题目

已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度3的结点,则该树有几个叶子结点?

提问时间：2021-03-31

答案

设该树中的叶子数为n0个.该树中的总结点数为n个,则有：
n=n0+n1+n2+…+nm (1)
又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为：
n-1=0*n0+1*n1+2*n2+…+m*nm (2)
联立(1)(2)方程组可得：
叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm