c++前序中序求二叉树

在C++中，前序遍历（Pre-order Traversal）和中序遍历（In-order Traversal）是两种基本的树遍历方式，它们通常用于二叉树。前序遍历是指先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。中序遍历则是先访问左子树，然后访问根节点，最后访问右子树。

要根据前序遍历和中序遍历的结果重建一棵二叉树，你需要遵循以下步骤：

1. 前序遍历的第一个元素总是树的根节点。
2. 在中序遍历中找到根节点的位置，这样就能确定左子树的中序遍历和右子树的中序遍历。
3. 根据左子树的节点数量，可以在前序遍历中划分出左子树的前序遍历和右子树的前序遍历。
4. 递归地使用上述步骤构建左子树和右子树。

下面是一个简单的例子，假设我们有以下前序和中序遍历的结果：

前序遍历：[根节点, 左子树节点, 右子树节点]
中序遍历：[左子树节点, 根节点, 右子树节点]

具体实现中，你需要编写递归函数来处理这些逻辑，并且创建相应的树节点。

下面是一个简单的C++代码示例，用于根据前序和中序遍历的结果重建二叉树：

#include <iostream>
#include <vector>
using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 函数声明
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd);

// 主函数，用于初始化和调用辅助函数
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) return NULL;
    return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}

// 辅助函数，用于递归构建树
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return NULL;

    // 前序遍历的第一个值是根节点
    TreeNode* root = new TreeNode(preorder[preStart]);

    // 在中序遍历中找到根节点的位置，来确定左子树和右子树的大小
    int inRoot = inStart;
    while (inorder[inRoot] != root->val && inRoot <= inEnd) {
        inRoot++;
    }

    int leftTreeSize = inRoot - inStart;

    // 递归构建左子树和右子树
    root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, inRoot - 1);
    root->right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd, inorder, inRoot + 1, inEnd);

    return root;
}

// 主函数入口
int main() {
    vector<int> preorder = {3, 9, 20, 15, 7}; // 前序遍历结果
    vector<int> inorder = {9, 3, 15, 20, 7};  // 中序遍历结果
    TreeNode* root = buildTree(preorder, inorder);

    // 这里可以添加代码来验证重建的树是否正确，例如通过后序遍历来打印树的节点
    // ...

    return 0;
}

这段代码只是重建树的一个基本实现，没有包含释放树节点内存的操作。在实际应用中，还需要考虑内存管理以避免内存泄漏。