先序和中序 生成二叉树 c语言

在C语言中，使用先序（前序）和中序遍历结果来重建二叉树是一种经典的算法问题。先序遍历的特点是先访问根节点，然后遍历左子树，最后遍历右子树；而中序遍历的特点是先遍历左子树，然后访问根节点，最后遍历右子树。给定这两个序列，可以唯一确定一棵二叉树。

重建二叉树的基本思路是：
1. 在先序遍历序列中，第一个元素总是树的根节点。
2. 在中序遍历序列中，根节点将树分为左子树和右子树两部分。
3. 根据中序遍历中左子树和右子树的长度，可以在先序遍历序列中分别找到左子树和右子树的先序遍历序列。
4. 递归地对左子树和右子树重复上述过程，直到所有的子树都被构建完成。

下面是一个简化的C语言代码示例，演示了如何根据先序遍历和中序遍历序列重建二叉树：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    char value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 函数声明
TreeNode* buildTree(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd);
int findPosition(char* array, int start, int end, char key);

// 主函数，用于测试重建二叉树的过程
int main() {
    char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
    char inorder[] = {'D', 'B', 'E', 'A', 'C', 'F'};
    int length = sizeof(preorder) / sizeof(preorder[0]);
    
    TreeNode* root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1);
    
    // 这里可以添加代码以验证树的构建是否正确，例如通过遍历树等操作
    
    return 0;
}

// 递归构建二叉树的函数
TreeNode* buildTree(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return NULL;

    // 创建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->value = preorder[preStart];
    root->left = root->right = NULL;

    // 在中序遍历中找到根节点的位置
    int inRoot = findPosition(inorder, inStart, inEnd, root->value);

    // 计算左子树的大小
    int numsLeft = inRoot - inStart;

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

// 辅助函数，用于在数组中找到指定值的索引
int findPosition(char* array, int start, int end, char key) {
    for (int i = start; i <= end; i++) {
        if (array[i] == key) return i;
    }
    return -1;
}

这个代码示例展示了如何通过先序和中序遍历序列来构建二叉树。需要注意的是，这个示例假设树中没有重复的元素，并且为了简化问题，没有考虑释放分配的内存。