bestree.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 123 行

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>

typedef char BELEM;

#include "..\include\book.h"
#include "..\include\bintree.h"
#include "..\include\binoperator.h"

const n=4;
int r[n+1][n+1];
float C[n+1][n+1], W[n+1][n+1], p[n+1], q[n+1];
char data[n+1];

void create_table( ) {
   int i, j, d, x, x0;
   float m;
   for (i=0; i<=n; i++)   // 初始化表
	   for (j=0; j<=n; j++)  {
         C[i][j] = W[i][j] = 0; 
		 r[i][j] = 0;
	   }
   for (i=0; i<=n; i++) {   // 初始化权表
      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 (d=2; d<=n; d++) // 生成d个结点的最佳二叉检索树
      for (j=d; j<=n; j++)  { // 生成t(i][j)
         i = j - d;
         m = C[i+1][j];   x0 = i + 1; // 第一棵树以Ki+1为根
         for (x=i+2; x<=j; x++) 
            if (C[i][x-1]+C[x][j]<m)  {
               m = C[i][x-1]+C[x][j];
               x0 = x;
            }
         C[i][j] = W[i][j]+m;
         r[i][j] = x0;
      }
   cout << "root matrix\n";  cout << "  ";
   for (i=0; i<=n; i++)   
	   cout << i << " ";
   cout << endl;
   for (i=0; i<=n; i++) {  
	   cout << i << " ";
	   for (j=0; j<=n; j++)
		 cout << r[i][j] << " ";
	   cout << endl;
   }
   cout << "cost matrix\n";    cout << "  ";
   for (i=0; i<=n; i++) 
	   cout << i << " ";
   cout << endl;
   for (i=0; i<=n; i++) { 
	   cout << i << " ";
	   for (j=0; j<=n; j++)
		 cout << C[i][j] << " ";
	   cout << endl;
   }
   cout << "weight matrix\n";    cout << "  ";
   for (i=0; i<=n; i++) 
	   cout << i << " ";
   cout << endl;
   for (i=0; i<=n; i++) {  
	   cout << i << " ";
	   for (j=0; j<=n; j++)
		 cout << W[i][j] << " ";
	   cout << endl;
   }
 }

void build(BinNode* &rt, int i, int j) {
   int x;
   if (j-i == 0)  rt = NULL;
   else {
      x = r[i][j];
      rt = new BinNode;
      rt->element = data[x];
	  cout << rt->element;
      build(rt->left, i, x-1);
      build(rt->right, x, j);
   }
}

void preorder(BinNode* rt) { // Preorder traversal
  if (rt == NULL) return;
  cout << rt->element << " ";
//  cout << rt->value( ) << " ";
  preorder(rt->leftchild());
  preorder(rt->rightchild());  
}

void inorder(BinNode* rt) { // Preorder traversal
  if (rt == NULL) return;
  inorder(rt->leftchild());
  cout << rt->value( ) << " ";
  inorder(rt->rightchild());  
}

void main() {
   BinNode *rt;
   cout << "input" << n <<" keys \n";
   for (int i=1; i<=n; i++)  
      cin >> data[i];
   cout << "input" << n <<"p[i]";
   for (i=1; i<=n; i++)  
      cin >> p[i];
   cout << "input" << n+1 <<"q[i]\n";
   for (i=0; i<=n; i++) 
      cin >> q[i];
   create_table( );
   build(rt, 0, n);
   preorder(rt);  cout << endl;
   inorder(rt);  cout << endl;
}