用数组A[1..n]顺序存储完全二叉树的各结点,则当i>0,且i<=【】时,结点A[i]的右子女是结点A[2i＋1],否

Question

用数组A[1..n]顺序存储完全二叉树的各结点，则当i＞0，且i＜=【 】时，结点A[i]的右子女是结点A[2i+1]，否则结点A[i]没有右子女。

Answer 1

正确答案：(n-1)/2
(n-1)/2 解析：完全二叉树删除最下面一层外，各层都被结点充满了，每一层结点个数恰是上一层结点个数的2倍。因此，从一个结点的编号就可以推知它的双亲以及左、右子女结点的编号。当i≤n/2时，结点i的左子女是结点2i，否则结点i没有左子女。当i≤(n-1)/2时，结点i的右子女是结点2i+1，否则结点i没有右子女。当i≠1时，结点i的双亲是结点[i/2]。