Question

I need to build an optimal binary search tree with an array of strings and frequency received from the user.in C

Answer 1

PLEASE GIVE IT A THUMBS UP

#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 costbst(int freq[], int i, int j)
{
if (j < i)   
return 0;
if (j == i)
return freq[i];

int funcsum = sum(freq, i, j);
int min = INT_MAX;

for (int r = i; r <= j; ++r)
{
int cost = costbst(freq, i, r-1) +
costbst(freq, r+1, j);
if (cost < min)
min = cost;
}

return min + funcsum;
}

int binary_optimal(char keys[3][10], int freq[], int n)
{
return costbst(freq, 0, n-1);
}

int main()
{
char keys[3][10];
int freq[3],i;
for(i=0;i<3;i++){
printf("Enter key and freq for %d\n",i+1 );
scanf("%s",keys[i]);
scanf("%d",&freq[i]);
}
printf("Optimal binary tree cost is %d ", binary_optimal(keys, freq, 3));
return 0;
}