满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(

问题单项选择题

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

（37）处应填（）。

A．2i

B．2i-1

C．2i+1

D．2i+2

答案

参考答案：C

解析：

试题(36)、(37)

[分析]：

本题考查数据结构中二叉树的基本知识。

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