作业帮 > 数学 > 作业

设有一棵k叉树,其中只有度为0和k两种结点……

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/22 12:56:24
设有一棵k叉树,其中只有度为0和k两种结点……
设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个
数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)
= (K-1) Nk +1
k叉树所有结点的度都不大于k,所以结点总数n=n0+n1+n2+…nk (1)
又因为度为k的结点有k个子树,所以,k叉树中子树结点就有
n(子)=n1+2n2+3n3+…+knk
k叉树中只有根节点不是子树结点,所以k叉树结点总数n=n(子)+1 即 n=n1+2n2+…+knk+1 (2)
结合(1)式和(2)式就得n0=(k-1)nk+(k-2)n(k-1)+…+n2+1
以上为通式~!
因为你的题目里说只有度为0的和度为k的节点,所以算式中只有n0和nk其他的都没有~!
n=n0+nk (1)
n(子)=knk
n=n(子)+1
即n=knk+1(2)
结合(1)(2)得出n0=(k-1)nk+1