C program for finding Optimal Binary Search Tree

//Program for OBST#include<stdio.h>float e[6][6],w[6][6],t;int root[6][6];float p[6],q[6];void obst(int i, int j){	int value = root[i][j];	if(i==value) 	{ 		printf("left child of k%d is d%d\n",value,value-1); 	} 	else 	{ 		printf("left child of k%d is k%d\n",value,root[i][value-1]);		obst(i,value-1);	}	if(j==value)	{		printf(" right child of k%d is d%d\n",value,value);	}	else	{		printf(" right child of k%d is k%d\n",value,root[value+1][j]);		obst(value+1,j);	}}int main(){p[1]=0.15;p[2]=0.10;p[3]=0.05;p[4]=0.10;p[5]=0.2;q[0]=0.05;q[1]=0.10;q[2]=0.05;q[3]=0.05;q[4]=0.05;q[5]=0.1;int l,i,n=5,r,j;for(i=1;i<=(n+1);i++){	e[i][i-1]=q[i-1];	w[i][i-1]=q[i-1];}for(l=1;l<=n;l++){	for(i=1;i<=(n-l+1);i++)	{		j=i+l-1;		e[i][j]=10000;		w[i][j]=w[i][j-1]+p[j]+q[j];		for(r=i;r<=j;r++)		{			t=e[i][r-1]+e[r+1][j]+w[i][j];			if(t<e[i][j])			{				e[i][j]=t;				root[i][j]=r;			}		}	}}printf("w :\n");for(i=1;i<=(n+1);i++){	for(j=i-1;j<=(n);j++)	{		printf("%f  ",w[i][j]);	}	printf("\n");}printf("e:\n");for(i=1;i<=(n+1);i++){	for(j=i-1;j<=n;j++)	{		printf("%f  ",e[i][j]);	}	printf("\n");}printf("Root \n");for(i=1;i<=n;i++){	for(j=i;j<=n;j++)	{		printf("%d  ",root[i][j]);	}	printf("\n");}printf("Root is k%d\n",root[1][n]);obst(1,n);}

 Output:

optimal binary search tree

Comments

Popular posts from this blog

MATLAB code for Circular Convolution using Matrix method

Positive number pipe in angular 2+