用c语言编程实现顺序查找、折半查找、二叉排序树和平衡二叉树

好的，以下是顺序查找、折半查找、二叉排序树和平衡二叉树的 C 语言实现：

顺序查找：

#include <stdio.h>

int sequential_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {3, 7, 1, 9, 2, 5};
    int n = sizeof(arr) / sizeof(int);
    int target = 9;

    int index = sequential_search(arr, n, target);
    if (index == -1) {
        printf("未找到 %d\n", target);
    } else {
        printf("找到 %d，下标为 %d\n", target, index);
    }

    return 0;
}

折半查找：

#include <stdio.h>

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(int);
    int target = 5;

    int index = binary_search(arr, n, target);
    if (index == -1) {
        printf("未找到 %d\n", target);
    } else {
        printf("找到 %d，下标为 %d\n", target, index);
    }

    return 0;
}

二叉排序树：

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void insert(struct TreeNode **root, int val) {
    if (*root == NULL) {
        *root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
        (*root)->val = val;
        (*root)->left = NULL;
        (*root)->right = NULL;
        return;
    }

    if (val < (*root)->val) {
        insert(&((*root)->left), val);
    } else {
        insert(&((*root)->right), val);
    }
}

void inorder_traversal(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder_traversal(root->left);
    printf("%d ", root->val);
    inorder_traversal(root->right);
}

int main() {
    struct TreeNode *root = NULL;

    insert(&root, 3);
    insert(&root, 1);
    insert(&root, 5);
    insert(&root, 2);
    insert(&root, 4);

    inorder_traversal(root);

    return 0;
}

平衡二叉树：

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    int height;  // 节点高度
};

struct TreeNode *new_node(int val) {
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return node;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int get_height(struct TreeNode *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

int get_balance_factor(struct TreeNode *node) {
    if (node == NULL) {
        return 0;
    }
    return get_height(node->left) - get_height(node->right);
}

struct TreeNode *left_rotate(struct TreeNode *node) {
    struct TreeNode *new_root = node->right;
    node->right = new_root->left;
    new_root->left = node;

    node->height = 1 + max(get_height(node->left), get_height(node->right));
    new_root->height = 1 + max(get_height(new_root->left), get_height(new_root->right));

    return new_root;
}

struct TreeNode *right_rotate(struct TreeNode *node) {
    struct TreeNode *new_root = node->left;
    node->left = new_root->right;
    new_root->right = node;

    node->height = 1 + max(get_height(node->left), get_height(node->right));
    new_root->height = 1 + max(get_height(new_root->left), get_height(new_root->right));

    return new_root;
}

void insert(struct TreeNode **root, int val) {
    if (*root == NULL) {
        *root = new_node(val);
        return;
    }

    if (val < (*root)->val) {
        insert(&((*root)->left), val);
    } else {
        insert(&((*root)->right), val);
    }

    (*root)->height = 1 + max(get_height((*root)->left), get_height((*root)->right));

    int balance_factor = get_balance_factor(*root);
    if (balance_factor > 1 && val < ((*root)->left)->val) {
        // LL
        *root = right_rotate(*root);
    } else if (balance_factor > 1 && val > ((*root)->left)->val) {
        // LR
        (*root)->left = left_rotate((*root)->left);
        *root = right_rotate(*root);
    } else if (balance_factor < -1 && val > ((*root)->right)->val) {
        // RR
        *root = left_rotate(*root);
    } else if (balance_factor < -1 && val < ((*root)->right)->val) {
        // RL
        (*root)->right = right_rotate((*root)->right);
        *root = left_rotate(*root);
    }
}

void inorder_traversal(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder_traversal(root->left);
    printf("%d ", root->val);
    inorder_traversal(root->right);
}

int main() {
    struct TreeNode *root = NULL;

    insert(&root, 3);
    insert(&root, 1);
    insert(&root, 5);
    insert(&root, 2);
    insert(&root, 4);

    inorder_traversal(root);

    return 0;
}

以上四种算法的时间复杂度分别为：

- 顺序查找：最坏时间复杂度为 O(n)，平均时间复杂度为 O(n)；
- 折半查找：最坏时间复杂度为 O(log n)，平均时间复杂度为 O(log n)；
- 二叉排序树：最坏时间复杂度为 O(n)，平均时间复杂度为 O(log n)；
- 平衡二叉树：最坏时间复杂度为 O(log n)，平均时间复杂度为 O(log n)。