最优二叉搜索树
问题描述：
已知二叉树集合p为根结点频率，集合q为叶结点的频率，根据比较权值大小，找出最优二叉搜索树。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。备注：
- 编程语言：c++
- 编译器：Code::Blocks 16.01
- 操作系统：windows 10
源代码：
//最优二叉搜索树 /*测试数据5
0.15 0.1 0.05 0.1 0.2
0.05 0.1 0.05 0.05 0.05 0.1
*/ #include<iostream>
#include <limits.h> //极限值头文件，INT_MAX无穷大，INT_MIN无穷小 using namespace std; void OBST(double *p,double *q,int n,double **e,int **r,double **w)
{
for(int i=1;i<=n+1;i++)
{
e[i][i-1]=q[i-1];
w[i][i-1]=q[i-1];
}
for(int l=1;l<=n;l++)
{
for(int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
e[i][j]=INT_MAX; //INT_MAX（无穷大）
w[i][j]=w[i][j-1]+p[j]+q[j];
for(int k=i;k<=j;k++)
{
double t=e[i][k-1]+e[k+1][j]+w[i][j];
if(t<e[i][j])
{
e[i][j]=t;
r[i][j]=k;
}
}
}
}
} int main()
{
int nn; //根结点个数
double *pp,*qq; //pp数组：根结点概率 qq数组：叶结点概率
double **ee,**ww; //ee二维数组：存储树的搜索权值 ww[i][j]=q[i-1]+p[i]+q[i]+...+p[j]+q[j]（i,j范围内的所有概率之和）
int **root; //存放根结点 cout<<"根结点个数：";
cin>>nn; pp = new double[nn+1];
qq = new double[nn+1];
//输入数据
cout<<"根结点概率："<<endl;
for(int r=1;r<=nn;r++)
cin>>pp[r];
cout<<"叶结点概率："<<endl;
for(int r=0;r<=nn;r++)
cin>>qq[r]; //创建动态二维数组
ee = new double*[nn+2];
root = new int*[nn+2];
ww = new double*[nn+2];
for(int i=0;i<=nn+1; i++)
{
ee[i] = new double[nn+1];
root[i] = new int[nn+1];
ww[i] = new double[nn+1];
} //赋初值
for(int j=0;j<=nn+1;j++)
{
for(int k=0;k<=nn;k++)
{
ee[j][k]=-1;
root[j][k]=-1;
ww[j][k]=-1;
}
} cout<<endl;
OBST(pp,qq,nn,ee,root,ww);//调用函数，根据二维数组root[i][j]画出二叉树 //输出二维数组
for(int j=0;j<=nn+1;j++)
{
for(int k=0;k<=nn;k++)
cout<<ee[j][k]<<"\t";
cout<<endl;
}
cout<<endl; for(int j=0;j<=nn+1;j++)
{
for(int k=0;k<=nn;k++)
cout<<root[j][k]<<"\t";
cout<<endl;
}
cout<<endl; for(int j=0;j<=nn+1;j++)
{
for(int k=0;k<=nn;k++)
cout<<ww[j][k]<<"\t";
cout<<endl;
}
cout<<endl; //释放空间
delete[] pp;
delete[] qq; for(int i=0;i<=nn+1;i++)
{
delete[] ee[i];
delete[] root[i];
delete[] ww[i];
}
delete[] ee;
delete[] root;
delete[] ww; return 0;
} 运行界面：
更多精彩
