c语言折半查找和二叉树的区别

折半查找和二叉树都是常用的查找算法，它们的区别如下：

1. 数据结构不同：折半查找是在一个有序数组中进行查找，而二叉树是一种树形结构，每个节点可以有左右子树。

2. 时间复杂度不同：折半查找的时间复杂度为O(logn)，而二叉树的时间复杂度取决于树的形态，最坏情况下可以达到O(n)，但通常情况下是O(logn)。

3. 空间复杂度不同：折半查找的空间复杂度为O(1)，而二叉树的空间复杂度取决于树的节点数，最坏情况下可以达到O(n)。

4. 插入和删除操作不同：对于有序数组，插入和删除操作会导致数组重新排序，效率较低；而对于二叉树，插入和删除操作可以通过调整树的结构来实现，效率较高。

综上所述，折半查找适用于静态查找，即数据不经常变动的情况下；而二叉树适用于动态查找，即数据经常变动的情况下。

相关问题

用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)。

用c语言1.定义长度为n的查找表，m个待查找数据，定义二叉树排序树的结点结构。 2.初始化随机数发生器，产生n个随机数构成的查找表并用简单选择排序。 3.创建顺序查找、折半查找、创建二叉排序树、二叉排序树查找，取得当前系统时间函数。 4.调用顺序查找、折半查找、二叉排序树查找函数，输出在长度为n的查找表中，查找m个数据耗费的总时间。

以下是用C语言实现的代码：

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

#define MAX_SIZE 100

typedef struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

void initTable(int table[], int size) {
    srand(time(NULL));
    for (int i = 0; i < size; i++) {
        table[i] = rand() % MAX_SIZE;
    }
}

void selectionSort(int table[], int size) {
    int i, j, minIdx, temp;
    for (i = 0; i < size - 1; i++) {
        minIdx = i;
        for (j = i + 1; j < size; j++) {
            if (table[j] < table[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            temp = table[i];
            table[i] = table[minIdx];
            table[minIdx] = temp;
        }
    }
}

int sequentialSearch(int table[], int size, int key) {
    for (int i = 0; i < size; i++) {
        if (table[i] == key) {
            return i;
        }
    }
    return -1;
}

int binarySearch(int table[], int size, int key) {
    int low = 0, high = size - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (table[mid] == key) {
            return mid;
        } else if (table[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

BSTNode* createBST(int table[], int size) {
    BSTNode* root = NULL;
    for (int i = 0; i < size; i++) {
        BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
        newNode->data = table[i];
        newNode->left = newNode->right = NULL;

        if (root == NULL) {
            root = newNode;
        } else {
            BSTNode* current = root;
            while (1) {
                if (table[i] < current->data) {
                    if (current->left == NULL) {
                        current->left = newNode;
                        break;
                    }
                    current = current->left;
                } else {
                    if (current->right == NULL) {
                        current->right = newNode;
                        break;
                    }
                    current = current->right;
                }
            }
        }
    }
    return root;
}

int BSTSearch(BSTNode* root, int key) {
    while (root != NULL) {
        if (root->data == key) {
            return 1;
        } else if (root->data > key) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return 0;
}

int main() {
    int table[MAX_SIZE], m;
    printf("请输入查找表的长度（不超过100）：");
    int n;
    scanf("%d", &n);
    printf("请输入待查找的数据个数：");
    scanf("%d", &m);

    initTable(table, n);
    selectionSort(table, n);

    int key;
    clock_t start, end;
    double duration;

    // 顺序查找
    start = clock();
    for (int i = 0; i < m; i++) {
        key = rand() % MAX_SIZE;
        sequentialSearch(table, n, key);
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("顺序查找 %d 个数据耗时 %lf 秒\n", m, duration);

    // 折半查找
    start = clock();
    for (int i = 0; i < m; i++) {
        key = rand() % MAX_SIZE;
        binarySearch(table, n, key);
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("折半查找 %d 个数据耗时 %lf 秒\n", m, duration);

    // 二叉排序树查找
    BSTNode* root = createBST(table, n);
    start = clock();
    for (int i = 0; i < m; i++) {
        key = rand() % MAX_SIZE;
        BSTSearch(root, key);
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("二叉排序树查找 %d 个数据耗时 %lf 秒\n", m, duration);

    return 0;
}

这段代码实现了以下功能：

1. 初始化长度为n的随机查找表，用简单选择排序进行排序。
2. 实现顺序查找、折半查找、创建二叉排序树、二叉排序树查找。
3. 针对每种查找方法，随机生成m个数据，输出在长度为n的查找表中查找这m个数据所耗费的总时间。