最优二叉搜索树

#include <iostream>  
using namespace std;  
const int MaxVal=9999,n=5;  
double p[n+1] = {-1,0.15,0.1,0.05,0.1,0.2};  //搜索到内部节点的概率  
double q[n+1] = {0.05,0.1,0.05,0.05,0.05,0.1};  //搜索到虚拟键的概率  
int root[n+1][n+1];  //记录根节点  
double w[n+2][n+2];  //子树概率总和  
double e[n+2][n+2];  //子树期望代价  
void optimalBST(int n)  
{  
    int i,j,k,len;
    for (i=1;i<=n+1;++i)  
    {  
        w[i][i-1]=q[i-1];  
        e[i][i-1]=q[i-1];  
    }  
    for(len=1;len<=n;++len)  
    {  
        for(i=1;i<=n-len+1;++i)  
        {  
            j=i+len-1;  
            e[i][j]=MaxVal;  
            w[i][j]=w[i][j-1]+p[j]+q[j];  
            for(k=i;k<=j;++k)  
            {  
                double temp=e[i][k-1]+e[k+1][j]+w[i][j];  
                if (temp<e[i][j])  
                {  
                    e[i][j]=temp;  
                    root[i][j]=k;  
                }  
            }  
        }  
    }  
}  
void printOptimalBST(int i,int j,int r)  
{  
    int rootChild = root[i][j];
    if (rootChild == root[1][n])  
    {  
        printf("k%d 是根\n",rootChild);
        printOptimalBST(i,rootChild - 1,rootChild);  
        printOptimalBST(rootChild + 1,j,rootChild);  
        return;  
    }  
    if (j < i - 1)  return;  
    else if (j == i - 1)  
    {  
        if (j < r)  printf("d%d 是 k%d 的左孩子\n",j,r);
        else  printf("d%d 是 k%d 的右孩子\n",j,r);
        return;  
    }  
    else  
    {  
        if (rootChild < r)  printf("k%d 是 k%d 的左孩子\n",rootChild,r); 
        else  printf("k%d 是 k%d 的左孩子\n",rootChild,r); 
    }  
    printOptimalBST(i,rootChild - 1,rootChild);  
    printOptimalBST(rootChild + 1,j,rootChild);  
}  
  
int main()  
{  
    optimalBST(n);  
    cout << "最优二叉树结构：" << endl;  
    printOptimalBST(1,n,-1);  
    system("pause");
    return 0;
}