数据结构中，在一棵有n个结点度为k的树中必有n（k-1）+1个空链域，这个结论是怎么得到的

Question

如题所述

Answer 1

共有nk个链域，但是只使用了n-1个（因为链域存储的是指向子树根结点的指针，可以理解为孩子，n个结点中只有根结点指针没有存储在链域中，故使用了n-1个链域），然后nk-(n-1)=n(k-1)+1.

不知道我这样说你能不能理解，我自己是这样算的

Answer 2

i=0 : k, ∑(k-i)ni = k∑ni - ∑i*ni=kn-(n-1)
解释：左边为空链域总数，其中ni:度为i的结点数；k:树的度。空链域只存在于ni(i<k)上。
右式仅仅是对左式进行的整理，∑ni即结点总数，∑i*ni即分支总数。

Answer 3

树的度：结点度的最大值
设度为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
<特殊情况: 二叉树，即k=2 时 就可以得到 n0=n2+1>

原理一样 你要掌握①式和②式

还有什么疑问再问我好了本回答被提问者和网友采纳