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

admin2010-11-26 33

问题已知一棵含有n个节点的树中，只有度为k的节点和度为0的叶子节点，则该树中含有的叶子节点个数为______。

选项

答案((k-1)×n+1)/k

解析设这棵树中叶子节点数为n⁰，度数为k的节点数为nk，总节点数为n，则
n＝n⁰+nk 式(1)
设树的总入度为m。由于在树中除了根节点外，其余每一个节点都有唯一的一个分支进入，则树的总节点数为
n＝m+1 式(2)
又由于树中这m个进入分支分别由非叶子节点射出，在这棵树中，只有度为k的节点和度为。的叶子节点，所有全部都

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

本试题收录于：二级VF题库NCRE全国计算机二级分类