optiamlbinarytree.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("輸入機率 用,相隔。");
        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]);
        }


        /*  此段為未來要加入key值 先不看
            System.out.println("輸入KEY值 用,相隔。");
            String inputkey = sc.nextLine();
            String[] inputKeyArray = inputkey.split(",");
            int[] inputkeyInt = new int[inputKeyArray.length];
            for(int i = 0;i < inputKeyArray.length;i++) {
                inputkeyInt[i] = Integer.parseInt(inputKeyArray[i]);
            }
            Arrays.sort(inputkeyInt);
        */


        int n = inputFrequency.length ;
        //Root表
        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);

    }

    //演算法
    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) {//檢查是否為葉子
            Node sub = new Node();
            sub.node = array[leftpivot][rightpivot];
            sub.level = level;
            i++;
            sub.index = i;
            return sub;
        }

        int subRoot = array[leftpivot][rightpivot];//設subRoot
        node.node = array[leftpivot][rightpivot];
        node.level = level;
        level ++;//層數加1

        int new_leftpivot = subRoot-1;//子數的左區間
        int new_rightpivot = subRoot+1;//右區間


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

        i++;//記node前面有幾個node,為了印出tree
        node.index = i;

        //右子樹
        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;
            }
            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);
            }
        }
    }


}