最优二叉探索树c语言代码极其伪代码
时间: 2024-06-20 12:03:52 浏览: 12
最优二叉搜索树是指在所有可能的二叉搜索树中,查找所有节点所需的平均比较次数最小的二叉搜索树。下面是该算法的C语言代码和伪代码:
C语言代码:
```c
#include <stdio.h>
#include <limits.h>
int sum(int freq[], int i, int j)
{
int s = 0;
for (int k = i; k <= j; k++)
s += freq[k];
return s;
}
int optimalSearchTree(int keys[], int freq[], int n)
{
int cost[n][n];
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
for (int L = 2; L <= n; L++)
{
for (int i = 0; i <= n - L + 1; i++)
{
int j = i + L - 1;
cost[i][j] = INT_MAX;
for (int r = i; r <= j; r++)
{
int c = ((r > i) ? cost[i][r - 1] : 0) +
((r < j) ? cost[r + 1][j] : 0) +
sum(freq, i, j);
if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[n - 1];
}
int main()
{
int keys[] = {10, 12, 20};
int freq[] = {34, 8, 50};
int n = sizeof(keys)/sizeof(keys);
printf("Cost of Optimal BST is %d", optimalSearchTree(keys, freq, n));
return 0;
}
```
伪代码:
```
optimalSearchTree(keys[], freq[], n)
cost[n][n]
for i in range(0,n)
cost[i][i] = freq[i]
for L in range(2,n+1)
for i in range(0,n-L+1)
j = i+L-1
cost[i][j] = INT_MAX
for r in range(i,j+1)
c = (cost[i][r-1] if r>i else 0) +
(cost[r+1][j] if r<j else 0) +
sum(freq, i, j)
if c < cost[i][j]
cost[i][j] = c
return cost[n-1]
```
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)