2. 计算机
  3. 已知一棵含有n个结点的树中，只有度为k的结点和度为0的叶子结点，则该树中含有的叶子结点个数为【 】。

已知一棵含有n个结点的树中，只有度为k的结点和度为0的叶子结点，则该树中含有的叶子结点个数为【 】。

admin2009-03-15  55
问题 已知一棵含有n个结点的树中，只有度为k的结点和度为0的叶子结点，则该树中含有的叶子结点个数为【  】。
选项
答案((k-1)×n+1)/k
解析 设这棵树中叶子结点数为n0，度数为k的结点数为nk，总结点数为n，则
　　　　　　　　　　　　　　n=n0+nk    式(1)
   设树的总入度为m。由于在树中除了根结点外，其余每一个结点都有唯一的一个分支进入，则树的总结点数为
　　　　　　　　　　　　　　n=m+1    式(2)
   又由于树中这m个进入分支分别由非叶子结点射出，在这棵树中，只有度为k的结点和度为0的叶子结点，所有全部都由度为k的结点射出，而且射出分支总数与总的进入分支数相等，即
　　　　　　　　　　　　　　m=k×nk    式(3)
   由式(1)、(2)、(3)可以得到n0=((k-1)×n+1)/k。
转载请注明原文地址:https://kaotiyun.com/show/aE7Z777K
本试题收录于： 二级VF题库NCRE全国计算机二级分类
0

二级VF

NCRE全国计算机二级

相关试题推荐
随机试题
最新回复(0)