Program to solve optimal binary search tree problem with dynamic programming

// program to solve optimal binary search tree problem with dynamic programming

#include<iostream.h>
#include<conio.h>

struct node
{
	int data;
	struct node *left,*right;
};

typedef struct node node;

class binary
{
	private:
		int w[10][10],c[10][10],r[10][10],n;
		int p[10],q[11];

		int find(int,int);
		node *cnst_tree(int,int);

	public:
		void obst();
		void setdata();
		node *tree();
};

node *binary::tree()
{
	return(cnst_tree(0,n));
}

void binary :: setdata()
{
	int i,j;

	cout<<"\nEnter number of identifiers: ";
	cin>>n;

	cout<<"\nEnter values for P vector ("<<n<<" values): ";
	for(i=1;i<=n;i++)
		cin>>p[i];

	cout<<"\nEnter values for Q vector ("<<n+1<<" values): ";
	for(i=0;i<=n;i++)
		cin>>q[i];
}

void binary :: obst()
{
	int i,j,k,m;

	for(i=0;i<=n-1;i++)
	{
		w[i][i]=q[i];
		r[i][i]=0;
		c[i][i]=0;

		w[i][i+1]=p[i+1]+q[i+1]+q[i];
		r[i][i+1]=i+1;
		c[i][i+1]=w[i][i+1];
	}

	w[n][n]=q[n];
	r[n][n]=0;
	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=find(i,j);
			c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
			r[i][j]=k;
		}
}

int binary ::find(int i,int j)
{
	int min=32767,m,l;

	m=r[i][j-1];
	while(m<=r[i+1][j])
	{
		if(c[i][m-1]+c[m][j]<min)
		{
			min=c[i][m-1]+c[m][j];
			l=m;
		}
		m++;
	}

	return l;
}

node * binary::cnst_tree(int i,int j)
{
	int k;
	node *p= new node;
	k=r[i][j];

	if(k==0)
		return NULL;
	else
	{
		p->data=k;
		p->left=cnst_tree(i,k-1);
		p->right=cnst_tree(k,j);
		return p;
	}
}

void inorder (node *x)
{
	if(x)
	{
		inorder(x->left);
		cout<<x->data<<"\t";
		inorder(x->right);
	}
}

void main()
{
	node *root;
	binary b;
	clrscr();

	b.setdata();

	b.obst();

	root=b.tree();

	cout<<"\nTree in inorder traversal is: \n\n\t";
	inorder(root);

	getch();
}