最优二叉搜索树问题(三)
delete m[i];
delete s[i];
delete w[i];
}
delete[] m;
delete[] s;
delete[] w;
return 0;
}
void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w)
{
//初始化构造无内部节点的情况
for(int i=0; i<=n; i++)
{
w[i+1][i] = a[i];
m[i+1][i] = 0;
s[i+1][i] = 0;
}
for(int r=0; r
{
for(int i=1; i<=n-r; i++)//i为起始元素下标
{
int j = i+r;//j为终止元素下标
int i1 = s[i][j-1]>i s[i][j-1]:i;
int j1 = s[i+1][j]>i s[i+1][j]:j;
//构造T[i][j] 填写w[i][j],m[i][j],s[i][j]
//首选i作为根，其左子树为空，右子树为节点
w[i][j]=w[i][j-1]+a[j]+b[j];
m[i][j]=m[i][i1-1]+m[i1+1][j];
s[i][j]=i1;
//不选i作为根，设k为其根，则k=i+1，……j
//左子树为节点：i,i+1……k-1,右子树为节点：k+1,k+2,……j
for(int k=i1+1; k<=j1; k++)
{
double t = m[i][k-1]+m[k+1][j];
if(t
{
m[i][j]=t;
s[i][j]=k;//根节点元素
}
}
m[i][j]+=w[i][j];
}
}
}
void Traceback(int n,int i,int j,int **s,int f,char ch)
{
int k=s[i][j];
if(k>0)
{
if(f==0)
{
//根
