按扩展二叉树的先序遍历结果构造二叉树的算法c语言完整代码

在C语言中，按扩展二叉树的先序遍历结果构造二叉树是一个常见的数据结构操作。这里提供一个简单的示例，假设我们已经得到了一个递归的先序遍历数组，数组的第一个元素是根节点，接下来的元素按照左子树、右子树的顺序排列。

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

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

// 创建新节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    newNode->val = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 根据先序遍历重构二叉树
TreeNode* buildTree(int* preorder, int n) {
    if (n <= 0) return NULL; // 遍历结束或空数组

    // 先序遍历的第一个元素是根节点
    TreeNode* root = createNode(preorder[0]);
    
    // 使用递归处理剩余元素
    int i = 1;
    while (i < n) {
        // 找到当前根节点的左子树位置
        int leftSubtreeSize = preorder[i] ? 1 : 0; // 如果preorder[i]非零，说明有左子树
        for (int j = i + 1; j < n && preorder[j] != preorder[i]; j++) {
            leftSubtreeSize++;
        }

        // 为根节点创建左子树
        root->left = buildTree(&preorder[i+1], leftSubtreeSize);

        // 移动指针到右子树开始的位置
        i += leftSubtreeSize + 1;
    }
    return root;
}

// 辅助函数，用于打印二叉树
void printInOrder(TreeNode* node) {
    if (node == NULL) return;
    printInOrder(node->left);
    printf("%d ", node->val);
    printInOrder(node->right);
}

int main() {
    int preorder[] = {1, 2, 4, 5, 3, 6, 7}; // 假设这是先序遍历的结果
    int n = sizeof(preorder) / sizeof(preorder[0]);

    TreeNode* root = buildTree(preorder, n);
    if (root) {
        printf("Constructed tree using preorder traversal:\n");
        printInOrder(root); // 输出构建的二叉树
    } else {
        printf("Failed to build the tree.\n");
    }

    return 0;
}

在这个例子中，`buildTree`函数是核心，它通过先序遍历信息逐步构建二叉树。注意，这个实现假设输入的先序遍历数组是有效的，并且每个节点的值都是唯一的。如果需要处理其他情况，可能需要进行额外的错误检查和调整。