计算机二级二叉树问题求解

设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1.则T中的叶子结点数为___________?
越详细越好啊。。。。。。

龙形蛇意 · 2018-4-30 02:00:10

假设有n个叶子节点，如果某个叶子节点又延伸出来m个叶子节点，则叶子节点数量就是n-1+m
所以看题中，假设一开始只有一个根节点（同时也是叶子节点），它的度为4，这时叶子节点数为1-1+4=4，这时有一个叶子节点度变成3，总的叶子节点数量就是4-1+3=6
类推下去，叶子节点总数为1+(4-1)+(3-1)+(2-1)*2+(1-1)*4=8
如果整理成另一个公式就是1+1*n1+2*n2...+m*nm-(n1+n2+n3...+nm)，其中ni就是度为i的节点数量，用到题中就是1+1*4+2*2+3*1+4*1-(4+2+1+1)=8

计算机二级 二叉树问题求解

1 个回复

计算机二级二叉树问题求解