数据结构中,在一棵有n个结点度为k的树中必有n(k-1)+1个空链域,这个结论是怎么得到的
问题描述:
数据结构中,在一棵有n个结点度为k的树中必有n(k-1)+1个空链域,这个结论是怎么得到的
答
树的度:结点度的最大值设度为0 ,度为1 ,度为2 ……度为k,度为k-1的结点数目分别为:n0,n1,n1,……,n(k-1),nk.总的结点数目:n=n0+n1+n2+……+n(k-1)+ nk.①总的分支数目:n-1=1*n1+2*n2+3*n3+……+(k-1)*n(k-1)+ k*...