根据给定二叉树的先序遍历和中序遍历结果,给出后序遍历,并写出C++代码
时间: 2024-10-19 11:09:04 浏览: 45
在计算机科学中,给定一棵二叉树的先序遍历和中序遍历结果,我们可以重建这棵树并求得其后序遍历。这是因为先序遍历(根-左-右),中序遍历(左-根-右)包含了足够的信息来重构树。
后序遍历遵循的顺序是左子树、右子树、根节点。首先,我们找到先序序列的第一个元素作为根,它也是中序遍历中从左到右的中间节点。然后在中序序列中找到这个根节点,将左半部分(直到但不包括根)看作左子树的结果,右半部分就是右子树的结果。最后对左右子树分别应用同样的过程。
以下是使用C++的一个简化的示例算法:
```cpp
#include <iostream>
#include <vector>
// 定义二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
std::vector<int> buildTreeFromPreInOrder(std::vector<int>& preOrder, std::vector<int>& inOrder) {
if (preOrder.empty() || inOrder.empty()) return {};
// 先序遍历的第一个元素是根
TreeNode* root = new TreeNode(preOrder[0]);
int index = 0;
for (int val : inOrder) {
if (val == preOrder[index]) {
// 找到根节点,开始构建子树
index++;
break;
}
}
// 左子树的中序遍历在当前根节点之前
auto leftEnd = index;
std::vector<int> leftSubtree = buildTreeFromPreInOrder(preOrder.begin() + index, inOrder.begin() + index);
// 右子树的中序遍历在当前根节点之后
auto rightStart = index + 1;
std::vector<int> rightSubtree = buildTreeFromPreInOrder(preOrder.begin() + rightStart, inOrder.end());
// 将左右子树连接到根节点
root->left = leftSubtree.empty() ? nullptr : &leftSubtree.back();
root->right = rightSubtree.empty() ? nullptr : &rightSubtree.back();
return {root};
}
// 后序遍历
void postorderTraversal(TreeNode* root, std::vector<int>& result) {
if (!root) return;
postorderTraversal(root->left, result);
postorderTraversal(root->right, result);
result.push_back(root->val);
}
// 示例用法
int main() {
std::vector<int> preOrder = {1, 2, 4, 5, 3};
std::vector<int> inOrder = {4, 2, 5, 1, 3};
TreeNode* treeRoot = buildTreeFromPreInOrder(preOrder, inOrder);
std::vector<int> postOrderResult;
postorderTraversal(treeRoot, postOrderResult);
for (int val : postOrderResult)
std::cout << val << " ";
return 0;
}
```
阅读全文