题目

若一棵度为4的树中度为2、3、4的结点个数分别为3、2、2，总结点个数为25，则该树中度为1的结点个数是多少？

题目解答

答案

结点总数n=n0+n1+n2+n3+n4，又由于除根结点外，每个结点都对应一个分支，所以总的分支数等于n-1。而度为i（0≤i≤4）的结点的分支数为i，所以有：总分支数=n-1=0×n0+1×n1+2×n2+3×n3+4×n4。综合两式得：n0=n2+2n3+3n4+1=3+2×2+3×2=14，则n=n0+n1+n2+n3+n4，n1=n-n0-n2-n3-n4=25-14-3-2-2=4，所以该树中度为1的结点个数是4。

解析

步骤 1：确定结点总数与分支数的关系
在树结构中，结点总数n等于度为0、1、2、3、4的结点个数之和，即n=n0+n1+n2+n3+n4。同时，除根结点外，每个结点都对应一个分支，所以总的分支数等于n-1。而度为i（0≤i≤4）的结点的分支数为i，所以有：总分支数=n-1=0×n0+1×n1+2×n2+3×n3+4×n4。

步骤 2：计算度为0的结点个数
根据题目条件，度为2、3、4的结点个数分别为3、2、2，代入公式n0=n2+2n3+3n4+1，得n0=3+2×2+3×2+1=14。

步骤 3：计算度为1的结点个数
根据结点总数n=25，代入公式n=n0+n1+n2+n3+n4，得n1=n-n0-n2-n3-n4=25-14-3-2-2=4。