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

admin2019-05-11  33

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


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

答案C

解析 本题考查数据结构中二叉树的基本知识。满二叉树的第1层(树根)有1个结点,第二层有2个结点,第三层有4个结点,依此类推,第h层有2h-1个结点。将所有层上的结点数相加就是树中的结点总数,即 20+21+22+…+2h-1=2h-1。显然对非空满二叉树中的结点按照题目中的方式进行编号,结点i的左子树编号为2i,右子树编号为2i+1。
转载请注明原文地址:https://jikaoti.com/ti/flL7FFFM
0

最新回复(0)