obst.java

《算法设计与分析》王晓东编著

public class OBST {
	
	public static void obst(double []a,double []b,double [][]m,
			                int [][]s,double [][]w)
	{
		int n=a.length-1;
		for (int i=0;i<=n;i++) {
			w[i+1][i]=a[i];
			m[i+1][i]=0;
			s[i+1][i]=0;
		}
		for (int r=0;r<n;r++)
		  for (int i=1;i<=n-r;i++) {
		  	int j=i+r,
			    i1=s[i][j-1]>i?s[i][j-1]:i,
			    j1=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 (int k=i1+1;k<=j1;k++) {
				double t=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];			    		
		  }
	}

	/* 用形如: 
	 *   根(左子树,右子树) 
	 * 的递归的表达式形式输出最忧二叉搜索树*/
	public static void traceback(int [][]s,int i,int j)
	{
		if (i>j)
		{
			System.out.print("null");
			return;			
		}
			
		int k=s[i][j];		
		System.out.print(k);
		
		if (i==j)	return ;
		
		System.out.print("(");
		traceback(s,i,k-1);
		System.out.print(",");
		traceback(s,k+1,j);
		System.out.print(")");
	}
	
	public static void main(String[] args) {
		/* 初始化概率数组a,b */
		double a[]=new double[]{0.1,0.05,0.15,0.2,0.05};
		double b[]=new double[]{0,0.2,0.05,0.15,0.05};
		
		int n=a.length-1;
		
		double [][]m =new double[n+2][n+2];
		int [][]s = new int[n+2][n+2]; /* s[i][j]保存最优子树T(i,j)的根结点 */
		double [][]w = new double[n+2][n+2];
		
		/* 计算最优二叉搜索树 */
		obst(a,b,m,s,w);
		
		/* 输出最优搜索树 */
		traceback(s,1,n);		
	}
}