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