输出bst的中根和先根序列
时间: 2024-05-26 10:12:24 浏览: 36
好的,我知道了。给定一棵二叉搜索树,可以通过遍历其节点来获取中根和先根序列。
先根序列可以通过先访问根节点,然后按照左子树的先根序列和右子树的先根序列的顺序遍历子树,得到整棵树的先根序列。
中根序列可以通过先遍历左子树的中根序列,然后访问根节点,最后遍历右子树的中根序列,得到整棵树的中根序列。
因此,可以通过递归的方式遍历树,输出相应的序列。
相关问题
用c++实现最优二叉搜索树先根序列打印
以下是用 C++ 实现最优二叉搜索树先根序列打印的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n;
int keys[MAXN];
int freqs[MAXN];
int dp[MAXN][MAXN];
int root[MAXN][MAXN];
void print_preorder(int l, int r) {
if (l > r) {
return;
}
int k = root[l][r];
cout << keys[k] << " ";
print_preorder(l, k - 1);
print_preorder(k + 1, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> keys[i] >> freqs[i];
}
for (int i = 1; i <= n; i++) {
dp[i][i] = freqs[i];
root[i][i] = i;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = INF;
for (int k = i; k <= j; k++) {
int cost = dp[i][k - 1] + dp[k + 1][j] + freqs[k];
if (cost < dp[i][j]) {
dp[i][j] = cost;
root[i][j] = k;
}
}
}
}
cout << "Optimal BST cost: " << dp[1][n] << endl;
cout << "Optimal BST preorder: ";
print_preorder(1, n);
cout << endl;
return 0;
}
```
其中,`keys[i]` 表示第 i 个关键字,`freqs[i]` 表示第 i 个关键字的频率,`dp[i][j]` 表示第 i 个关键字到第 j 个关键字构成的子树的最小代价,`root[i][j]` 表示第 i 个关键字到第 j 个关键字构成的子树的根节点。
首先,我们初始化每个单独的节点的代价和根节点。然后,我们从小到大枚举子树的长度,从左到右枚举子树的起点和终点,计算每个可能的根节点的代价,选取代价最小的作为该子树的根节点。最后,我们输出最优二叉搜索树的代价和先根序列。
注意,这里的先根序列是指先输出根节点,然后递归输出左子树和右子树。
最优二分检索树问题,写出满足如下要求的C++代码,输出最优二分检索树先根遍历时得到的字符编号序列。
以下是最优二分检索树问题的C++代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
void printOptimalBST(vector<vector<int>>& root, int i, int j, int parent) {
if (i > j) return;
if (parent == 0) cout << "k" << root[i][j] << " is root" << endl;
else {
if (j < parent) cout << "k" << root[i][j] << " is left child of " << "k" << parent << endl;
else cout << "k" << root[i][j] << " is right child of " << "k" << parent << endl;
}
printOptimalBST(root, i, root[i][j] - 1, root[i][j]);
printOptimalBST(root, root[i][j] + 1, j, root[i][j]);
}
void optimalBST(vector<int>& keys, vector<int>& freq) {
int n = keys.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
vector<vector<int>> root(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < n; i++) {
dp[i][i] = freq[i];
root[i][i] = i;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k <= j; k++) {
int cost = ((k > i) ? dp[i][k - 1] : 0) +
((k < j) ? dp[k + 1][j] : 0) +
freq[k];
if (cost < dp[i][j]) {
dp[i][j] = cost;
root[i][j] = k;
}
}
}
}
cout << "The optimal BST cost is: " << dp[0][n - 1] << endl;
cout << "The optimal BST is: " << endl;
printOptimalBST(root, 0, n - 1, 0);
}
int main() {
vector<int> keys = {10, 12, 16, 21};
vector<int> freq = {4, 2, 6, 3};
optimalBST(keys, freq);
return 0;
}
```
其中,`optimalBST`函数使用动态规划求解最优二分检索树的成本,并构造出最优二分检索树。`printOptimalBST`函数则用于输出最优二分检索树的先根遍历序列,其中`root`数组保存了每个子树的根节点编号。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)