1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175 | //动态规划求解最优二叉搜索树
#include <iostream>
using namespace std;
const int MAX = 10000000;
typedef struct TNode { //定义二叉树的结构
int elem; //结点的值
struct TNode *left; //左孩子
struct TNode * right; //右孩子
}TNode;
//动态规划求解最优二叉树，p[]储存实际结点的概率，q[]储存虚键的概率，n为实际结点的个数
//e[i][j]记录当前搜索期望，w[i][j]记录每个子树上的概率和，root[i][j]记录树Tij的根
void optimal_bst(double p[], double q[], int n, double **e, double **w, int **root) {
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++) { //将实际结点的个数逐渐从1扩展到n
for (int i = 1; i <= n - l + 1; i++) {
int j = i + l - 1;
e[i][j] = MAX; //先赋值无穷
w[i][j] = w[i][j - 1] + p[j] + q[j];
for (int r = i; r <= j; r++) {
double tmp = e[i][r - 1] + e[r + 1][j] + w[i][j];
if (tmp < e[i][j]) { //求 min{e[i][r-1] + e[r+1][j] + w[i][j]}
e[i][j] = tmp;
root[i][j] = r;
}
}
}
}
}
//递归输出最优二叉搜索树的括号化结构，虚拟键不输出，只输出实际结点
void print_optimal_bst(int i, int j, int **root, int nodeValue[]) {
if (i > j) {
cout << "{}";
return;
}
else {
int r = root[i][j];
cout << "K" << r << "(" << nodeValue[r] << ")";
cout << "{";
print_optimal_bst(i, r - 1, root, nodeValue);
cout << ",";
print_optimal_bst(r + 1, j, root, nodeValue);
cout << "}";
}
}
//输出上述括号化结构的解释，并构建最优二叉搜索树
void construct_optimal_bst(int i, int j, int k, int n, int **root, int nodeValue[], TNode *T) {
int r = root[i][j];
if (i == 1 && j == n) { //二叉树的根
cout << "K" << r << ": root" << endl;
T->elem = nodeValue[r]; //将根存入树结构中
construct_optimal_bst(1, r - 1, r, n, root, nodeValue, T);
construct_optimal_bst(r + 1, n, r, n, root, nodeValue, T);
}
else if (j == i - 1) { //遇到虚拟键
if (j < k) {
cout << "D" << j << ": Left child of K" << k << endl;
}
else {
cout << "D" << j << ": Right child of K" << k << endl;
}
}
else { //遇到实际结点
if (nodeValue[r] < nodeValue[k]) {
cout << "K" << r << ": Left child of K" << k << endl;
TNode *tl = new TNode; //为T的左孩子开空间
if (tl == NULL) {
cout << "Memory allocation error!";
exit(-1);
}
tl->left = NULL;
tl->right = NULL;
tl->elem = nodeValue[r];
T->left = tl;
construct_optimal_bst(i, r - 1, r, n, root, nodeValue, T->left); //左子树递归调用
construct_optimal_bst(r + 1, j, r, n, root, nodeValue, T->left);
}
else {
cout << "K" << r << ": Right child of K" << k << endl;
TNode *tr = new TNode; //为T的右孩子开空间
if (tr == NULL) {
cout << "Memory allocation error!";
exit(-2);
}
tr->left = NULL;
tr->right = NULL;
tr->elem = nodeValue[r];
T->right = tr;
construct_optimal_bst(i, r - 1, r, n, root, nodeValue, T->right); //右子树递归调用
construct_optimal_bst(r + 1, j, r, n, root, nodeValue, T->right);
}
}
}
//在二叉搜索树T中查找元素elem，输出查找结果以及比较的次数count
void binarySearch(int elem, TNode *T, int count) {
count++;
if (T == NULL) { //结果查找失败
cout << "NULL" << endl;
cout << "After " << count << " comparisons, query failed." << endl;
}
else if (T->elem == elem) { //结果查找成功
cout << T->elem << endl;
cout << "After " << count << " comparisons, query succeeded!" << endl;
}
else if (elem < T->elem) { //若elem < T->elem，则在左子树继续查找
cout << T->elem << " --> ";
binarySearch(elem, T->left, count);
}
else if (elem > T->elem) { //若elem > T->elem，则在右子树继续查找
cout << T->elem << " --> ";
binarySearch(elem, T->right, count);
}
}
int main() {
int n = 7; //实际结点的个数
int nodeValue[] = {0, 2, 5, 8, 16, 23, 29, 35}; //各结点的值
double p[] = {0, 13, 17, 25, 24, 19, 15, 12}; //查找成功的概率
double q[] = {8, 9, 1, 10, 17, 11, 13, 7}; //查找失败的概率
//为e，w，root三表开空间
double **e = new double*[n + 2];
for (int i = 0; i < n + 2; i++) {
e[i] = new double[n + 2];
}
double **w = new double*[n + 2];
for (int i = 0; i < n + 2; i++) {
w[i] = new double[n + 2];
}
int **root = new int*[n + 2];
for (int i = 0; i < n + 2; i++) {
root[i] = new int[n + 2];
}
//求解最优二叉搜索树的代价
optimal_bst(p, q, n, e, w, root);
//输出最优二叉搜索树的代价
cout << "The cost of the optimal binary tree is " << e[1][n] << endl;
//输出最优二叉搜索树的括号化结构
print_optimal_bst(1, n, root, nodeValue);
cout << endl;
//为二叉搜索树T开空间
TNode *T = new TNode;
if (T == NULL) {
cout << "Memory allocation error!" << endl;
exit(-3);
}
T->left = NULL;
T->right = NULL;
T->elem = nodeValue[n + 1];
//构建最优二叉搜索树，并输出详细结构
construct_optimal_bst(1, n, root[1][n], n, root, nodeValue, T);
//查找元素elem
int elem;
while (1) {
cout << endl;
cout << "Please enter the element you want to look for (Enter -1 to quit): ";
cin >> elem;
if (elem == -1) {
break;
}
else {
int count = 0;
binarySearch(elem, T, count); //返回是否查找成功，经过了几次比较
}
}
return 0;
}
|