[4,5,19,23,2,8]的最优二叉搜索树，C语言实现源码

下面是一个简单的C语言实现源码：

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

// 二叉搜索树节点结构体
struct Node {
    int key;
    struct Node* left, *right;
};

// 创建一个新的二叉搜索树节点
struct Node* newNode(int key) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

// 计算给定数组中所有元素的加权和
int sum(int freq[], int i, int j) {
    int s = 0;
    for (int k = i; k <= j; k++)
        s += freq[k];
    return s;
}

// 构建最优二叉搜索树
struct Node* optimalBST(int keys[], int freq[], int n) {
    // 构建动态规划表
    int cost[n][n];
    for (int i = 0; i < n; i++)
        cost[i][i] = freq[i];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n-len+1; i++) {
            int j = i + len - 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) +
                        sum(freq, i, j);
                if (c < cost[i][j]) {
                    cost[i][j] = c;
                }
            }
        }
    }

    // 构建二叉搜索树
    struct Node* root = newNode(keys[0]);
    struct Node* parent[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            parent[i][j] = NULL;
        }
    }
    parent[0][0] = root;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n-len+1; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++) {
                struct Node* left = NULL, *right = NULL;
                if (k > i) {
                    left = parent[i][k-1];
                } 
                if (k < j) {
                    right = parent[k+1][j];
                }
                struct Node* node = newNode(keys[k]);
                parent[i][j] = node;
                node->left = left;
                node->right = right;
            }
        }
    }

    return root;
}

// 中序遍历二叉搜索树，输出所有键值
void inorder(struct Node* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

int main() {
    int keys[] = {4, 5, 19, 23, 2, 8};
    int freq[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(keys) / sizeof(keys[0]);
    struct Node* root = optimalBST(keys, freq, n);
    printf("最优二叉搜索树的键值为：");
    inorder(root);
    return 0;
}

这个实现使用动态规划算法来构建最优二叉搜索树，并输出所有键值。