如果一棵非空k(k≥2)叉树T中每个非叶结点都有k个孩子,则称T为正则k叉树。请回答下列问题并给出推导过程。 若T有m个非叶结点,则T中的叶结点有多少个?

admin2017-08-16  26

问题 如果一棵非空k(k≥2)叉树T中每个非叶结点都有k个孩子,则称T为正则k叉树。请回答下列问题并给出推导过程。
若T有m个非叶结点,则T中的叶结点有多少个?

选项

答案根据定义,正则k叉树中仅含有两类结点:叶结点(个数记为n0)和度为k的分支结点(个数记为nk)。树T中的结点总数n=n0+nk=n0+m。树中所含的边数e=n-1,这些边均为m个度为k的结点发出的,即e=m×k。整理得:n0+m=m×k+1,故n0=(k.1)×m+1。

解析
转载请注明原文地址:https://jikaoti.com/ti/jnfjFFFM
0

最新回复(0)