先序遍历和中序遍历还原二叉树，并输出先序遍历、中序遍历和后序遍历后的结果C++

先序遍历（Preorder Traversal）和中序遍历（Inorder Traversal）通常用于构建二叉树，尤其是当给定的是两个遍历序列时。下面是一个简单的C++示例，展示了如何利用这两个遍历顺序来重构二叉树并计算其相应的遍历结果： ```cpp // 假设我们有先序遍历pre[]和中序遍历in[]作为输入 // 定义二叉树节点结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; // 通过先序遍历重建二叉树 TreeNode* buildTree(vector<int>& pre, vector<int>& in, int start, int end) { if (start > end) return nullptr; // 先序遍历的第一个元素是当前节点 TreeNode* root = new TreeNode(pre[start]); // 找到该节点在中序遍历中的位置 int index = find(in.begin(), in.end(), pre[start]); // 中序遍历的剩余部分用于左右子树的创建 int leftEnd = index - 1; int rightStart = index + 1; // 分别递归地构建左子树和右子树 root->left = buildTree(pre, in, start + 1, leftEnd); root->right = buildTree(pre, in, rightStart, end); return root; } // 先序遍历、中序遍历和后序遍历的实现 void printPreOrder(TreeNode* root) { if (root != nullptr) { cout << root->val << " "; printPreOrder(root->left); printPreOrder(root->right); } } void printInOrder(TreeNode* root) { if (root != nullptr) { printInOrder(root->left); cout << root->val << " "; printInOrder(root->right); } } void printPostOrder(TreeNode* root) { if (root != nullptr) { printPostOrder(root->left); printPostOrder(root->right); cout << root->val << " "; } } int main() { // 假设你已经有了pre和in数组，这里省略实际调用 auto treeRoot = buildTree(pre, in, 0, pre.size() - 1); // 输出先序遍历、中序遍历和后序遍历的结果 cout << "Preorder traversal: "; printPreOrder(treeRoot); cout << "\nInorder traversal: "; printInOrder(treeRoot); cout << "\nPostorder traversal: "; printPostOrder(treeRoot); return 0; }[^1] ``` 在这个代码中，`buildTree()`函数负责根据先序遍历和中序遍历构建二叉树，而`printPreOrder()`, `printInOrder()`, 和 `printPostOrder()` 函数则分别用于打印不同遍历方式下的结果。