### Data Structure Program to build optimal binary search tree

/* pgm to build optimal binary search tree*/
#include<stdio.h>
#define INF 10000
int root[10][10];//{0};
float p[10],c[10][10];//={0};
int mark[25],used[25],r[25];
int n;
char val[20];
void buildtree()
{
int i,j,d,k,kmin;
float sum,min;
/* initial configuration*/
for(i=1;i<=n;i++)
{
c[i][i]=p[i];
c[i][i-1]=0;
root[i][i]=i;
}
c[n+1][n]=0;
//=================
for(d=1;d<n;d++)
for(i=1;i<=n-d;i++)
{
j=i+d;
min=INF;
for(k=i;k<=j;k++)
if(c[i][k-1]+c[k+1][j] < min)
{
min=c[i][k-1]+c[k+1][j];
kmin=k;
}
root[i][j]=kmin;
sum=0;
for(k=i;k<=j;k++)
sum+=p[k];
c[i][j]=sum+min;
}
}
void printRoot()
{
int i,j;
clrscr();
printf("\n\n\t\tPROB MATRIX\n\n");
for(i=1;i<=n+1;i++,printf("\n"))
for(j=0;j<=n;j++)
printf("\t%.2f",c[i][j]);
printf("\n\n\t\tROOT MATRIX\n\n");
for(i=1;i<=n+1;i++,printf("\n"))
for(j=0;j<=n;j++)
printf("\t%d",root[i][j]);
}
void trace(int f,int i,int j)
{
int rt,lt;
r[f]=root[i][j];
used[f]=1;
mark[r[f]]=1;
rt=2*f+2;
lt=2*f+1;
if(r[f]>1 && !mark[root[i][r[f]-1]])
trace(lt,i,r[f]-1);//left sub tree
if(r[f]<n && !mark[root[r[f]+1][j]])
trace(rt,r[f]+1,j);//right sub tree
}
void print(int i,int level)
{
if(used[i])
{
print(2*i+2,level+1);
// if(r[i])
printf("\n%*c",4*level,val[r[i]]);
print(2*i+1,level+1);
}
}
void main()
{
int i,j,node[10];
clrscr();
printf("\n\n\t\tOPTIMUM BINARY SEARCH TREE\n\n");
printf("\t\tEnter the no. of nodes in the tree : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
val[i]=65+i-1;
node[i]=i;
printf("\n\tEnter the Node %d probability : ",i);
scanf("%f",&p[i]);
}
buildtree();
printRoot();
trace(0,1,n);
printf("\n\t\tOPTIMAL BINARY SEARCH TREE\n");
print(0,1);
// maketree(n);
getch();
}