已知前序中序求后序c语言

已知一棵二叉树的前序遍历（Preorder）和中序遍历（Inorder），我们可以利用这两个序列重构出这棵树的后序遍历（Postorder）。因为前序、中序遍历可以唯一确定一棵树的结构，而后序遍历是先左子树、右子树、根节点的顺序。

以下是使用C语言的一个简单算法：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 根据前序和中序遍历重建后序遍历
TreeNode* buildTreeFromPreAndInOrder(int pre[], int in[], int n) {
    if (n <= 0)
        return NULL;

    // 中序遍历找到根节点的位置
    for (int i = 0; i < n; ++i) {
        if (in[i] == pre[0]) {
            TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
            root->val = pre[0];
            pre++;
            in += i + 1; // 留出右子树部分
            break;
        }
    }

    // 递归构建左右子树
    root->left = buildTreeFromPreAndInOrder(pre, in, n);
    root->right = buildTreeFromPreAndInOrder(pre, in, n);

    return root;
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->val); // 输出节点值
    }
}

int main() {
    int pre[] = {1, 2, 4, 5, 3};
    int in[] = {4, 2, 5, 1, 3};
    int n = sizeof(pre) / sizeof(pre[0]);

    TreeNode* root = buildTreeFromPreAndInOrder(pre, in, n);
    printf("后序遍历结果：");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

在这个示例中，`buildTreeFromPreAndInOrder`函数首先定位到前序遍历的第一个元素，即当前节点。然后分别对左子树和右子树进行递归处理，最后通过`postorderTraversal`打印出后序遍历的结果。