【说明】构造最优二叉查找树。
具有n个结点的有序序列a₁, a₂, …, a_n存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a₁, a₂, …, a_n-1, a_n的查找成功的概率p₁, p₂, …, p_n-1, p_n存在于数组元素 p[1]、p[2], …, p[n—1]、p[n]之中, p[0]未用。另外, 查找失败的概率q₀, q₁, …, q_n-1, q_n存在于数组元素q[0]、p[1], …, q[n-1]、q[n]之中。算法计算的序列a_i+1, a_i+2,…, a_j-1, a_j的最优二叉查找树T_ij的代价C_ij存在于数组元素c[i][j]之中, T_ij的根结点的序号r_ij存在于r[i][j]之中, 它的权值存在于w[i][j]之中。为了便于内存的动态分配, 统统使用一维数组取代二维数组。
const float MAXNUM=99999. 0; //尽可能大的浮点数
template＜{{U}} (1) {{/U}}＞
void OPtimal_Binary_Search_Tree(float p[], float q[], Type a[], int n) {
float *C, *W;
c={{U}} (2) {{/U}};
w={{U}} (3) {{/U}};
int *r;
r=new int[(n+1)*(n+1)];
for(i=0; i＜=n; i++)
{ c[i*(n+1)+i]=0. 0; // 即：c[i][i]=0.0, 用一维数组表示
w[i*(n+1)+i]=q[i]; // 即：w[i][i]=q[i], 用一维数组表示
}
int i, j, k, m, length; // m表示根结点的下标或序号, 范围为0～n
float minimum;
for(length=1; length＜=n; length++) //处理的序列长度由1到n
for(i=0; i＜=n-length; i++){ //i为二叉查找树T_ij的起始序号
j=i + length; //j为二叉查找树T_ij的终止序号。如：处理序列a₁a₂a₃时,
//相应的二叉查找树为T₀₃, i=0, 而j=3
w[i*(n+1)+j]={{U}} (4) {{/U}};
minimum =MAXMUM;
for(k=i+1; k＜=j; k++) //考察以a_i+1、a_i+2, …, a_i为根的情况
if({{U}} (5) {{/U}}＜minimum)
{ minimum=c[i*(n+1)+k-1]+c[k*(n+1)+j];m=k; }
c[i*(n+1)+j]=w[i*(n+1)+j]+c[i*(n+1)+m-1]+c[m*(n+1)+j];
r[i*(n+1)+j]=m; // r[i][j]=m
}
} //构造好的最优二叉查找树的根结点的序号在r[0][n]中