optimalbinarysearchtree.java

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

public class OptimalBinarySearchTree {
	public static void optimalBinarySearchTree(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;
		}
		for (int r=0;r<n;r++)
		  for (int i=1;i<=n-r;i++) {
		  	int j=i+r;
		  	w[i][j]=w[i][j-1]+a[j]+b[j];
		  	m[i][j]=m[i+1][j];
		  	s[i][j]=i;
		  	for (int k=i+1;k<=j;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];
		
		/* 计算最优二叉搜索树 */
		optimalBinarySearchTree(a,b,m,s,w);
		
		/* 输出最优搜索树 */
		traceback(s,1,n);		
	}
}