用c语言完成 请完成最优二分检索树的代码

最优二分检索树，也称为哈夫曼树或权值树，是一种特殊的二叉树，它的每个节点都有一个权值，且权值越大的节点离根节点越近。在查找某个元素时，先从根节点开始比较，如果要查找的元素比当前节点的权值小，则进入左子树继续查找；否则进入右子树继续查找。最终找到目标元素或者查找失败。

以下是用 C 语言实现最优二分检索树的代码：

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

/* 二叉树节点结构体 */
typedef struct TreeNode {
    int val;  /* 节点权值 */
    struct TreeNode *left;  /* 左子树 */
    struct TreeNode *right; /* 右子树 */
} TreeNode;

/* 动态规划求最优二分检索树 */
void optimalBST(int *keys, int *freq, int n, int **cost, int **root) {
    /* 初始化二维数组 */
    for (int i = 0; i <= n; i++) {
        cost[i][i] = freq[i];
        root[i][i] = 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;
                c += k < j ? cost[k+1][j] : 0;
                c += freq[k];
                if (c < cost[i][j]) {
                    cost[i][j] = c;
                    root[i][j] = k;
                }
            }
        }
    }
}

/* 递归构造最优二分检索树 */
TreeNode *buildTree(int *keys, int i, int j, int **root) {
    if (i > j) {
        return NULL;
    }
    int k = root[i][j];
    TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));
    node->val = keys[k];
    node->left = buildTree(keys, i, k-1, root);
    node->right = buildTree(keys, k+1, j, root);
    return node;
}

/* 打印二叉树 */
void printTree(TreeNode *root, int level) {
    if (root == NULL) {
        return;
    }
    printTree(root->right, level+1);
    for (int i = 0; i < level; i++) {
        printf("   ");
    }
    printf("%d\n", root->val);
    printTree(root->left, level+1);
}

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

    /* 申请二维数组存储子问题的最优解 */
    int **cost = (int **) malloc(sizeof(int *) * (n+1));
    for (int i = 0; i <= n; i++) {
        cost[i] = (int *) malloc(sizeof(int) * (n+1));
    }

    /* 申请二维数组存储子问题的根节点 */
    int **root = (int **) malloc(sizeof(int *) * (n+1));
    for (int i = 0; i <= n; i++) {
        root[i] = (int *) malloc(sizeof(int) * (n+1));
    }

    /* 动态规划求解最优二分检索树 */
    optimalBST(keys, freq, n, cost, root);

    /* 构造最优二分检索树 */
    TreeNode *rootNode = buildTree(keys, 0, n-1, root);

    /* 打印最优二分检索树 */
    printTree(rootNode, 0);

    /* 释放动态申请的内存 */
    for (int i = 0; i <= n; i++) {
        free(cost[i]);
        free(root[i]);
    }
    free(cost);
    free(root);

    return 0;
}

在这个代码中，我们使用了动态规划算法来求解最优二分检索树。首先，我们申请了两个二维数组 `cost` 和 `root`，其中 `cost[i][j]` 表示从第 `i` 个关键字到第 `j` 个关键字的最小搜索代价，`root[i][j]` 表示从第 `i` 个关键字到第 `j` 个关键字的最优根节点。然后，我们通过自底向上的方式计算出 `cost` 和 `root` 数组。

接下来，我们使用递归的方式构造最优二分检索树。具体地，对于从第 `i` 个关键字到第 `j` 个关键字的子树，我们选择 `root[i][j]` 作为根节点，然后递归构造左右子树。最后，我们打印出构造好的二叉树。

注意，在代码执行结束后，需要释放动态申请的内存，避免内存泄漏。