设有一棵k叉树,其中只有度为0和k两种结点……设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数
更新时间：2026-09-30 16:20:29
问题描述:
设有一棵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