递归遍历建立二叉树用c语言实现

在C语言中，使用递归遍历建立二叉树通常有两种方式：前序遍历（Root-Left-Right）、中序遍历（Left-Root-Right）和后序遍历（Left-Right-Root）。这里我会分别给出前序、中序和后序构建二叉树的例子。假设我们已经有一个包含整数的数组，我们要将其转换成对应的二叉树。

**1. 前序遍历（根-左-右）**

struct TreeNode* buildTreePreOrder(int* preorder, int n) {
    if (n <= 0)
        return NULL;
    TreeNode* root = TreeNode{preorder[0], NULL, NULL};
    int index = 1;  // 前序遍历已访问的第一个元素的索引
    return recursiveBuildTreePreOrder(preorder + 1, n - 1, index, root);
}

TreeNode* recursiveBuildTreePreOrder(int* arr, int end, int start, TreeNode* current) {
    if (start > end)
        return NULL;

    TreeNode* left = recursiveBuildTreePreOrder(arr, end, start * 2 + 1, current->left);
    TreeNode* right = recursiveBuildTreePreOrder(arr, end, start * 2 + 2, current->right);

    current->left = left;
    current->right = right;
    return current;
}

**2. 中序遍历（左-根-右）**

struct TreeNode* buildTreeInOrder(int* inorder, int n) {
    return recursiveBuildTreeInOrder(inorder, n, 0, n - 1);
}

TreeNode* recursiveBuildTreeInOrder(int* arr, int end, int start, int mid) {
    if (start > mid)
        return NULL;

    TreeNode* root = recursiveBuildTreeInOrder(arr, mid, start, mid - 1);
    root->left = findLeftMost(arr + start, mid);
    return root;
}

TreeNode* findLeftMost(int* arr, int end) {
    while (arr[end] != NULL)
        end--;
    return TreeNode{arr[end], NULL, NULL};
}

**3. 后序遍历（左-右-根）**

struct TreeNode* buildTreePostOrder(int* postorder, int n) {
    return recursiveBuildTreePostOrder(postorder, n, 0, n - 1, NULL);
}

TreeNode* recursiveBuildTreePostOrder(int* arr, int end, int start, int mid, TreeNode* lastVisited) {
    if (start > mid)
        return NULL;

    TreeNode* root = recursiveBuildTreePostOrder(arr, end, mid + 1, end, lastVisited);
    TreeNode* left = lastVisited->left;
    TreeNode* right = lastVisited->right;

    lastVisited->left = recursiveBuildTreePostOrder(arr, mid, start, mid - 1, root);
    lastVisited->right = root;
    return lastVisited;
}