使用C语言代码生成一个B树
时间: 2023-11-27 17:07:42 浏览: 45
好的,下面是一个简单的B树实现的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define M 3
typedef struct node {
int n;
int keys[M - 1];
struct node *p[M];
} node;
node *root = NULL;
void insert(int key);
void split(node *x, int i);
void set_key(node *x, int i, int k);
void insert_nonfull(node *x, int k);
void traverse(node *x);
int main() {
int n, i, x;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter the elements: ");
for (i = 0; i < n; i++) {
scanf("%d", &x);
insert(x);
}
printf("Traversal of constructed tree:\n");
traverse(root);
return 0;
}
void insert(int key) {
if (root == NULL) { // create a new tree
root = (node *)malloc(sizeof(node));
root->keys[0] = key;
root->n = 1;
} else {
if (root->n == M - 1) { // if root is full, split it
node *s = (node *)malloc(sizeof(node));
s->p[0] = root;
split(s, 0);
root = s;
}
insert_nonfull(root, key);
}
}
void split(node *x, int i) {
node *z = (node *)malloc(sizeof(node));
node *y = x->p[i];
z->n = M / 2 - 1;
int j;
for (j = 0; j < M / 2 - 1; j++)
z->keys[j] = y->keys[j + M / 2];
if (!y->leaf) {
for (j = 0; j < M / 2; j++)
z->p[j] = y->p[j + M / 2];
}
y->n = M / 2 - 1;
for (j = x->n; j >= i + 1; j--)
x->p[j + 1] = x->p[j];
x->p[i + 1] = z;
for (j = x->n - 1; j >= i; j--)
set_key(x, j + 1, x->keys[j]);
set_key(x, i, y->keys[M / 2 - 1]);
x->n++;
}
void set_key(node *x, int i, int k) {
x->keys[i] = k;
}
void insert_nonfull(node *x, int k) {
int i = x->n - 1;
if (x->leaf) {
while (i >= 0 && k < x->keys[i]) {
set_key(x, i + 1, x->keys[i]);
i--;
}
set_key(x, i + 1, k);
x->n++;
} else {
while (i >= 0 && k < x->keys[i])
i--;
i++;
if (x->p[i]->n == M - 1) {
split(x, i);
if (k > x->keys[i])
i++;
}
insert_nonfull(x->p[i], k);
}
}
void traverse(node *x) {
int i;
for (i = 0; i < x->n; i++) {
if (!x->leaf)
traverse(x->p[i]);
printf("%d ", x->keys[i]);
}
if (!x->leaf)
traverse(x->p[i]);
}
```
这个B树每个节点最多有3个子节点(M = 3),可以通过修改定义中的M来改变节点大小。另外,这里使用了一个简单的方法来遍历树,输出所有的键值。你可以根据需要修改代码实现其他操作。