bst.cpp

最佳二叉树是具有最佳检索效率的二叉树.本程序提供了最佳二叉树的构造方法.

/* 最佳二叉排序树是具有最佳检索效率的二叉排序树,

本程序提供了最佳二叉排序树的构造方法*/

#include<stdio.h>

#define MAXVALUE 1e8

#define N 10
	float c[N][N];

	float w[N][N];

	int r[N][N];

void OBT(float p[], float q[],int n)
{  
   int k0, i, j, k, m; float min;

   for(i=0; i<=n; i++)                     /* 数组下三角清零 */
     for(j=0; j<=i; j++)
        c[i][j]=w[i][j]=r[i][j]=0;



for(i=0; i<=n; i++)                     /* 计算w[i][j] */



{   w[i][i]=q[i];



  for(j=i+1; j<=n; j++)



    w[i][j]=w[i][j-1]+p[j]+q[j];
}

for(j=1; j<=n; j++)                     /* 计算一个内部结点的最佳二叉排序树 */



{ c[j-1][j]=w[j-1][j]; r[j-1][j]=j;}



for(m=2; m<=n; m++)                /* 计算m个结点的最佳二叉排序树 */



  for(i=0; i<=n-m; i++)



  {  j=i+m; min=MAXVALUE; k0=i+1;



        for(k=i+1; k<=j; k++)  /* 在i<k≤j范围内，找出使C(i,k-1)+C(k,j)最小的k。*/



          if( (c[i][k-1]+c[k][j])<=min)



          { min=c[i][k-1]+c[k][j]; k0=k;}



        c[i][j]=w[i][j]+min; r[i][j]=k0;



  }



}

void OBT1(float p[], float q[], float *c[], float *w[], int *r[], int n)
{
  int i,j,l,k;
  int f;
  float min;
  float m;
   for(i=0; i<=n; i++)                     /* 数组下三角清零 */
     for(j=0; j<=i; j++)
        c[i][j]=w[i][j]=r[i][j]=0;

  for(i=0;i<=n;i++){
   w[i][i]=q[i];
   c[i][i]=0;  

  }
  for(l=1;l<=n;l++)
	  for(i=0;i<=n-l;i++){
	  j=i+l;f=i+1;min=65535;
	  w[i][j]=w[i][j-1]+p[j]+q[j];
	  for(k=i+1;k<=j;k++){
	  m=c[i][k-1]+c[k][j];

	  if(m<=min){
	  min=m;f=k;

	  }
	  }
	  
	  c[i][j]=w[i][j]+min;
	  
	  r[i][j]=f;
	}
}
void BT(int i,int j,int r[N][N])
{
  int m;
  char ch='a';
	printf("%c%d\n",ch,r[i][j]);
  m=r[i][j];
	if(i<m-1)BT(i,m-1,r);
	if(m<j)BT(m,j,r);
  return ;
}

int main(){

//	float p[]={0,1,5,4,3};

//	float q[]={5,4,3,2,1};
	char ch='a';
	float p[]={0,4,2,1,1};

	float q[]={2,3,1,1,1};
	int i,j;
/*	float* cc[N];

	float* ww[N];

	int* rr[N];

	float c[N][N];

	float w[N][N];

	int r[N][N];

	int i,j;

	for(i=0;i<N;i++){

		cc[i]=c[i];

		ww[i]=w[i];

		rr[i]=r[i];

	}
*/
	OBT(p,q,4);

	printf("r\n");

	for(i=0;i<4;i++){

		for(j=i+1;j<=4;j++)

			printf("%c%d ",ch,r[i][j]);/*打印数组r*/

		putchar('\n');

	}
	
		printf("\nw\n");

	for(i=0;i<=4;i++){

		for(j=i+1;j<=4;j++)

			printf("%.0f ",w[i][j]);/*打印数组w*/

		putchar('\n');

	}
  	printf("\nc\n");
	for(i=0;i<4;i++){

		for(j=i+1;j<=4;j++)

			printf("%.0f ",c[i][j]);/*打印数组c*/

		putchar('\n');

	}
		putchar('\n');
 BT(0,4,r);
	return 0;

}