上面的问题,用c或c++风格代码写一段代码
时间: 2024-10-05 22:00:58 浏览: 22
以下是使用 C++ 编写的函数,用于将扩展先根序列转换为中根序列和后根序列:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 创建二叉树的辅助结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderTraversal(TreeNode* root, vector<int>& res, bool isPostOrder = false) {
if (root == nullptr) return;
if (!isPostOrder) { // 中根遍历
res.push_back(root->val);
inorderTraversal(root->left, res);
inorderTraversal(root->right, res);
} else { // 后根遍历
inorderTraversal(root->left, res, true);
inorderTraversal(root->right, res, true);
res.push_back(root->val);
}
}
int main() {
int n;
cin >> n;
vector<int> expandedPreorder(n * 2 + 1);
for (int i = 0; i <= 2 * n; i++) {
cin >> expandedPreorder[i];
}
vector<int> middleOrder;
vector<int> postOrder;
TreeNode* root = new TreeNode(expandedPreorder[0]);
for (int i = 1; i <= 2 * n; i++) {
if (expandedPreorder[i] != -1) {
if (expandedPreorder[i - 1] == -1) { // 左孩子
root->left = new TreeNode(expandedPreorder[i]);
} else if (expandedPreorder[i + 1] == -1) { // 右孩子
root->right = new TreeNode(expandedPreorder[i]);
}
}
}
inorderTraversal(root, middleOrder);
inorderTraversal(root, postOrder, true);
cout << "中根遍历: ";
for (int val : middleOrder) {
cout << val << " ";
}
cout << endl;
cout << "后根遍历: ";
for (int val : postOrder) {
cout << val << " ";
}
cout << endl;
// 清理内存
for (TreeNode* node = root; node; node = node->left) {
delete node;
}
return 0;
}
```
这个程序首先读取扩展先根序列,然后创建二叉树并分别进行中根遍历和后根遍历。注意,这里使用了 C++ 的栈来模拟中根遍历过程,并通过创建实际的二叉树节点来进行后根遍历。最后清理内存以避免内存泄漏。
阅读全文