最优二叉搜索树.doc

#include""#definemax50voidOBST(intn,inta[],intb[],intm[][max],ints[][max]){intw[max][max];for(inti=0;i<=n;i++){w[i+1][i]=a[i];m[i+1][i]=0;s[i+1][i]=0;}for(intr=0;r<n;r++)for(i=1;i<=n-r;i++){intj=i+r;inti1=s[i][j-1]>i?s[i][j-1]:i;intj1=s[i+1][j]>i?s[i+1][j]:j;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i1-1]+m[i1+1][j];s[i][j]=i1;for(intk=i1+1;k<=j1;k++){intt=m[i][k-1]+m[k+1][j];if(t<=m[i][j]){m[i][j]=t;s[i][j]=k;}}m[i][j]+=w[i][j];printf("w[%d][%d]=%d",i,j,w[i][j]);printf("m[%d][%d]=%d",i,j,m[i][j]);printf("s[%d][%d]=%d",i,j,s[i][j]);printf("\n");}}voidmain(){voidOBST(intn,inta[],intb[],intm[][max],ints[][max]);intn,a[max],b[max],m[max][max],s[max][max],i,j;printf("请输入n的值:\nn=");scanf("%d",&n);printf("\nb={");for(i=1;i<=n;i++)scanf("%d",&b[i]);printf("}\na={");for(i=0;i<=n;i++)scanf("%d",&a[i]);printf("}\n");OBST(n,a,b,m,s);}