最优二叉搜索树c语言

最优二叉搜索树（Optimal Binary Search Tree，简称OBST）是一种特殊的二叉搜索树，它的查找效率比一般的二叉搜索树要高。下面是一个简单的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 计算最优二叉搜索树的函数
int optimalBST(int freq[], int n)
{
    int cost[n][n];

    for (int i = 0; i < n; i++) {
        cost[i][i] = freq[i];
    }

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length + 1; i++) {
            int j = i + length - 1;
            cost[i][j] = INT_MAX;

            for (int k = i; k <= j; k++) {
                int c = ((k > i) ? cost[i][k - 1] : 0) +
                        ((k < j) ? cost[k + 1][j] : 0) +
                        freq[k];

                if (c < cost[i][j]) {
                    cost[i][j] = c;
                }
            }
        }
    }

    return cost[0][n - 1];
}

int main()
{
    int freq[] = {10, 12, 16, 21};
    int n = sizeof(freq) / sizeof(freq[0]);

    printf("最优二叉搜索树的最小代价为：%d\n", optimalBST(freq, n));

    return 0;
}

这里使用了动态规划的思想，先计算出长度为1的子树的代价，再计算出长度为2的子树的代价，直到计算出整棵树的代价。时间复杂度为O(n^3)，空间复杂度为O(n^2)。