c++实现构造最优二分检索树
时间: 2023-09-18 17:15:55 浏览: 81
下面是 C++ 实现构造最优二分检索树的示例代码,其中假设有 n 个关键字和 n+1 个虚拟关键字:
```c++
#include <iostream>
using namespace std;
const int MAXN = 100;
int w[MAXN]; // 关键字权值
int v[MAXN + 1][MAXN + 1]; // 子问题的最优解
int root[MAXN + 1][MAXN + 1]; // 子问题的最优解对应的根节点
// 构造最优二分检索树
void optimal_bst(int n) {
// 初始化子问题的最优解
for (int i = 1; i <= n + 1; i++) {
v[i][i - 1] = 0;
}
// 枚举子问题规模
for (int len = 1; len <= n; len++) {
// 枚举子问题的起点
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
v[i][j] = INT_MAX;
// 枚举根节点
for (int k = i; k <= j; k++) {
int cost = v[i][k - 1] + v[k + 1][j] + w[k];
if (cost < v[i][j]) {
v[i][j] = cost;
root[i][j] = k;
}
}
}
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
optimal_bst(n);
cout << "最小代价为:" << v[1][n] << endl;
return 0;
}
```
在上述代码中,数组 `v` 存储子问题的最优解,数组 `root` 存储子问题的最优解对应的根节点。函数 `optimal_bst` 利用动态规划的思想,从子问题规模为 1 的情况开始,逐步扩大子问题规模,直到求解整个问题。最终,函数输出最优解 `v[1][n]`。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)