59-伪代码详解

4.10.4　伪代码详解

（1）构建最优二叉搜索树

采用一维数组p[]、q[]分别记录实结点和虚结点的搜索概率，c[i][j]表示最优二叉搜索树T（i，j）的搜索成本，w[i][j]表示最优二叉搜索树T（i，j）中的所有实结点和虚结点的搜索概率之和，s[i][j]表示最优二叉搜索树T（i，j）的根节点序号。首先初始化，令c[i][i−1]=0.0，w[i][i−1]=q[i−1]，其中i= 1，2，3，…，n+1。按照递归式计算元素规模是1的{s_i}（j=i）的最优二叉搜索树搜索成本c[i][j]，并记录最优策略，即树根s[i][j]，i=1，2，3，…，n。按照递归式计算元素规模是2的{s_i，s_i+1}（j=i+1）的最优二叉搜索树搜索成本c[i][j]，并记录最优策略，即树根s[i][j]，i=1，2，3，…，n−1。以此类推，直到求出所有元素{s₁，…，s_n} 的最优二叉搜索树搜索成本c[1][n]和最优策略s[1][n]。

void Optimal_BST()
{
     for(i=1;i<=n+1;i++)
     {
          c[i][i-1]=0.0;
          w[i][i-1]=q[i-1];
     }
     for(int t=1;t<=n;t++)                 //t为关键字的规模
          //从下标为i开始的关键字到下标为j的关键字
          for(i=1;i<=n-t+1;i++)
          {
               j=i+t-1;
               w[i][j]=w[i][j-1]+p[j]+q[j];
               c[i][j]=c[i][i-1]+c[i+1][j];//初始化
               s[i][j]=i;                  //初始化
               for(k=i+1;k<=j;k++) //选取i+1到i之间的某个下标的关键字作为从i到j的根，如果组成的树的期望值当前最小，则k为从i到j的根节点
               {
                    double temp=c[i][k-1]+c[k+1][j];
                if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)//C++中浮点数因为精度问题不可以直接比较，fabs(temp-c[i][j])>1E-6表示两者不相等
                    {
                         c[i][j]=temp;
                         s[i][j]=k;        //k即为从下标i到j的根节点
                    }
               }
               c[i][j]+=w[i][j];
          }
}

（2）构造最优解

Construct_Optimal_BST(int i,int j,bool flag)表示构建从结点i到结点j的最优二叉搜索树。首次调用时，flag=0、i=1、j=n，表示首次构建，读取的第一个数值s[1][n]为树根，其他递归调用flag=1。

Construct_Optimal_BST(int i,int j,bool flag)：首先读取s[i][j]，令k=s[i][j]，判断如果k−1<i，表示虚结点e_k−1是s_k的左子树；否则，递归求解左子树Construct_Optimal_BST(i，k−1，1)。判断如果kj，输出虚结点e_k是s_k的右孩子；否则，输出s[k+1][j]是s_k的右孩子，递归求解右子树Construct_Optimal_BST(k +1，j，1)。

void Construct_Optimal_BST(int i,int j,bool flag)
{
     if(flag==0)
     {
           cout<<"S"<<s[i][j]<<" 是根"<<endl;
           flag=1;
     }
     int k=s[i][j];
     //如果左子树是叶子
     if(k-1<i)
     {
          cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
     }
     //如果左子树不是叶子
     else
     {
          cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
          Construct_Optimal_BST(i,k-1,1);
     }
     //如果右子树是叶子
     if(k>=j)
     {
          cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
     }
     //如果右子树不是叶子
     else
     {
          cout<<"S"<<s[k+1][j]<<" is the right child of "<<"S"<<k<<endl;
          Construct_Optimal_BST(k+1,j,1);
     }
}