作业10-最优查找树.docVIP

十、最优二叉查找树 1.算法描述 begin for i 0 until do begin ; ; end; for L 1 until n do for i0 until n-L do begin ji+L ; let m be a value of k, ik=j,for which is minimum end end procedure BuildTree(i,j) begin create vertex v[i][j], the root of T[i][j] label v[i][j] by r[i][j] let m be the subscript of r[i][j] if im-1 then make BuildTree(i,m-1) the left subtree of v[i][j]; if mj then make BuildTree(m,j) the right subtree of v[i][j] end 算法复杂度： 2.算法实现 int Prepare( KeyType a[],KeyType P[],KeyType Q[], KeyType w[][N+1],KeyType c[][N+1],KeyType r[][N+1], KeyType len) { int step,start,k,end,m; KeyType min,temp; step=0; //初始化，步长为 0 时 for(start=0; start=len; start++) { w[start][start]=Q[start]; c[start][start]=0; } //计算1 ~ N行 for(step=1; step=len; step++) { for(start=0;start=len-step; start++) { end=start+step; //计算w[start][end] w[start][end]=w[start][end-1]+P[end]+Q[end]; //计算使c[start][k]+c[k][end]最小的k值m min=MIN_INIT; for(m=0,k=start+1; k=end; k++) { temp = c[start][k-1]+c[k][end]; if(temp=min) { min=temp; m=k; } } //计算c[start][end] r[start][end] c[start][end]=w[start][end]+c[start][m-1]+c[m][end]; r[start][end]=a[m-1]; } } } /************************************ * 构造最优查找二叉树 ***********************************/ void BuildTree(VertexType** T,int i,int j, KeyType w[][N+1],KeyType c[][N+1],KeyType r[][N+1]) { int m; (*T)=(VertexType*)malloc(sizeof(VertexType)); if(NULL==(*T)) { printf(memery error!\n); exit(0); } (*T)-value=m=r[i][j]; (*T)-lchild=(*T)-rchild=NULL; //递归调用 if(im-1) BuildTree(((*T)-lchild),i,m-1,w,c,r); if(mj) BuildTree(((*T)-rchild),m,j,w,c,r); } 3.测试样例 a1, a2, a3, a4 P={4,2,1,1}, Q={2,3,1,1,1}; 4.结果输出