学步园

本书从文字翻译的案例切入，假设把英文翻译为法文，每个英文单词为关键字，其对应法文为卫星数据。用二叉查找树存储，该怎么设计这个查找树。即使是红黑树，查找的时间复杂度也为O(lgn)即树的深度。但是因为文章中某个单词出现的频率不同，所以可能有些频率很高的单词比如the的深度可能很深，而不常见的Aha的深度却可能很浅。根据直觉，我们应该让本例中the更加靠近树根才对（其实即使概率最高也不见得就是树根）。我们应该让查找整个树的期望次数最小，即构建一个最优二叉查找树。一个最优二叉查找树的左右子树的肯定也是最优的。数组p中是k1~k5的概率。k1到k5是从小到大的顺序，即字典序。当找不到要查找到英文单词时肯定最终会走到树叶，每个树叶出现的概率存储到数组q中。我一直没弄明白这个树叶的概率作者是怎么搞出来的。谁知道告诉我一下。

程序一个注意的地方就是浮点数比较，不能直接比较，除非相差很大才行，如果两个浮点数相等，要是直接使用大于号进行判断也有可能成立。

代码如下：

#include <iostream>
using namespace std;

void OpticalBST(double *p,double *q,int n,double (*e)[6],int (*root)[6])
{
	double w[n+1][6];
	for(int i=1;i<=n+1;i++)
	{
		e[i][i-1]=q[i-1];
		w[i][i-1]=q[i-1]; 
	}
	
	for(int l=1;l<=n;l++)
	{
		for(int i=1;i<=n-l+1;i++)
		{
			int j=i+l-1;
			e[i][j]=1<<30;
			//cout<<e[i][j];system("pause");
			w[i][j]=w[i][j-1]+p[j]+q[j];//子树i...j的总概率 
			for(int r=i;r<=j;r++)
			{
				double t=e[i][r-1]+e[r+1][j]+w[i][j];
				if(e[i][j]-t>0.0000000001)//不能直接用e[i][j]>t，因为如果e[i][j]和t都是浮点数，即使相等的话，相减可能也不等于0 
				{
					e[i][j]=t;
					root[i][j]=r;
				} 
			}
		}
	}
}

void ConstructOpticalBST(int (*root)[6],int i,int j)
{
	if(i==1&&j==5)
	{
		cout<<"k"<<root[i][j]<<"是根"<<endl;//system("pause");
	}
	if(i<root[i][j]) 
	{
		cout<<"k"<<root[i][root[i][j]-1]<<"是k"<<root[i][j]<<"的左孩子"<<endl;
		ConstructOpticalBST(root,i,root[i][j]-1);
	}
	else
	{
		cout<<"d"<<root[i][j]-1<<"是k"<<root[i][j]<<"的左孩子"<<endl;
	}
	if(root[i][j]<j)
	{
		cout<<"k"<<root[root[i][j]+1][j]<<"是k"<<root[i][j]<<"的右孩子"<<endl;
		ConstructOpticalBST(root,root[i][j]+1,j);
	}
	else
	{
		cout<<"d"<<root[i][j]<<"是k"<<root[i][j]<<"的右孩子"<<endl;
	} 
}

int main()
{
	int n=5;
	double p[6]={0,0.15,0.1,0.05,0.1,0.2};//第一个不用。1~5分别代表k1~k5,并且k1~k5是按从下到大顺序排列。K的顺序对于输出整个数很重要。 
	double q[6]={0.05,0.1,0.05,0.05,0.05,0.1}; 
	double e[7][6];
	int root[6][6];
	
	OpticalBST(p,q,n,e,root);
	ConstructOpticalBST(root,1,5);
    system("pause");
    return 0;
}