struct node
{
int iData;
struct node* pLeft;
struct node* pRight;
}node;
 
 
node* getNode(int iData)
{
node* pNewNode = (node *)malloc(sizeof(node));
pNewNode->iData = iData;
pNewNode->m_pLeft = NULL;
pNewNode->m_pRight = NULL;
return pNewNode;
}
void insert(node* pParent, int iData)
{
if (pParent == NULL)
{
pParent = getNode(iData);
if (pRoot == NULL)
{
pRoot = pParent;
}
}
else
{
if (iData < pParant->iData)
{
insert(pParent->pLeft, iData);
}
else
{
insert(pParent->pRight, iData);
}
} }

#include<iostream>
#include<cstdio>
using namespace std;
float find(float c[50][50],int r[50][50],int,int);
int main(void)
{
   int i,n,k,l;
  float w[50][50];
  int r[50][50];
  float p[50],q[50];
  int j,min;
  float c[50][50];
  cout<<endl<<endl;
  cout<<"enter the no.of identifiers"<<endl;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cout<<"Enter The Identifier "<<i<<endl;
    cin>>p[i];
  }
  //cout<<"q"<<endl;
  //cin>>q;
  for(i=0;i<=n;i++)
  {
    cout<<"Enter The Qualifier "<<i<<endl;
    cin>>q[i];
  }
  for(i=0;i<=n-1;i++)
  {
    w[i][i]=q[i];
    r[i][i]=0;
    c[i][i]=0.0;
    //optimal trees with one node.
    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]=0;
  c[n][n]=0.0;
  for(int 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(c,r,i,j);
      c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
      r[i][j]=k;
    }
 
    cout<<"Weight Is\t"<<w[0][n]<<endl;
    cout<<"Cost Is\t"<<c[0][n]<<endl;
    cout<<"Root Is\t"<<r[0][n]<<endl<<endl;
    cout<<"Matrix format"<<endl;
    for(i=0;i<=n;i++)
    {
       cout<<"\n";
       for(j=i;j<=n;j++)
       {
	  cout<<"\nWeight="<<w[i][j];
	  cout<<"\tCost="<<c[i][j];
	  cout<<"\tRoot="<<r[i][j];
       }
  }
  int b;
cout<<"\nRoot is "<<r[0][n];
b=r[0][n];
i=n;
cout<<"\nLeft child is "<<r[0][i-2];
cout<<"\nRight child of "<<b<<" is "<<r[i-2][n-1];
cout<<"\nThis is again a root";
i=1;
cout<<"\nRight sub child is "<<r[n-1][n];
cout<<"\nLeft sub child is "<<r[i-2][n-2];
    cin.get();
}
float find(float c[50][50],int r[50][50],int i,int j)
{
   int min;
   float l;
   min=1000;
   for(int m=r[i][j-1];m<=r[i+1][j];m++)
     if(c[i][m-1]+c[m][j]<min)
     {
       min=c[i][m-1]+c[m][j];
       l=m;
     }
     cin.get();
     cin.get();
     cin.get();
     return 0;
}