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

admin2017-08-16 45

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

选项

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

解析

转载请注明原文地址:https://kaotiyun.com/show/iJRi777K

计算机408

相关试题推荐

随机试题

最新回复(0)