数据结构:设树T的高度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子树为多少?为什么?
1个回答

设度为0的结点数为n0,度为1的结点数为n1,度为2的结点数为n2,度为3的结点数为n3,度为4的结点数为n4,那么这棵树总的结点数为n0+n1+n2+n3+n4;又因为树中的每个结点(除了根结点外)都有一个指针指向它,那么这棵树总的结点数为总的指针数加上1;

总的指针数=1*n1+2*n2+3*n3+4*n4;故有:

1+1*n1+2*n2+3*n3+4*n4=n0+n1+n2+n3+n4;从而有

n0=1+n2+2*n3+3*n4=1+2+2*1+3*1=8;