编写一个程序实现二叉树先序,中序,后序遍历,以及由先序和后序恢复二叉树c++
时间: 2024-11-27 22:13:32 浏览: 40
在C++中,我们可以使用递归的方式来实现二叉树的先序(Preorder)、中序(Inorder)和后序(Postorder)遍历,以及利用这两个序列重构二叉树。这里是一个简单的示例:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历(根-左-右)
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// 中序遍历(左-根-右)
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
}
// 后序遍历(左-右-根)
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
}
// 根据先序和后序重建二叉树(假设输入顺序正确)
TreeNode* buildTreeFromPreAndPost(vector<int>& preOrder, vector<int>& postOrder) {
if (preOrder.empty() || postOrder.empty()) return nullptr;
int index = 0; // 先序中查找当前节点的位置
for (int i = 0; i < postOrder.size(); ++i) {
if (postOrder[i] == preOrder[index]) { // 找到根节点
TreeNode* node = new TreeNode(preOrder[index]);
int leftSize = i - 1; // 计算左子树大小
int rightSize = postOrder.size() - i - 1; // 计算右子树大小
// 构建左右子树并插入根节点
node->left = buildTreeFromPreAndPost(preOrder.begin() + index + 1, postOrder.begin() + leftSize + 1);
node->right = buildTreeFromPreAndPost(preOrder.begin() + index + 1 + leftSize, postOrder.end());
break; // 已找到根节点,跳出循环
}
}
return node;
}
int main() {
// 示例数据
vector<int> preOrder = {1, 2, 4, 5, 3};
vector<int> postOrder = {4, 5, 2, 3, 1};
TreeNode* tree = buildTreeFromPreAndPost(preOrder, postOrder);
// 测试遍历
cout << "Preorder traversal: ";
preorderTraversal(tree);
cout << endl;
cout << "Inorder traversal: ";
inorderTraversal(tree);
cout << endl;
cout << "Postorder traversal: ";
postorderTraversal(tree);
cout << endl;
return 0;
}
```
阅读全文