动态规划之最优二叉搜索树 -电脑资料

/* * 最优二叉搜索树 */public class OptimalBST {	private final int MAX=10000;	private final int SCALE = 5;			//树的规模	private double[][]  e= null;			//e[i][j]表示树ki..kj的期望代价	private double[][]  w= null;			//子树期望代价增加值	private int[][]  root=null;				//记录子树的根	private double[] p = {0,0.15,0.10,0.05,0.10,0.20};	//k1..k5的概率	private double[] q = {0.05,0.10,0.05,0.05,0.05,0.10};	//d1..d5的概率		public static void main(String[] args) {				OptimalBST bst = new OptimalBST();		obst.compute();					//最优二叉搜索树		obst.print(1, obst.SCALE, 0);		}		public OptimalBST() {		e = new double[SCALE+2][SCALE+1];		w = new double[SCALE+2][SCALE+1];		root = new int[SCALE+2][SCALE+1];			}		//计算得到最优二叉搜索树期望代价	private void compute() {		for(int i=1;i<=SCALE+1;i++) {			e[i][i-1] = q[i-1];			w[i][i-1] = q[i-1];		}		for(int len=1;len<=SCALE;len++) {			for(int i=1;i<=SCALE-len+1;i++) {				int j=i+len-1;				e[i][j] = MAX;				w[i][j] = w[i][j-1] + p[j] + q[j];				for(int r=i;r<=j;r++) {					double t = e[i][r-1] + e[r+1][j]+w[i][j];					if(t< e[i][j]) {						e[i][j] = t;						root[i][j] = r;					}				}			}		}		}		//打印最优二叉查找树的结构	void print(int i,int j,int r)	{		int rootChild = root[i][j];			//子树根节点		if (rootChild == root[1][SCALE]) {			//输出整棵树的根			System.out.println("k" + rootChild + "是根");			print(i,rootChild - 1,rootChild);			print(rootChild + 1,j,rootChild);			return;		}		if (j< i - 1) {			return;		}		else if (j == i - 1) { //遇到虚拟键			if (j< r) {				System.out.println("d" + j + "是k" + r + "的左孩子");			}			else				System.out.println("d" + j + "是k" + r + "的右孩子");			return;		}		else {      //遇到内部结点			if (rootChild< r) {				System.out.println("k" + j + "是k" + r + "的左孩子");			}			else {				System.out.println("k" + j + "是k" + r + "的右孩子");			}		}		print(i,rootChild - 1,rootChild);		print(rootChild + 1,j,rootChild);	}	}

    运行结果与算法导论上一致：

k2是根k1是k2的左孩子d0是k1的左孩子d1是k1的右孩子k5是k2的右孩子k4是k5的左孩子k3是k4的左孩子d2是k3的左孩子d3是k3的右孩子d4是k4的右孩子d5是k5的右孩子