算法导论15.5-1答案

题目：算法导论第二版 P216 15.5-1

package introductionToAlgorithms.dp;

public class ConstructOprimalBST {
	private int[][] root={{1,1,2,2,2},{0,2,2,2,4},
				{0,0,3,4,5},{0,0,0,4,5},{0,0,0,0,5}};
	
	public void constructOptimalBST(int left,int right){
		if(left == 0 && right == root.length-1) {
			System.out.println("k[" + root[left][right]+"] is the root");
		}
		if(left < right) {
			int r = root[left][right]-1;
			System.out.println("k[" + root[left][r-1]+"] is the left child of k[" + (r+1) + "]");
			constructOptimalBST(left,r-1);
			
			if(r  < right ) //右孩子不是k[i]，而是d[i]，不用在这里打印
				System.out.println("k[" + root[r+1][right]+"] is the right child of k[" + (r+1) +"]");
			constructOptimalBST(r+1,right);
		}else if(left == right) {
			System.out.println("d[" + left+"] is the left child of k[" + (left+1) +"]");	
			System.out.println("d[" + (left+1)+"] is the right child of k[" + (left+1) +"]");			
		}else {
			System.out.println("d[" + left +"] is the right child of k[" + (right+1) + "]");
		}
		
	}

	public static void main(String[] args) {
		ConstructOprimalBST c = new ConstructOprimalBST();
		c.constructOptimalBST(0,c.root.length-1);
	}

}