-
Use mathematical induction to prove that the number of leaves in a nonempty full K-ary tree is
$$(K − 1)n + 1$$, where n is the number of internal nodes.
-
当一个非空满K叉树只有一个叶子结点时，此时内部结点数为0，满足其叶子结点数为1;
-
假设，对于一个有
$$n'=n-1$$个内部结点（
$$n\geq1$$）的K叉树，其叶子结点数为
$$n_{leaf}'=(K − 1)n' + 1$$。
-
那么此时，由于该K叉树为满K叉树，则添加
$$K$$个结点，使得它仍为满二叉树。内部结点
$$n=n'+1=n$$。同时叶子结点数
$$n_{leaf}=n_{leaf}'+K=Kn'-n+1+K$$。代入
$$n=n'+1$$，
$$Kn-K-n+1+K=(K-1)n+1$$仍然成立。
综上所述，一个非空满K叉树的叶子结点为
$$(K − 1)n + 1$$，其中
$$n$$是内部结点数。
$$\dfrac{k+2}{k+6}$$