OBST C program

       /*  OPTIMAL BINARY SEARCH TREE*/

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void get_data();

int min_value(int i,int j);

void obst();

void build_tree();

int p[SIZE];

int q[SIZE];

int  a[SIZE];

int w[SIZE][SIZE];

int c[SIZE][SIZE];

int r[SIZE][SIZE];

int n;

void get_data()

{

       int i;

       clrscr();

       printf("\n optimal binary search tree\n");

       printf("\n enter no of nodes\n");

       scanf("%d",&n);

       printf("\n enter data as......\n");

       for(i=1;i<=n;i++)

       {

              printf("\n a[%d]",i);

              scanf("%d",&a[i]);

       }

       for(i=1;i<=n;i++)

       {

              printf("\n p[%d]",i);

              scanf("%d",&p[i]);

       }

       for(i=0;i<=n;i++)

       {

              printf("\n q[%d]",i);

              scanf("%d",&q[i]);

       }

}

int min_value(int i,int j)

{

       int m,k;

       int minimum=32000;

       for(m=r[i][j-1];m<=r[i+1][j];m++)

       {

              if(c[i][m-1]+c[m][j]<minimum)

              {

                     minimum=c[i][m-1]+c[m][j];

                     k=m;

              }

       }

       return k;

}

void obst()

{

       int i,j,k,l,m;

       for(i=0;i<n;i++)

       {

              w[i][i]=q[i];

              r[i][i]=c[i][i]=0;

              w[i][i+1]=q[i]+q[i+1]+p[i+1];

              r[i][i+1]=i+1;

              c[i][i+1]=q[i]+q[i+1]+p[i+1];

       }

       w[n][n]=q[n];

       r[n][n]=c[n][n]=0;

       for(m=2;m<=n;m++)

       {

              for(i=0;i<=n-m;i++)

              {

                     j=i+m;

                     w[i][j]=w[i][j-1]+p[j]+q[j];

                     k=min_value(i,j);

                     c[i][j]=w[i][j]+c[i][k-1]+c[k][j];

                     r[i][j]=k;

              }

       }

}

void build_tree()

{

       int i,j,k;

       int queue[20],front=-1; int rear=-1;

       clrscr();

       printf("the optimal binary search tree for the given nodes is....\n");

       printf("\nthe root of this obst::%d",r[0][n]);

       printf("\nthe cost of this obst is::%d",c[0][n]);

       printf("\n\n\tNODE\tLEFT CHILD\tRIGHT CHILD");

       printf("\n----------------------------------------");

       queue[++rear]=0;

       queue[++rear]=n;

       while(front!=rear)

       {

         i=queue[++front];

         j=queue[++front];

         k=r[i][j];

         printf("\n\t%d\t",k);

         if(r[i][k-1]!=0)

         {

            printf("%d\t\t",r[i][k-1]);

            queue[++rear]=i;

            queue[++rear]=k-1;

         }

         else

             printf("-\t\t");

              if(r[k][j]!=0)

              {

                printf("%d\t",r[k][j]);

                queue[++rear]=k;

                queue[++rear]=j;

              }

              else

                  printf("-\t");

            }

            printf("\n");

            }

       void main()

       {

         get_data();

         obst();

         build_tree();

         getch();

         }

/*optimal binary search tree

 enter no of nodes

4

 enter data as......

 a[1]1

 a[2]2

 a[3]3

 a[4]4

 p[1]3

 p[2]3

 p[3]1

 p[4]1

 q[0] 2

 q[1] 3

 q[2] 1

q[3] 1

q[4] 1

the optimal binary search tree for the given nodes is....

the root of this obst::2

the cost of this obst is::32

 NODE    LEFT CHILD      RIGHT CHILD

        --------------------------------------

        2         1                       3

        1         -                        -

        3         -                       4

        4         -                        -

*/