数据结构中,在一棵有n个结点度为k的树中必有n(k-1)+1个空链域,这个结论是怎么得到的
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/25 07:09:16
![数据结构中,在一棵有n个结点度为k的树中必有n(k-1)+1个空链域,这个结论是怎么得到的](/uploads/image/z/5171342-14-2.jpg?t=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%AD%2C%E5%9C%A8%E4%B8%80%E6%A3%B5%E6%9C%89n%E4%B8%AA%E7%BB%93%E7%82%B9%E5%BA%A6%E4%B8%BAk%E7%9A%84%E6%A0%91%E4%B8%AD%E5%BF%85%E6%9C%89n%EF%BC%88k-1%EF%BC%89%2B1%E4%B8%AA%E7%A9%BA%E9%93%BE%E5%9F%9F%2C%E8%BF%99%E4%B8%AA%E7%BB%93%E8%AE%BA%E6%98%AF%E6%80%8E%E4%B9%88%E5%BE%97%E5%88%B0%E7%9A%84)
数据结构中,在一棵有n个结点度为k的树中必有n(k-1)+1个空链域,这个结论是怎么得到的
数据结构中,在一棵有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*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
原理一样 你要掌握①式和②式
还有什么疑问再问我好了