用java代码写最优二分检索树

二分搜索树（Binary Search Tree）是一种基于二分查找的数据结构，它的左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。最优二分搜索树（Optimal Binary Search Tree）也称为哈夫曼树（Huffman Tree），是一种带权路径最短的二叉树，它的带权路径长度最小，也就是说，它的各个叶子节点的深度加上其权值的乘积之和最小。

以下是用Java代码实现最优二分搜索树的示例：

public class OptimalBST {
    private static final int INF = Integer.MAX_VALUE;
    private static int n;
    private static int[] p;
    private static int[] q;
    private static int[][] w;
    private static int[][] e;
    private static int[][] root;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入节点数：");
        n = scanner.nextInt();

        p = new int[n + 1];
        q = new int[n + 1];

        System.out.println("请输入节点的概率：");
        for (int i = 1; i <= n; i++) {
            p[i] = scanner.nextInt();
        }

        System.out.println("请输入虚拟节点的概率：");
        for (int i = 0; i <= n; i++) {
            q[i] = scanner.nextInt();
        }

        w = new int[n + 2][n + 2];
        e = new int[n + 2][n + 2];
        root = new int[n + 1][n + 1];

        optimalBST();

        System.out.println("最优二叉搜索树的带权路径长度为：" + e[1][n]);
    }

    private static void optimalBST() {
        // 初始化 w、e、root 数组
        for (int i = 1; i <= n + 1; i++) {
            w[i][i - 1] = q[i - 1];
            e[i][i - 1] = q[i - 1];
        }

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                e[i][j] = INF;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                for (int k = i; k <= j; k++) {
                    int t = e[i][k - 1] + e[k + 1][j] + w[i][j];
                    if (t < e[i][j]) {
                        e[i][j] = t;
                        root[i][j] = k;
                    }
                }
            }
        }
    }
}

该代码中，使用了动态规划的思想，通过计算每个子树的带权路径长度，逐步求得最优二叉搜索树的带权路径长度。在计算过程中，使用了一个 root 数组，记录了每个子树的根节点。最后，根据 root 数组和节点的概率，可以构建出最优二叉搜索树。