Question

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

Answer 1

设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001
根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + n1 = 1001
由于完全二叉树的n1 只能是0或者1，为满足2n2 + n1 = 1001，n1 = 1，因此n2 = 500
所以n0 = 501，即叶子个数是501个

Answer 2

设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001
根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + n1 = 1001
由于完全二叉树的n1 只能是0或者1，为满足2n2 + n1 = 1000，n1 = 0，因此n2 = 500
所以n0 = 501，即叶子个数是501个

Answer 3

首先，要知道在完全二叉树中有一个定理：当有0个度为1的结点，该二叉树的总结点数为奇数，有1个度为1的结点，该二叉树的总结点数为偶数。在该题中，总节点数为1001，是奇数。所以可知该完全二叉树中有0个度为1的结点。
n表示总节点数
n1表示度为1的结点
n2表示度为2的结点
n0表示度为0的结点
有n=n0+n1+n2
n0=n2+1
已知n1
所以可得n=2n2+1
可得n2=500
n0=500+1
n0=501

Answer 4

1023是满二叉树，有512片叶子。1001比1023少22个结点，所以有512-22+22/2=501片叶子。
511是满二叉树，有256片叶子。1001比511多490个结点，所以有256+490-(490+1)/2=501片叶子。
所以答案就是501了。

Answer 5

二叉树性质：n0
=
n2
+
1
因为n0
+
n1
+
n2
=
1001
所以2n2
+
1
+
n1
=
1001
由于该等式右边为奇数，左边的n1只能是偶数
又因为完全二叉树中度为1结点个数n1要么是0要么是1
所以只能是0
因此n2
=
500
所以n0
=
501