问题
填空题
已知一棵含有n个节点的树中,只有度为k的节点和度为0的叶子节点,则该树中含有的叶子节点个数为______。
答案
参考答案:((k-1)×n+1)/k
解析: 设这棵树中叶子节点数为n0,度数为k的节点数为nk,总节点数为n,则
n=n0+nk 式(1)
设树的总入度为m。由于在树中除了根节点外,其余每一个节点都有唯一的一个分支进入,则树的总节点数为
n=m+1 式(2)
又由于树中这m个进入分支分别由非叶子节点射出,在这棵树中,只有度为k的节点和度为。的叶子节点,所有全部都由度为A的节点射出,而且射出分支总数与总的进入分支数相等地,即
m=k·nk 式(3)
由式(1)、(2)、(3)可以得到n0=((k-1)×n+1)/k。