Question

在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为（），假定树根结点的编号为0.

在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为（），假定树根结点的编号为0. 答案是C。 求解释
A.2i B.2i-1 C.2i+1 D.2i+2

Answer 1

答案选C。若i＝0，则左孩子显然为1，i＝1，左孩子为3.假设i>1，且设第j层的第一个结点编号为i，由二叉树的定义和性质可知i＝2^(j-1)-1,则左孩子必为第j+1层的第一个结点，编号为2^j-1＝2^(j-1)+1＝2i+1。