在一棵完全二叉树中,其根的序号为1,()可判声序号为p和q的两个结点是否在同一层。
A.A
B.B
C.C
D.D
参考答案:A
解析:
一棵深度为k且有2k-1(k≥1)个结点的二叉树称为满二叉树。如果深度为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为所求的结果。