Thursday, October 7, 2010

C Programming - Program to find optimal binary search tree using dynamic programming

ALGORITHM

C Programming - Program to find optimal binary search tree using dynamic programming


#include
#include

# define INFINITE 999

void fnDisplay(float afA[7][7],int iN)
{
int iI,iJ;
for(iI=1;iI<=iN+1;iI++)
{
for(iJ=0;iJ<=iN;iJ++)
if(iJ>=iI-1)
printf(" %4.2f ",afA[iI][iJ]);
else
printf(" ");
printf("\n");
}
}

void fnTree(int iFirst,int iLast,float afRoot[7][7])
{
int iK;
if(iFirst>iLast || iLast==0)
return;
iK=afRoot[iFirst][iLast];
printf(" %d ",iK);
fnTree(iFirst,iK-1,afRoot);
fnTree(iK+1,iLast,afRoot);
}

void fnOptimalBST(float afFrequency[7],int iN)
{
int iI,iJ,iK,iS,iD,iRootmin;
float afMain[7][7],afRoot[7][7],fSum,fMin;
for(iI=1;iI<=iN;iI++)
{
afMain[iI][iI-1]=0;
afMain[iI][iI]=afFrequency[iI];
afRoot[iI][iI]=iI;
}
afMain[iN+1][iN]=0;
for(iD=1;iD {
for(iI=1;iI<=iN-iD;iI++)
{
iJ=iI+iD;
fMin=INFINITE;
for(iK=iI;iK<=iJ;iK++)
if((afMain[iI][iK-1]+afMain[iK+1][iJ]) {
fMin=afMain[iI][iK-1]+afMain[iK+1][iJ];
iRootmin=iK;
}
afRoot[iI][iJ]=iRootmin;
fSum=afFrequency[iI];
for(iS=iI+1;iS<=iJ;iS++)
fSum+=afFrequency[iS];
afMain[iI][iJ]=fMin+fSum;
}
}
printf("\n\nMain table:\n");
fnDisplay(afMain,iN);
printf("\n\nRoot table:\n");
fnDisplay(afRoot,iN);
printf("\n\nOptimal Binary search tree is :\n\t");
fnTree(1,iN,afRoot);
printf("\n\nCost is %f",afMain[1][iN]);
}

void main()
{
int iI,iN;
float afFrequency[7];
clrscr();
printf("Enter the no of nodes : ");
scanf("%d",&iN);
printf("\nEnter the frequency of the nodes : \n");
for(iI=1;iI<=iN;iI++)
scanf("%f",&afFrequency[iI]);
fnOptimalBST(afFrequency,iN);
getch();
}


/* OUTPUT:
-------
How many nodes: 5

Enter the search probabilities:
.1 .2 .3 .2 .2


Main table:
0.00 0.10 0.40 1.00 1.40 2.00
0.00 0.20 0.70 1.10 1.70
0.00 0.30 0.70 1.20
0.00 0.20 0.60
0.00 0.20
0.00


Root table:
0.00 1.00 2.00 2.00 3.00 3.00
0.00 2.00 3.00 3.00 3.00
0.00 3.00 3.00 4.00
0.00 4.00 4.00
0.00 5.00
0.00


Optimal Binary search tree is :
3 2 1 4 5

Cost is 2.000000
*/


Comment and discuss your doubts

No comments:

Post a Comment