简介

给定一个n个不同关键字的已排序的序列K=<k1,k2,…,kn>，我们希望用这些关键字构造一颗二叉搜索树，对于给定的搜索频率，该二叉搜索树所需的期望代价最小。称这个二叉树为最优二叉搜索树。

代码具体实现

#include<iostream>
using namespace std;
const int N = 3;
double a[100];
double b[100];
void OptimalBinarySearchTree(double a[], double b[], int n, double** m, int** s, double** w) {
	for (int i = 0; i <= n; i++) {
		w[i + 1][i] = a[i];
		m[i + 1][i] = 0;
	}
	for (int r = 0; r < n; r++)
	{
		for (int i = 1; i <= n - r; i++) {
			int j = i + r;
			w[i][j] = w[i][j - 1] + a[j] + b[j];
			m[i][j] = m[i + 1][j];
			s[i][j] = i;
			for (int k = i + 1; k <= j; k++) {
				double t = m[i][k - 1] + m[k + 1][j];
				if (t < m[i][j]) {
					m[i][j] = t;
					s[i][j] = k;
				}
				m[i][j] += w[i][j];
			}
		}
	}
}
void Traceback(int n, int i, int j, int** s, int f, char ch)
{
	int k = s[i][j];
	if (k > 0)
	{
		if (f == 0)
		{
			cout << "Root：" << k << " (i:j):(" << i << "," << j << ")" << endl;
		}
		else
		{
			cout << ch << " of " << f << ":" << k << " (i:j):(" << i << "," << j << ")" << endl;
		}

		int t = k - 1;
		if (t >= i && t <= n)
		{
			Traceback(n, i, t, s, k, 'L');
		}
		t = k + 1;
		if (t <= j)
		{
			Traceback(n, t, j, s, k, 'R');
		}
	}
}
int main() {
	int n;
	cout << "请输入a的个数" << endl;
	cin >> n;
	cout << "请输入a：" << endl;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int p;
	cout << "请输入b的个数" << endl;
	cin >> p;
	cout << "请输入b:" << endl;
	for (int i = 0; i < p; i++) {
		cin >> b[i];
	}
	double** m = new double* [N + 2];
	int** s = new int* [N + 2];
	double** w = new double* [N + 2];
	for (int i = 0; i < N + 2; i++)
	{
		m[i] = new double[N + 2];
		s[i] = new int[N + 2];
		w[i] = new double[N + 2];
	}
	OptimalBinarySearchTree(a, b, N, m, s, w);
	cout << "二叉搜索树最小平均路长为：" << m[1][N] << endl;
	cout << "最优解为：" << endl;
	Traceback(N, 1, N, s, 0, '0');
	for (int i = 0; i < N + 2; i++)
	{
		delete m[i];
		delete s[i];
		delete w[i];
	}
	delete[] m;
	delete[] s;
	delete[] w;
	return 0;
}