问答题
设记录R[i]的关键字为R[i]．KEY(1≤i≤k)，树结点T[i](1≤i≤k-1)指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[i](1≤f≤k)的败者树，要求除R[1．．k]和T[0一K-1]以外，只用O(1)辅助空间。【东南大学1995九(15分)】
【正确答案】正确答案：void Adjust(int T[]，int s) {／／选得最小关键字记录后，沿从叶子结点R[s]到根结点T[0]的路径调整败者树 t=(s+k)／2； ／／T[t]是R[s]的双亲结点 while(t>0) {if(R[s]．key>R IT[t\]\]．key) s<一一>T[t]； ／／s指示新的胜者 t=t／2； }／／while T[0]=s； }／／Adjust void CreateL08erTree(int T[]) {／／R[0]到R[k一1]为完全二叉树T的叶子结点，本算法建立败者树 R[k]．key=MINKEY； ／／MINKEY是与题中要求的关键字类型相同的机器最小数 for(i=0；i=0 ； i—-) Adjust(T，i)； }／／createL0serTree
【答案解析】