一个包含n个结点的完全二叉树,采用顺序存储方式存储(从下标1开始),若已知结点i的左子结点存在,则其左子结点的下标是多少?
答案解析
核心考点说明:本题考察完全二叉树的顺序存储特性和结点下标之间的关系。完全二叉树的顺序存储中,父节点和子节点的下标存在固定关系,理解此关系是解题关键。
解题思路分析:完全二叉树的顺序存储中,如果父节点下标为i,则其左子节点下标为2i,右子节点下标为2i+1。题目已知左子节点存在,要求左子节点的下标,因此直接使用2i的公式即可。
每个选项的详细分析:
A. 2i:这是完全二叉树中,父节点为i时,其左子节点的下标,当左子节点存在时,这是正确的公式。
B. 2i+1:这是完全二叉树中,父节点为i时,其右子节点的下标。题目要求的是左子节点,因此是错误的。
C. i/2 (向下取整):这是完全二叉树中,子节点为i时,其父节点的下标。与题目要求相反,而且直接i/2不一定是整数,因此错误。
D. (i-1)/2 (向下取整):这是完全二叉树中,子节点为i时,其父节点的下标。与题目要求相反。在完全二叉树中,根节点的下标是1,所以它的父节点是不能通过(i-1)/2得到的,此选项错误。
易错点提醒:要区分父节点找子节点和子节点找父节点的公式,注意完全二叉树的顺序存储特性和下标的起始值(本题下标从1开始)。
正确答案的关键依据:完全二叉树的顺序存储特性,左子节点下标为2i。
正确答案:A