一道CSP2025 J组的题目
体面如下:
一棵包含1000个节点的完全二叉树,其叶子节点的数量为多少?
A.499 B.512 C.500 D.501
我们知道一个二叉树中有以下三种节点:有两个子节点的节点、只有一个子节点的节点、叶子节点(没有子节点的节点),所以二叉树的节点可以表示为:$sum=n_1+n_2+n_0$,而通过总结发现有两个子节点的节点数总是比叶子节点少一个,所以又有了:$n_2=n_0-1$,也可变形为:$n_0=n_2+1$,带入原式可得:$sum=n_1+2n_2+1$,而对于完全二叉树,只有一个子节点的节点要么有一个,要么没有,分别尝试后,可以通过奇偶性判断出只有一个子节点的节点的个数。
而对于这道题可以列出$1000=n_1+2n_2+1$,只有$n_1=1$时才成立,所以得出如下式子:$1000=1+2n_2+1$,解的$n_2=499$,通过$n_0=n_2+1$得出叶子节点有500个。
故此题选C。