在一棵完全二叉树中,其根的序号为1,(1)可判声序号为p和q的两个结点是否在同一层。A.B.C.D.

Question

在一棵完全二叉树中，其根的序号为1，(1)可判声序号为p和q的两个结点是否在同一层。

A．

B．

C．

D．

Answer 1

正确答案：A
解析：一棵深度为k且有2k-1(k1)个结点的二叉树称为满二叉树。如果深度为k、有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第k层或k-1层(最后两层)。性质1：具有n(n＞0)个结点的完全二叉树的深度为+1。性质2：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：(1)如果i=1，则结点i无双亲，是二叉树的根；如果i＞1，则其双亲是结点[i/2]。(2)如果2i＞n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。(3)如果2i+1＞n，则结点i无右孩子：否则，其右孩子是结点2i+1。根据以上性质，要判定序号为p和q的两个结点是否在同一层，即求是否成立。所以A为所求的结果。