optimalTree.java

import java.util.*;

public class Main {
    static double minAvg;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("type in frequency from the keyboard, use , to split.。");
        String input = sc.nextLine();
        String[] inputArray = input.split(",");
        double[] inputFrequency= new double[inputArray.length];

        for(int i = 0;i < inputFrequency.length;i++) {
            inputFrequency[i] = Float.parseFloat(inputArray[i]);
        }

        int n = inputFrequency.length ;
        //Root table
        int [][]R = new int[n+1][n+1];

        double A [][] = optst(n,inputFrequency,R);


        showAtable(A);
        System.out.println();
        System.out.println();
        showRtable(R);
        System.out.println();
        System.out.println();

        new BinarySearchTree().showRTableTree(R);

    }

    //algorithm, find min cost
    static double[][] optst(int n, double p[],int R[][]){
        int i,j,diagonal;

        double [][]A = new double[n+1][n+1];

        for (i=1; i<=n; i++) {
            A[i-1][i-1] = 0;
            A[i-1][i] = p[i-1];

            R[i-1][i] = i;
            R[i-1][i-1] = 0;
        }

        for(diagonal=1; diagonal<=n-1; diagonal++) {
            for(i=1; i<=n-diagonal; i++) {
                j = i + diagonal;
                double minimum = Double.MAX_VALUE;
                double sum = 0;
                int minr = 0;

                for(int k=i; k<=j; k++) {
                    if (A[i-1][k-1]+A[k][j] < minimum) {
                        minimum = A[i-1][k-1]+A[k][j];
                        minr = k;
                    }
                    sum += p[k-1];
                }
                A[i-1][j] = minimum + sum;
                R[i-1][j] = minr;
            }
        }

        return A;
    }


    static void showAtable(double a[][]) {
        for(int i=0;i<a.length;i++)
        {
            for(int z=0;z<a.length;z++) {
                System.out.printf("%.3f"+"\t",a[i][z]);

            }
            System.out.println();
        }

    }

    static void showRtable(int a[][]) {
        for(int i=0; i<a.length; i++) {
            for(int j=0; j<a[0].length;j++) {
                System.out.print(String.valueOf(a[i][j]) + "\t\t");
            }
            System.out.println();
        }
    }
}


class BinarySearchTree {


    public void showRTableTree(int array[][]) {

        Node node = new Node();
        build(array, node, 1, array.length-1, 0, -1);
        node.showTree(node);
    }
    Node build(int array[][], Node node, int leftpivot, int rightpivot, int level, int i) {
        if (leftpivot == rightpivot) {//Check if it is a leaf
            Node sub = new Node();
            sub.node = array[leftpivot][rightpivot];
            sub.level = level;
            i++;
            sub.index = i;
            return sub;
        }

        int subRoot = array[leftpivot][rightpivot];//sub Root
        node.node = array[leftpivot][rightpivot];
        node.level = level;
        level ++;

        int new_leftpivot = subRoot-1;
        int new_rightpivot = subRoot+1;


        //find left sub tree
        Node newTree = new Node();
        if (new_leftpivot>=leftpivot) {
            //將傳的左子樹放入次樹的左子樹
            node.leftNode = build(array, newTree, leftpivot, new_leftpivot, level, i);
            i = node.leftNode.index;
        }

        i++;//has several nodes before it.
        node.index = i;

        //find right sub tree
        if (new_rightpivot<=rightpivot) {
            node.rightNode = build(array, newTree, new_rightpivot, rightpivot, level, i);
            i = node.rightNode.index;
        }


        return node;
    }


    class Node {
        Node leftNode ;
        Node rightNode;

        int node = 0;
        int level = 0;
        int index = 0;

        int nowlevel = 0;


        void showTree(Node node) {
            if (nowlevel != node.level) {
                System.out.println();
                nowlevel = node.level;
            }
            //according to this node has how many nodes before it
            for (int i = 0; i< node.index; i++) {
                System.out.print("\t\t");
            }
            System.out.print(node.node);

            if (node.leftNode != null) {
                showTree(node.leftNode);
            }

            if (node.rightNode != null) {
                showTree(node.rightNode);
            }
        }
    }


}