abstractoptimalbst.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * 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 2008
package 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;
	}

}