一棵完全二叉树上有1001个结点,其中叶子结点的个数是(3)。A.490B.500C.501D.505

Question

一棵完全二叉树上有1001个结点，其中叶子结点的个数是(3)。

A．490

B．500

C．501

D．505

Answer 1

正确答案：C
解析：这棵完全--X．树的高度为根据二叉树的性质，从第1层到第 9层共有结点2⁹-1＝511个。第10层全部是叶子结点，因此处于第10层的叶子结点数为 1001-511＝490。同时注意到，第9层有2^9-1-490/2＝11个叶子结点。因此共有490+11 =501个叶子结点。也可以用另外一种方法来做。设二叉树的总结点数为n，叶子结点数为n0，度为1的结点数为n1，度为2的结点数为n2，根据二叉树的性质有：n0=n2+1，n=n1+2n2+1，于是可得，n=n1+2n0-1，由于在完全二叉树中，度为1的结点总数n1要么为0要么为1，此题中显然为0，这样才能保证等式两边都是奇数，因此1001＝2n0-1，解得n0＝501。