C++ Program to Implement OBST

C++ Program to Implement OBST

#include<iostream>

#include<conio.h>

#include<stdio.h>

using namespace std;

#define MAX 10

int main()

{

int w[MAX][MAX], c[MAX][MAX], r[MAX][MAX], p[MAX], q[MAX];

int temp=0, root, min, min1, n;

int i,j,k,b;

cout<<"Enter the number of elements:";

cin>>n;

cout<<"\n";

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

{

cout<<"Enter the Element ";

cin>>p[i];

}

cout<<"\n";

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

{

cout<<"Enter the Probability ";

cin>>q[i];

}

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

{

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

{

w[i][j] = 0;

c[i][j] = 0;

r[i][j] = 0;

}

}

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

{

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

{

if(i == j)

{

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

c[i][j] = 0;

r[i][j] = 0;

}

}

}

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

{

for(i=0,j=b+1; j < n+1 && i < n+1; j++,i++)

{

if(i!=j && i < j)

{

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

min = 30000;

for(k = i+1; k <= j; k++)

{

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

if(min > min1)

{

min = min1;

temp = k;

}

}

c[i][j] = min;

r[i][j] = temp;

}

}

}

printf("Minimum cost = %d\n",c[0][n]);

root = r[0][n];

printf("Root  = %d \n",root);

cout<<"\n**Weight matrix***\n";

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

{

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

{

cout<<w[i][j]<<"\t";

}

cout<<"\n";

}

cout<<"\n**Cost matrix***\n";

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

{

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

{

cout<<c[i][j]<<"\t";

}

cout<<"\n";

}

cout<<"\n**Root matrix***\n";

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

{

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

{

cout<<r[i][j]<<"\t";

}

cout<<"\n";

}

return 0;

}

Output

Enter the number of elements:6

Enter the Element 10

Enter the Element 3

Enter the Element 9

Enter the Element 2

Enter the Element 0

Enter the Element 10

Enter the Probability 5

Enter the Probability 6

Enter the Probability 4

Enter the Probability 4

Enter the Probability 3

Enter the Probability 8

Enter the Probability 0

Minimum cost = 158

Root  = 3 

**Weight matrix***

5 21 28 41 46 54 64

0 6 13 26 31 39 49

0 0 4 17 22 30 40

0 0 0 4 9 17 27

0 0 0 0 3 11 21

0 0 0 0 0 8 18

0 0 0 0 0 0 0

**Cost matrix***

0 21 41 79 96 121 158

0 0 13 39 53 78 115

0 0 0 17 31 56 89

0 0 0 0 9 26 53

0 0 0 0 0 11 32

0 0 0 0 0 0 18

0 0 0 0 0 0 0

**Root matrix***

0 1 1 2 3 3 3

0 0 2 3 3 3 3

0 0 0 3 3 3 4

0 0 0 0 4 5 6

0 0 0 0 0 5 6

0 0 0 0 0 0 6

0 0 0 0 0 0 0