二叉树的遍历问题求中序遍历

Question

博主有能C++代码实现 已知二叉树的先序和后序遍历求中序遍历的程序吗？想看看谢谢

Answer 1

引自免费微信小程序：皆我百晓生

在C++中，可以使用递归的方法来解决这个问题。首先我们需要定义一个二叉树节点的数据结构，然后编写函数来根据已知的先序和后序遍历结果构建二叉树，并进行中序遍历。

以下是完整的C++代码实现：

#include <iostream>
#include <vector>

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

// 根据先序和后序遍历创建二叉树
TreeNode* buildTree(std::vector<int>& preOrder, std::vector<int>& postOrder, int& preIndex, int start, int end) {
    if (start > end) return nullptr;

    // 先序遍历的第一个元素作为根节点
    TreeNode* root = new TreeNode(preOrder[preIndex++]);

    // 找到后序遍历中的根节点位置
    int rootPosInPostOrder = 0;
    for (int i = start; i <= end; ++i) {
        if (postOrder[i] == root->val) {
            rootPosInPostOrder = i;
            break;
        }
    }

    // 构建左子树
    root->left = buildTree(preOrder, postOrder, preIndex, start, rootPosInPostOrder - 1);

    // 构建右子树
    root->right = buildTree(preOrder, postOrder, preIndex, rootPosInPostOrder + 1, end);

    return root;
}

// 中序遍历二叉树
void inorderTraversal(TreeNode* node) {
    if (node == nullptr) return;

    inorderTraversal(node->left);
    std::cout << node->val << " ";
    inorderTraversal(node->right);
}

int main() {
    std::vector<int> preOrder = {1, 2, 4, 7, 3, 5, 6};
    std::vector<int> postOrder = {4, 7, 2, 6, 5, 3, 1};

    int preIndex = 0;
    TreeNode* root = buildTree(preOrder, postOrder, preIndex, 0, preOrder.size() - 1);

    std::cout << "Inorder traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

这段代码首先定义了一个TreeNode结构体来表示二叉树节点，然后定义了buildTree函数，这个函数是递归地根据给定的先序和后序遍历数组构建二叉树。最后，我们有一个inorderTraversal函数用于执行中序遍历。

在main函数中，我们给出了一个具体的例子，展示了如何使用这些函数来重建二叉树并进行中序遍历。运行此代码将输出中序遍历的结果：4 2 7 1 5 3 6。

请注意，这个方法只适用于完全二叉树（即除了最后一层外，其他层的所有节点都尽可能向左靠拢）。对于非完全二叉树，这种方法可能无法正确构建二叉树。