CSP-J 2022 第一轮 第 8 题：完全二叉树数组存储求兄弟与子节点位置

题目

一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

选项

• A. $8$、$18$
• B. $10$、$18$
• C. $8$、$19$
• D. $10$、$19$

答案

C

题解

选 C：$8$、$19$。

完全二叉树按层从左到右存入数组，根结点下标为 $1$ 时，下标为 $i$ 的结点：

• 左子结点下标为 $2i$；
• 右子结点下标为 $2i+1$；
• 偶数下标的结点是左孩子，兄弟下标为 $i+1$；奇数下标的非根结点是右孩子，兄弟下标为 $i-1$。

因此，第 $9$ 个位置的结点是右孩子：

• 兄弟结点位置：$9-1=\boxed{8}$；
• 右子结点位置：$2\times9+1=\boxed{19}$。