请给出详细的C++代码
时间: 2024-10-08 21:02:47 浏览: 16
为了展示如何在C++中通过上述步骤计算二叉树的后根序列,我们可以编写一个函数来完成递归操作。假设`Node`是一个简单的二叉树节点结构,包含整数值和左右指针:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点
struct Node {
int data;
Node* left, *right;
};
// 中序遍历的辅助函数,用于查找根节点索引
int findRootIndex(Node* root, vector<int>& inorder) {
for (size_t i = 0; i < inorder.size(); ++i) {
if (inorder[i] == root->data)
return i;
}
return -1;
}
// 计算后根序列的递归函数
vector<int> constructPostorder(Node* root, vector<int>& inorder, size_t start=0) {
vector<int> postorder;
// 如果根节点为空,直接返回空序列
if (!root)
return postorder;
// 找到当前节点在中序遍历中的索引
size_t index = findRootIndex(root, inorder);
// 递归获取左子树的后根序列
vector<int> left_postorder = constructPostorder(root->left, inorder, start);
// 递归获取右子树的后根序列
vector<int> right_postorder = constructPostorder(root->right, inorder, index + 1);
// 将结果合并并添加当前节点
postorder.insert(postorder.end(), left_postorder.begin(), left_postorder.end());
postorder.push_back(root->data);
postorder.insert(postorder.end(), right_postorder.rbegin(), right_postorder.rend());
return postorder;
}
// 示例:给定中根序和先根序,构造后根序
void computePostorder(Node* root, vector<int>& inorder, vector<int>& preOrder) {
if (!root)
return;
// 获取中序遍历的长度
size_t inorderSize = inorder.size();
// 构造后根序
vector<int> postorder = constructPostorder(root, inorder);
// 输出结果
for (auto& num : postorder)
cout << num << " ";
cout << endl;
}
// 示例用法:创建一个二叉树并测试函数
int main() {
// 创建示例二叉树
Node* tree = new Node{5, new Node(3, new Node(2), new Node(4)), new Node(6, NULL, new Node(7))};
// 中序遍历
vector<int> inorder = {2, 4, 5, 3, 6, 7};
// 先序遍历
vector<int> preOrder = {5, 3, 2, 6, 7, 4};
computePostorder(tree, inorder, preOrder); // 输出后根序
delete tree;
return 0;
}
```
在这个代码中,`computePostorder`函数接收中根序和先根序,然后调用`constructPostorder`递归生成后根序。注意,你需要提供具体的二叉树数据结构和相关的中序遍历和先序遍历数组。运行此代码,将看到后根序列。
阅读全文