B树的顺序查找的完整代码

B树是一种自平衡的树形数据结构，常用于数据库和文件系统中。B树的顺序查找可以通过递归实现，以下是一个简单的C语言B树顺序查找的代码示例：

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

#define M 3

typedef struct node {
    int n; // 节点中关键字的个数
    int keys[M - 1]; // 关键字数组
    struct node *children[M]; // 子节点指针数组
} node;

node *root = NULL;

// 创建一个新节点
node *new_node(int key) {
    node *new = (node *)malloc(sizeof(node));
    new->n = 1;
    new->keys[0] = key;
    for (int i = 0; i < M; i++) {
        new->children[i] = NULL;
    }
    return new;
}

// 插入一个关键字到节点中
void insert_key(node *n, int key) {
    int i = n->n - 1;
    while (i >= 0 && n->keys[i] > key) {
        n->keys[i + 1] = n->keys[i];
        i--;
    }
    n->keys[i + 1] = key;
    n->n++;
}

// 分裂节点
void split_node(node *parent, int pos, node *child) {
    node *new = new_node(child->keys[M / 2]);
    child->n = M / 2;
    new->n = M - M / 2 - 1;
    for (int i = 0; i < new->n; i++) {
        new->keys[i] = child->keys[i + M / 2 + 1];
    }
    if (child->children[0] != NULL) {
        for (int i = 0; i < M - M / 2; i++) {
            new->children[i] = child->children[i + M / 2 + 1];
        }
    }
    for (int i = parent->n; i > pos; i--) {
        parent->children[i + 1] = parent->children[i];
        parent->keys[i] = parent->keys[i - 1];
    }
    parent->children[pos + 1] = new;
    parent->keys[pos] = child->keys[M / 2 - 1];
    parent->n++;
}

// 插入一个关键字到B树中
void insert(int key) {
    if (root == NULL) {
        root = new_node(key);
        return;
    }
    node *cur = root;
    node *parent = NULL;
    int pos = -1;
    while (cur != NULL) {
        pos = -1;
        for (int i = 0; i < cur->n; i++) {
            if (cur->keys[i] == key) {
                return;
            }
            if (cur->keys[i] > key) {
                pos = i;
                break;
            }
        }
        if (pos == -1) {
            pos = cur->n;
        }
        if (cur->children[0] != NULL) {
            parent = cur;
            cur = cur->children[pos];
            continue;
        }
        insert_key(cur, key);
        if (cur->n == M) {
            if (parent == NULL) {
                parent = new_node(0);
                root = parent;
                parent->children[0] = cur;
            }
            split_node(parent, pos, cur);
        }
        return;
    }
}

// 在B树中查找一个关键字
node *search(int key) {
    node *cur = root;
    while (cur != NULL) {
        for (int i = 0; i < cur->n; i++) {
            if (cur->keys[i] == key) {
                return cur;
            }
            if (cur->keys[i] > key) {
                cur = cur->children[i];
                break;
            }
            if (i == cur->n - 1) {
                cur = cur->children[i + 1];
                break;
            }
        }
    }
    return NULL;
}

// 打印B树
void print_tree(node *cur) {
    if (cur == NULL) {
        return;
    }
    for (int i = 0; i < cur->n; i++) {
        printf("%d ", cur->keys[i]);
    }
    printf("\n");
    if (cur->children[0] != NULL) {
        for (int i = 0; i <= cur->n; i++) {
            print_tree(cur->children[i]);
        }
    }
}

int main() {
    insert(1);
    insert(2);
    insert(3);
    insert(4);
    insert(5);
    insert(6);
    insert(7);
    insert(8);
    insert(9);
    insert(10);
    print_tree(root);
    node *result = search(5);
    if (result != NULL) {
        printf("Found %d\n", result->keys[0]);
    } else {
        printf("Not found\n");
    }
    return 0;
}