/* * Copyright (C) 2003-2008 Wang Pengcheng <wpc0000@gmail.com> * Permission is granted to copy, distribute and/or modify this * document under the terms of the GNU Free Documentation License, * Version 2.0 or any later version published by the Free Software Foundation; * with no Invariant Sections. * You may obtain a copy of the License at *   http://www.gnu.org/licenses/lgpl.txt *///19 Feb 2008package cn.edu.whu.iss.algorithm.unit15.optimalbst;public abstract class AbstractOptimalBST implements GetOptimalBSTInfor {	protected double[] p;	protected double[] q;	protected double ans;	protected int[][] root;	protected int n;		public AbstractOptimalBST(double[] p, double[] q) {		super();		this.p = p;		this.q = q;		n = p.length;	}	public AbstractOptimalBST() {		super();		n = 0;	}	public String getOptimalBST(double[] p, double[] q) {		this.p = p;		this.q = q;		n = p.length;		return getOptimalBST();	}	public String getOptimalBST() {		optimalBST();		return constructOptimalBST();	}		private String constructOptimalBST(){		int r = root[1][n];		String s = "K"+r+" is the root\n";		s+=printOptimalBST(r,"left",1,r-1);		s+=printOptimalBST(r, "right", r+1, n);		return s;	}		private String printOptimalBST(int r,String s,int i,int j){		String a = "";		if(i==j){			int t = root[i][j];			a+="K"+t+" is the "+s+" child of K"+r+"\n";			a+="D"+(i-1)+" is the left child of K"+t+"\n";			a+="D"+(i)+" is the right child of K"+t+"\n";		}else if(i>j){			a+="D"+(j)+" is the right child of K"+r+"\n";		}else{			int t = root[i][j];			a+="K"+t+" is the "+s+" child of K"+r+"\n";			a+=printOptimalBST(t, "left", i, t-1);			a+=printOptimalBST(t, "right", t+1, j);		}		return a;	}	public double optimalBST(double[] p, double[] q) {		this.p = p;		this.q = q;		n = p.length;		ans = optimalBST();		return ans;	}}