前序序列和中序序列构建二叉树c语言

二叉树的前序遍历是先访问根节点，再访问左子树，最后访问右子树；中序遍历是先访问左子树，再访问根节点，最后访问右子树。因此，如果给出二叉树的前序序列和中序序列，可以通过递归的方式构建整棵二叉树。

具体实现如下：

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

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

// 通过前序序列和中序序列构建二叉树
Node* buildTree(int* preorder, int* inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return NULL;
    }

    // 前序序列的第一个元素为根节点
    int rootVal = preorder[preStart];
    Node* root = (Node*) malloc(sizeof(Node));
    root->data = rootVal;

    // 在中序序列中找到根节点的位置
    int rootIndex;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }

    // 递归构建左子树
    root->left = buildTree(preorder, inorder, preStart + 1, preStart + rootIndex - inStart, inStart, rootIndex - 1);

    // 递归构建右子树
    root->right = buildTree(preorder, inorder, preStart + rootIndex - inStart + 1, preEnd, rootIndex + 1, inEnd);

    return root;
}

// 二叉树的中序遍历
void inorderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }

    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    int inorder[] = {4, 2, 5, 1, 6, 3, 7};

    Node* root = buildTree(preorder, inorder, 0, 6, 0, 6);

    printf("中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

上述代码中，`buildTree` 函数通过前序序列和中序序列以及其对应的索引范围来构建二叉树。主要的实现思路是首先找到根节点，然后递归构建左子树和右子树。`inorderTraversal` 函数用来验证构建的二叉树是否正确。