问题
填空题
用数组A[1..n]顺序存储完全二叉树的各结点,则当i>0,且i<= _________时,结点A[i]的右子女是结点A[2i+1],否则结点A[i]没有右子女。
答案
参考答案:(n-1)/2
解析:完全二叉树中除最下面一层外,各层都被结点充满了,每一层结点个数恰是上一层结点个数的2倍。 因此,从一个结点的编号就可以推知它的双亲以及左、右子女结点的编号。当 i≤n/2 时,结点 i 的左子女是结点 2i,否则结点 i 没有左子女。当 i≤(n-1)/2 时,结点 i 的右子女是结点 2i+1,否则结点 i 没有右子女。 当 i≠1 时,结点 i 的双亲是结点 i/2」。