一个具有 n 个结点的完全二叉树,按层序编号(从1开始,根节点为1),则编号为 i (1 <= i <= n) 的结点的父结点编号是?

答案解析

核心考点说明:本题考察完全二叉树的性质,以及结点编号和父结点编号之间的关系。难点在于如何推导出一般情况下的父节点计算公式。 解题思路分析:完全二叉树的层序编号中,对于结点 i,如果 i > 1,那么它的父节点编号是 (i/2) 向下取整。因为对于每一个节点,其左孩子的编号是 2i,右孩子的编号是 2i+1。反过来推,当 i 是偶数时,其父节点是 i/2,当 i 是奇数时,其父节点是 (i-1)/2。合并起来就是 (i-1)/2 向下取整 每个选项的详细分析: A. i/2:如果 i 是偶数,则正确,例如 4 的父结点为 2。但如果 i 是奇数,则不正确,例如 3 的父结点为 1,而 3/2=1.5。 B. (i-1)/2:如果i是偶数,(i-1)/2 向下取整仍然是 i/2,如果 i 是奇数,则向下取整正好对应 i 的父节点。因此正确。 C. 2i:这是结点 i 的左孩子编号,不是父结点编号。 D. 2i+1:这是结点 i 的右孩子编号,不是父结点编号。 易错点提醒:容易混淆结点 i 的父结点和孩子结点编号的计算公式,需要理清层序编号的规律。 正确答案的关键依据:根据完全二叉树的层序编号规律,推导出父节点编号的计算公式为(i-1)/2,取整。
正确答案:B
随机推荐
开始刷题