数据结构中,在一棵有n个结点度为k的树中必有n（k-1）+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*nk②
等式左边n-1的由来:除了根节点外所有的其他每个结点都向上有一个分支指向它
等式右边的由来：某个结点所产生的分支数目=这个结点的度
空链域个数：k*n0+（k-1）*n1+(k-2)*n2+……+n(n-1)+0*nk③
①式乘以k减去②得到③ (k*①-②=③=n*(k-1)+1)
k*①-②得到：k*n-(n-1)=[k*n0+k*n1+……+ k*n(k-1)+ k*nk]-[n1+2*n2+3*n3+……+k*nk]
化简得到：k*n-(n-1)=k*n0+（k-1）*n1+(k-2)*n2+……+n(n-1)+0*nk=③=n*(k-1)+1)
下面是证明 n0=n2+1
①-②得到：
n0+n1+n2+……+n(k-1)+ nk-1=1*n1+2*n2+3*n3+……+(k-1)*n(k-1)+ k*nk
化简得：n0-1=+n2+2*n3+……+(k-2)*n(k-1)+( k-1)*nk
原理一样 你要掌握①式和②式
还有什么疑问再问我好了
相关问题
