问题 单项选择题

在一棵完全二叉树中,其根的序号为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为所求的结果。

材料题
单项选择题