最优二叉检索树c++实现

最优二叉搜索树，又称为哈夫曼树，是一种特殊的二叉树。它的特点是，对于任意一个节点，它的左子树都比它小，它的右子树都比它大，同时，整棵树的带权路径长度最小。以下是一个使用C语言实现最优二叉搜索树的示例代码：

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

// 定义最大值
#define MAX 99999

// 定义节点结构体
typedef struct _node {
    int key;            // 节点值
    int weight;         // 权重
    struct _node *left; // 左子树指针
    struct _node *right;// 右子树指针
} Node;

// 打印二叉树
void printTree(Node *root, int space) {
    if (root == NULL) {
        return;
    }
    space += 5;
    printTree(root->right, space);
    printf("\n");
    for (int i = 5; i < space; i++) {
        printf(" ");
    }
    printf("%d\n", root->key);
    printTree(root->left, space);
}

// 构造最优二叉搜索树
void constructOptimalBST(int keys[], int weights[], int n) {
    Node *root[n+1];
    int cost[n+1][n+1];
    int sum[n+1];

    for (int i = 0; i < n; i++) {
        // 初始化叶子节点
        root[i] = (Node *)malloc(sizeof(Node));
        root[i]->key = keys[i];
        root[i]->weight = weights[i];
        root[i]->left = NULL;
        root[i]->right = NULL;
        // 初始化cost数组和sum数组
        cost[i][i] = weights[i];
        sum[i] = weights[i];
        for (int j = i+1; j < n; j++) {
            cost[i][j] = MAX;
        }
    }
    sum[n] = 0;
    cost[n][n] = 0;

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n-len; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++) {
                int c = ((k > i) ? cost[i][k-1] : 0) + ((k < j) ? cost[k+1][j] : 0) + sum[j+1] - sum[i];
                if (c < cost[i][j]) {
                    cost[i][j] = c;
                    root[i][j] = (Node *)malloc(sizeof(Node));
                    root[i][j]->key = keys[k];
                    root[i][j]->weight = weights[k];
                    root[i][j]->left = (k > i) ? root[i][k-1] : NULL;
                    root[i][j]->right = (k < j) ? root[k+1][j] : NULL;
                }
            }
        }
    }
    printf("最优二叉搜索树的代价为：%d\n", cost[0][n-1]);
    printf("最优二叉搜索树的结构如下：\n");
    printTree(root[0][n-1], 0);
}

int main() {
    int keys[] = {10, 12, 20, 30};
    int weights[] = {34, 8, 50, 10};
    int n = sizeof(keys) / sizeof(keys[0]);
    constructOptimalBST(keys, weights, n);
    return 0;
}

以上代码使用动态规划的方法构造最优二叉搜索树，时间复杂度为O(n^3)，空间复杂度为O(n^2)。