// zuiyousousuoerchashu.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include
     
      using namespace std;double p[] = { 0,0.15,0.1,0.05,0.10,0.2 };double q[] = { 0.05,0.10,0.05,0.05,0.05,0.10};double e[7][7], w[7][7];int root[7][7];void option(int n)                    //求最优搜索二叉树{	for (int i = 1; i <= n + 1; i++) {		e[i][i - 1] = q[i - 1];       //j=i-1，则节点左边为空，此时为伪关键字d(i-1)		w[i][i - 1] = q[i - 1];      //w为搜索代价增量	}	for (int l = 1; l <= n; l++) {     //自底向上地计算间隔为1,2,3..个节点时的最优父节点，l为间隔量		for (int i = 1; i <= n - l + 1; i++) {           //i为起点			int j = i + l - 1;                          //j为每一段的终点			e[i][j] = 65535;                            //先设置为一个较大的树			w[i][j] = w[i][j - 1] + p[j] + q[j];        //利用递归式计算w的值			for (int r = i; r <= j; r++) {              //此循环从[i,j]中找出使代价最小的最优节点作为父节点，w[i][j]已由上步算出				double t = e[i][r - 1] + e[r + 1][j] + w[i][j];				if (t < e[i][j]) {					e[i][j] = t;					root[i][j] = r;				}			}		}	}}void construct(int i, int j)  //重建最优二叉树，先递归左子树的节点，再递归右子树的节点{	if (i <= j)	{		int r = root[i][j];		cout << r <
      
        j)                                   //i>j时，该节点右边没有关键字，因此右边有一个伪关键字子节点	{		cout << "d" << j << "是k" << j << "的右孩子" << endl;	}}int main(){	option(5);	//construct(1, 5);	construct2(1, 5);	while (1);    return 0;}