题目
在具有200个结点的完全二叉树中,设根结点的层次编号为 1,则层次编号为60的结点,其双亲结点的层次编号为()A. 30B. 60C. 120D. 121
在具有200个结点的完全二叉树中,设根结点的层次编号为 1,则层次编号为60的结点,其双亲结点的层次编号为()
A. 30
B. 60
C. 120
D. 121
题目解答
答案
A. 30
解析
完全二叉树的结构特点是:除最后一层外,其他各层的结点数均达到最大值,且最后一层的结点尽可能向左排列。在完全二叉树中,结点的编号通常从根结点开始,按层序递增排列。双亲结点的编号计算是解题的关键:若某结点编号为$i$,则其双亲结点的编号为$\lfloor \frac{i}{2} \rfloor$。
本题中,层次编号实际指结点的编号,而非层数。题目要求找到编号为60的结点的双亲结点编号,进而确定其对应的选项。
-
确定双亲结点编号
根据完全二叉树的性质,编号为$i$的结点,其双亲结点的编号为$\lfloor \frac{i}{2} \rfloor$。
代入$i=60$,得双亲结点编号为:
$\lfloor \frac{60}{2} \rfloor = 30$ -
验证选项
选项中A为30,与计算结果一致,因此正确答案为A。