数据结构考研分类复习真题 第十章 答案[46]

void Adjust(int T[]int s)

{ //选得最小关键字记录后从叶到根调整败者树选下一个最小关键字

//沿从叶子结点R[s]到根结点T[]的路径调整败者树

t=(s+k)/; //T[t]是R[s]的双亲结点

while(t>)

{ if(R[s]key>R[T[t]]key) s<>T[t]; //s指示新的胜者

t=t/;

}//while

T[]=s;

}//Adjust

void CreateLoserTree(int T[])

{ //建立败者树已知R[]到R[k]为完全二叉树T的叶子结点存有k个关键字沿

//从叶子到根的k条路径将T调整为败者树

R[k]key=MINKEY; //MINKEY是最小关键字

for(i=;i<k;i++) T[i]=k; //设置T中败者的初值

//依次从R[k]R[k]…R[]出发调整败者

for(i=k;k>=;i) Adjust(Ti);

}//CreateLoserTree

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []