47．满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为 {{U}}(1) {{/U}}。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为{{U}} (2) {{/U}}(高度为3的满二叉树如图8-17所示)。

单选题 (1)

A、 2^h
B、 2^h-1
C、 2^h-1
D、 2^h-1+1

【正确答案】 C

【答案解析】

单选题 (2)

A、 2i
B、 2i-1
C、 2i+1
D、 2i+2

【正确答案】 C

【答案解析】
[解析] 满二叉树的第1层(树根)有1个结点，第二层有2个结点，第三层有4个结点，依此类推，第h层有2^h-1个结点。将所有层上的结点数相加就是树中的结点总数，即2⁰+2¹+2²+…+2^h-1=2^h-1。第1空的正确答案为选项C。
显然对非空满二叉树中的结点按照题目中的方式进行编号，结点i的左子树编号为2i，右子树编号为2i+1。第2空的正确答案为选项C。

单选题 (1)

A、 1
B、 2
C、 3
D、 4
E、 5 6 7 8 9

【正确答案】

【答案解析】

单选题 (2)

A、 1
B、 2
C、 3
D、 4
E、 5 6 7 8 9

【正确答案】 D

【答案解析】

单选题 (3)

A、 1
B、 2
C、 3
D、 4
E、 5 6 7 8 9

【正确答案】

【答案解析】

单选题 (4)

A、 N1下面
B、 N8下面
C、 N9下面
D、 N6下面

【正确答案】 B

【答案解析】
[解析] 要按照题目要求填结点，那么，左下角的结点n7应当具有最小值，也就是1，右下角的结点n6，应当具有最大值，也就是9。如图8-19所示，现在考虑将2、3、4、 5、6、7、8放入其中。
现在，不考虑n7和n6，在要放入数值的树中，其左下角结点为n4，放入剩余数字的最小值2，根据题目对此树的要求，n8应当放入3。右下角结点为n3，放入剩余数字的最大值为8，根据题目要求，n1应当放入7。结果如图8-20所示。
现在只剩下4、5、6了，根据题目要求，显然应当在n2放入4，n5放入5，n6放入6。最终结果如图8-21所示。所以，第1空的正确答案为选项G，第2空的正确答案为选项D，第3空的正确答案为选项F。