BtreeB树属于多叉树,在存储大量数据的时候可以降低层高,内节点和叶子节点都可以存储数据.B树的内节点不存储数据,用来做索引.B树的性质一颗M阶B数T满足一下条件1每个结点至多拥有M颗子树。2根结点至少拥有两颗子树。3除了根结点以外其余每个分支结点至少拥有M/2颗子树。(M为奇数时就向上取整)4所有叶子结点在同一层上。5有K颗子树的分支结点则存在K-1个关键字关键字按照递增顺序进行排序。6每个节点中的关键字数量满足ceil(M/2)-1 nM-1。ceil表示向上取整以M6为例,6阶B树.1每个结点至多拥有6颗子树。2根结点至少拥有两颗子树。3除了根结点以外其余每个分支结点至少拥有3颗子树。4所有叶子结点在同一层上。5有K颗子树的分支结点则存在K-1个关键字关键字按照递增顺序进行排序。6每个节点中的关键字数量满足2n5注意:结点的所有关键词都是有序的父节点的关键词,可以作为分割点分割开来子节点父节点的子节点的个数 父节点关键词的个数1插入规则: 先分裂再插入分裂条件: 结点中关键词个数等于M-1事例:见下图以二十六个字母为例。添加F的时候,根节点就需要分裂插入I的时候,最左侧结点也需要分裂插入R的时候,根节点需要分裂子节点的分裂:确定分裂的节点y创建一个空节点z把需要分裂节点y的中间关键词后面的关键词给空节点如果需要分裂节点y不是叶子结点,把需要分裂节点的后SUM_B个子树给分裂出来的节点z把分裂出来的节点z添加到y的父节点x的子树中把需要分裂节点y的中间关键词加入到父节点x中把需要分裂节点的中间以及后面的关键词给删除掉根节点分裂:创建一个空节点空节点指向根节点然后使用上面子节点的分裂 分裂根节点删除删除非叶子节点元素最终都会转换成删除叶子结点元素。不改变中序遍历。规则:如果结点中关键词个数等于ceil(M/2)-1就借位如果直接删除,关键词的个数小于ceil(M/2)-1,就合并借位借不到就合并合并:一个父节点和它的两个子节点(左节点和右节点)进行合并,合并到第一个子节点(左节点)上面确定父节点和两个需要合并的子节点把父节点需要合并的关键词拷贝到第一个子节点(左节点)上面把右节点的关键词拷贝到左节点上面如果左右节点不是叶子结点,就把右节点的子树拷贝到左节点上面销毁有节点把父节点的关键词和子节点都往前移动一位如果父节点是根节点需要单独考虑事例:删除A的时候,结点[CF]需要借位,借位后,结点[AB]需要合并删除B的时候,结点[FI]需要借位删除D的时候,结点[DE]需要合并删除E的时候,结点[IL]需要借位,但借不到,就合并完整代码这里的代码只存储key。下面还有一份优化代码存储key、value并且支持宏定义修改为int 或者 char*类型并增加查找修改功能。#include stdio.h #include stdlib.h #include string.h // 参考 //https://blog.csdn.net/Long_xu/article/details/126823578?spm1001.2014.3001.5502 //https://bbs.csdn.net/topics/619515305 #define SUB_M 3 // M6, and SUB_MM/2 typedef int KEY_VALUE; typedef struct _btree_node { //int keys[2 * SUB_M - 1]; // 存储关键字的个数M-1 KEY_VALUE *keys; // 存储关键字,节点有多个关键字 // void *value; // 存储数据 struct _btree_node **childrens; // 子树M int num; // 已存储的key数量 int leaf; // 是否为叶子结点 }btree_node; typedef struct _btree { btree_node *root; int t; // M阶tM/2 }btree; btree_node *btree_create_node(int t,int leaf) { btree_node *node (btree_node *)calloc(1, sizeof(btree_node)); if (node NULL) return NULL; node-keys (KEY_VALUE *)calloc(1, (2 * t - 1)*sizeof(KEY_VALUE)); if (node-keys NULL) { free(node); return NULL; } node-childrens (btree_node **)calloc(1, (2 * t)*sizeof(btree_node*)); if (node-childrens NULL) { free(node-keys); free(node); return NULL; } node-leaf leaf; node-num 0; return node; } void btree_destroy_node(btree_node *node) { if (node NULL) return; if (node-childrens ! NULL) free(node-childrens); if (node-keys ! NULL) free(node-keys); free(node); } /**********************分裂 split************************/ // 子节点分裂 void btree_split_child(btree *T, btree_node *x, int idx) { int t T-t; btree_node *y x-childrens[idx]; btree_node *z btree_create_node(t,y-leaf); z-num t - 1; int i 0; for (i 0; i t - 1; i) z-keys[i] y-keys[t i]; if (y-leaf 0)//inner,内节点 { for (i 0; i t; i) z-childrens[i] y-childrens[t i]; } y-num t-1; // 移动、插入结点 for (i x-num; i idx 1; i--) { x-childrens[i 1] x-childrens[i]; } x-childrens[idx 1] z; // key 交换 for (i x-num-1; i idx; i--) { x-keys[i 1] x-keys[i]; } x-keys[idx] y-keys[t-1]; x-num 1; } /*************************分裂 split end*****************************/ // 创建根结点 void btree_create(btree *T, int t) { T-t t; btree_node *x btree_create_node(t, 1); T-root x; } void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) { int i x-num - 1; if (x-leaf 1) { while (i 0 x-keys[i] k) { x-keys[i 1] x-keys[i]; i--; } x-keys[i 1] k; x-num 1; } else { while (i 0 x-keys[i] k) i--; if (x-childrens[i 1]-num (2 * (T-t)) - 1) { btree_split_child(T, x, i 1); if (k x-keys[i 1]) i; } btree_insert_nonfull(T, x-childrens[i 1], k); } } void btree_insert(btree *T, KEY_VALUE key) { btree_node *r T-root; if (r-num 2 * T-t - 1) { btree_node *node btree_create_node(T-t, 0); T-root node; node-childrens[0] r; btree_split_child(T, node, 0); int i 0; if (node-keys[0] key) i; btree_insert_nonfull(T, node-childrens[i], key); } else { btree_insert_nonfull(T, r, key); } } /*************************合并 merge*****************************/ void btree_merge(btree *T, btree_node *x, int idx) { btree_node *left x-childrens[idx]; btree_node *right x-childrens[idx 1]; int i 0; // 合并keys left-keys[T-t-1] x-keys[idx]; for (i 0; i T-t-1; i) { left-keys[T-t i] right-keys[i]; } // 如果不是子树需要拷贝结点 if (!left-leaf) { for (i 0; i T-t; i) { left-childrens[T-t i] right-childrens[i]; } } left-num T-t; btree_destroy_node(right); // x 的key前移 for (i idx 1; i x-num; i) { x-keys[i - 1] x-keys[i]; x-childrens[i] x-childrens[i 1]; } x-childrens[i 1] NULL; x-num - 1; if (x-num 0) { T-root left; btree_destroy_node(x); } } void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) { if (node NULL) return; int idx 0, i; while (idx node-num key node-keys[idx]) { idx; } if (idx node-num key node-keys[idx]) { if (node-leaf) { for (i idx; i node-num - 1; i) { node-keys[i] node-keys[i 1]; } node-keys[node-num - 1] 0; node-num--; if (node-num 0) { //root free(node); T-root NULL; } return; } else if (node-childrens[idx]-num T-t) { btree_node *left node-childrens[idx]; node-keys[idx] left-keys[left-num - 1]; btree_delete_key(T, left, left-keys[left-num - 1]); } else if (node-childrens[idx 1]-num T-t) { btree_node *right node-childrens[idx 1]; node-keys[idx] right-keys[0]; btree_delete_key(T, right, right-keys[0]); } else { btree_merge(T, node, idx); btree_delete_key(T, node-childrens[idx], key); } } else { btree_node *child node-childrens[idx]; if (child NULL) { printf(Cannot del key %d\n, key); return; } if (child-num T-t - 1) { btree_node *left NULL; btree_node *right NULL; if (idx - 1 0) left node-childrens[idx - 1]; if (idx 1 node-num) right node-childrens[idx 1]; if ((left left-num T-t) || (right right-num T-t)) { int richR 0; if (right) richR 1; if (left right) richR (right-num left-num) ? 1 : 0; if (right right-num T-t richR) { //borrow from next child-keys[child-num] node-keys[idx]; child-childrens[child-num 1] right-childrens[0]; child-num; node-keys[idx] right-keys[0]; for (i 0; i right-num - 1; i) { right-keys[i] right-keys[i 1]; right-childrens[i] right-childrens[i 1]; } right-keys[right-num - 1] 0; right-childrens[right-num - 1] right-childrens[right-num]; right-childrens[right-num] NULL; right-num--; } else { //borrow from prev for (i child-num; i 0; i--) { child-keys[i] child-keys[i - 1]; child-childrens[i 1] child-childrens[i]; } child-childrens[1] child-childrens[0]; child-childrens[0] left-childrens[left-num]; child-keys[0] node-keys[idx - 1]; child-num; node-keys[idx - 1] left-keys[left-num - 1]; left-keys[left-num - 1] 0; left-childrens[left-num] NULL; left-num--; } } else if ((!left || (left-num T-t - 1)) (!right || (right-num T-t - 1))) { if (left left-num T-t - 1) { btree_merge(T, node, idx - 1); child left; } else if (right right-num T-t - 1) { btree_merge(T, node, idx); } } } btree_delete_key(T, child, key); } } int btree_delete(btree *T, KEY_VALUE key) { if (!T-root) return -1; btree_delete_key(T, T-root, key); return 0; } /******************测试************************/ void btree_print(btree *T, btree_node *node, int layer) { btree_node* p node; int i; if (p) { printf(\nlayer %d keynum %d is_leaf %d\n, layer, p-num, p-leaf); for (i 0; i node-num; i) printf(%c , p-keys[i]); printf(\n); layer; for (i 0; i p-num; i) if (p-childrens[i]) btree_print(T, p-childrens[i], layer); } else printf(the tree is empty\n); } int main() { btree T { 0 }; btree_create(T, SUB_M); srand(48); int i 0; char key[30] ABCDEFGHIJKLMNOPQRSTUVWXYZ; for (i 0; i 26; i) { //key[i] rand() % 1000; printf(插入%c , key[i]); btree_insert(T, key[i]); //btree_print(T, T.root, 0); //printf(---------------------------------\n); } btree_print(T, T.root, 0); for (i 0; i 26; i) { printf(\n删除%c---------------------------------\n,key[25 - i]); btree_delete(T, key[25 - i]); //btree_traverse(T.root); btree_print(T, T.root, 0); } return 0; }优化的代码版本可以存储key、value并且支持宏定义修改为int 或者 char*类型并增加了查找和修改的功能。#include stdio.h #include stdlib.h #include string.h // 6阶B树 #define SUB_M 3 // M6, and SUB_MM/2 /* 必须完全懂得代码明白什么时候可以浅拷贝什么时候得深拷贝 浅拷贝我有一块内存你也有一块内存先释放你你再指向我 深拷贝你申请一块内存我copy给你我释放 */ #define KEY_TYPE_CHAR //#define KEY_TYPE_INT #ifdef KEY_TYPE_INT typedef int* KEY_TYPE; //可以修改key的类型 #endif #ifdef KEY_TYPE_CHAR typedef char* KEY_TYPE; #endif /* int --- char * 赋值 node-key del_node-key; --- void *temp node-key;// 这是交换啊 node-key del_node-key; del_node-key temp; 比较 if( a b ) -- strcmp(a,b) 0 */ typedef struct _btree_node { //int keys[2 * SUB_M - 1]; // 存储关键字的个数M-1 // KEY_TYPE* char**即 char* keys[2*t-1]。 keys是一数组存储的是字符型指针 KEY_TYPE *keys; // 存储关键字,节点有多个关键字 KEY_TYPE *values; // 存储数据 struct _btree_node **childrens; // 子树M int num; // 已存储的key数量 int leaf; // 是否为叶子结点 }btree_node; typedef struct _btree { btree_node *root; int node_count; int t; // M阶tM/2 }btree; char* strdup(const char* s) { if (!s) return NULL; char* p malloc(strlen(s) 1); if (p) strcpy(p, s); return p; } btree_node *btree_create_node(int t,int leaf) { btree_node *node (btree_node *)calloc(1, sizeof(btree_node)); if (node NULL) return NULL; node-keys (KEY_TYPE *)calloc(1, (2 * t - 1)*sizeof(KEY_TYPE)); if (node-keys NULL) { free(node); return NULL; } node-values (KEY_TYPE *)calloc(1, (2 * t - 1)*sizeof(KEY_TYPE)); if (node-values NULL) { free(node-keys); free(node); return NULL; } node-childrens (btree_node **)calloc(1, (2 * t)*sizeof(btree_node*)); if (node-childrens NULL) { free(node-keys); free(node-values); free(node); return NULL; } node-leaf leaf; node-num 0; return node; } void btree_destroy_node(btree_node *node) { if (node NULL) return; // 如果是内部节点应该先递归删除所有子节点 if (!node-leaf) { for (int i 0; i node-num; i) { if (node-childrens[i]) { btree_destroy_node(node-childrens[i]); } } } if (node-keys ! NULL) { for (int i 0; i node-num; i) { if (node-keys[i] ! NULL) { free(node-keys[i]); // 释放每个 char* 字符串 } } free(node-keys); // 释放指针数组本身 } if (node-values ! NULL) { for (int i 0; i node-num; i) { if (node-values[i] ! NULL) { free(node-values[i]); // 释放每个 char* 字符串 } } free(node-values); // 释放指针数组本身 } if (node-childrens ! NULL) { free(node-childrens); // 释放子节点指针数组 } free(node); } /**********************分裂 split************************/ // 子节点分裂 // x是需要分裂节点的父节点 // idx表示x节点下的第几颗子树 // 需要分裂的节点就是x下的第idx颗子树 void btree_split_child(btree *T, btree_node *x, int idx) { int t T-t; btree_node *y x-childrens[idx];// 需要分解的节点 btree_node *z btree_create_node(t, y-leaf); // 根节点是一分为三,这样就需要创建两个空节点,这里的代码参考btree_insert函数 // 非根节点是一分为二,需要创建一个空节点z z-num t - 1; int i 0; // 把需要分裂节点y中间关键词后面的关键词给空节点z for (i 0; i t - 1; i) { #ifdef KEY_TYPE_INT z-keys[i] y-keys[t i]; z-values[i] y-values[t i]; #endif #ifdef KEY_TYPE_CHAR // z-keys[i] y-keys[t i];// 浅拷贝 // z-values[i] y-values[t i]; z-keys[i] strdup(y-keys[t i]); // 深拷贝 key z-values[i] strdup(y-values[t i]); // 深拷贝 value // 不需要释放只需将原指针置NULL y-keys[t i] NULL; y-values[t i] NULL; #endif } if (y-leaf 0) // inner,内节点 { for (i 0; i t; i) { z-childrens[i] y-childrens[t i]; } } y-num t-1; // 移动、插入结点 for (i x-num; i idx 1; i--) { x-childrens[i 1] x-childrens[i]; } x-childrens[idx 1] z; // key 交换 for (i x-num-1; i idx; i--) { x-keys[i 1] x-keys[i]; x-values[i 1] x-values[i]; } x-keys[idx] y-keys[t-1]; x-values[idx] y-values[t-1]; x-num 1; } // 创建根结点 void btree_create(btree *T, int t) { T-t t; btree_node *x btree_create_node(t, 1); T-root x; T-node_count 0; } // 结点x插入关键词k void btree_insert_nonfull(btree *T, btree_node *x, KEY_TYPE key, KEY_TYPE value) { int i x-num - 1; if (x-leaf 1) { #ifdef KEY_TYPE_INT while (i 0 x-keys[i] key) #endif #ifdef KEY_TYPE_CHAR while (i 0 (strcmp(x-keys[i] , key) 0) ) { #endif x-keys[i 1] x-keys[i]; x-values[i 1] x-values[i]; i--; } #ifdef KEY_TYPE_INT x-keys[i 1] key; x-values[i 1] value; #endif #ifdef KEY_TYPE_CHAR x-keys[i 1] strdup(key); // 分配内存并拷贝字符串 x-values[i 1] strdup(value); // 分配内存并拷贝字符串 #endif /* #ifdef KEY_TYPE_CHAR x-keys[i 1] malloc(strlen(key) 1); memset(x-keys[i 1], 0, strlen(key) 1); strcpy(x-keys[i 1], key); x-values[i 1] malloc(strlen(value) 1); memset(x-values[i 1], 0, strlen(value) 1); strcpy(x-values[i 1], value); #endif */ x-num 1; } else { #ifdef KEY_TYPE_INT while (i 0 x-keys[i] key) i--; #endif #ifdef KEY_TYPE_CHAR while (i 0 (strcmp( x-keys[i] , key) 0)) i--; #endif if (x-childrens[i 1]-num (2 * (T-t)) - 1) { btree_split_child(T, x, i 1); #ifdef KEY_TYPE_INT if (key x-keys[i 1]) i; #endif #ifdef KEY_TYPE_CHAR if (strcmp(key , x-keys[i 1]) 0) i; #endif } btree_insert_nonfull(T, x-childrens[i 1], key, value); } } void btree_insert(btree *T, KEY_TYPE key, KEY_TYPE value) { btree_node *r T-root; if (r-num 2 * T-t - 1) { btree_node *node btree_create_node(T-t, 0); T-root node; node-childrens[0] r; btree_split_child(T, node, 0); int i 0; #ifdef KEY_TYPE_INT if (node-keys[0] key) i; #endif #ifdef KEY_TYPE_CHAR if(strcmp(node-keys[0],key) 0) i; #endif btree_insert_nonfull(T, node-childrens[i], key, value); } else { btree_insert_nonfull(T, r, key, value); } T-node_count; } /*************************合并 merge*****************************/ void btree_merge(btree *T, btree_node *x, int idx) { btree_node *left x-childrens[idx]; btree_node *right x-childrens[idx 1]; int i 0; // 合并keys left-keys[T-t-1] x-keys[idx]; left-values[T-t-1] x-values[idx]; x-keys[idx] NULL; // 置NULL避免重复释放 x-values[idx] NULL; for (i 0; i T-t-1; i) { left-keys[T-t i] right-keys[i]; left-values[T-t i] right-values[i]; right-keys[i] NULL; // 置NULL right-values[i] NULL; } // 如果不是子树需要拷贝结点 if (!left-leaf) { for (i 0; i T-t; i) { left-childrens[T-t i] right-childrens[i]; right-childrens[i] NULL; } } left-num T-t; right-num 0; // 清空计数避免btree_destroy_node时释放 //btree_destroy_node(right); // 只释放right节点本身不递归释放其子节点因为它们已被转移 if (right-childrens ! NULL) { free(right-childrens); right-childrens NULL; } free(right-keys); free(right-values); free(right); // x 的key前移 for (i idx 1; i x-num; i) { x-keys[i - 1] x-keys[i]; x-values[i - 1] x-values[i]; x-childrens[i] x-childrens[i 1]; } //x-childrens[i 1] NULL; x-childrens[x-num] NULL; x-num - 1; if (x-num 0) { T-root left; x-childrens[0] NULL; btree_destroy_node(x); } } void btree_delete_key(btree *T, btree_node *node, KEY_TYPE key) { if (node NULL) return; int idx 0, i; #ifdef KEY_TYPE_INT while (idx node-num key node-keys[idx]) { idx; } #endif #ifdef KEY_TYPE_CHAR while (idx node-num (strcmp(key , node-keys[idx]) 0)) { idx; } #endif #ifdef KEY_TYPE_INT if (idx node-num key node-keys[idx]) #endif #ifdef KEY_TYPE_CHAR if (idx node-num (strcmp(key , node-keys[idx]) 0)) { #endif if (node-leaf) { // 先释放要删除的key的内存 if (node-keys[idx]) { free(node-keys[idx]); node-keys[idx] NULL; } if (node-values[idx]) { free(node-values[idx]); node-values[idx] NULL; } for (i idx; i node-num - 1; i) { node-keys[i] node-keys[i 1]; node-values[i] node-values[i 1]; } node-keys[node-num - 1] NULL; node-values[node-num - 1] NULL; node-num--; if (node-num 0) { //root free(node); T-root NULL; } return; } else if (node-childrens[idx]-num T-t) { btree_node *left node-childrens[idx]; node-keys[idx] left-keys[left-num - 1]; node-values[idx] left-values[left-num - 1]; btree_delete_key(T, left, left-keys[left-num - 1]); } else if (node-childrens[idx 1]-num T-t) { btree_node *right node-childrens[idx 1]; node-keys[idx] right-keys[0]; node-values[idx] right-values[0]; btree_delete_key(T, right, right-keys[0]); } else { btree_merge(T, node, idx); btree_delete_key(T, node-childrens[idx], key); } } else { btree_node *child node-childrens[idx]; if (child NULL) { #ifdef KEY_TYPE_INT printf(Cannot del key %d\n, key); #endif #ifdef KEY_TYPE_CHAR printf(Cannot del key %s\n, key); #endif return; } if (child-num T-t - 1) { btree_node *left NULL; btree_node *right NULL; if (idx - 1 0) left node-childrens[idx - 1]; if (idx 1 node-num) right node-childrens[idx 1]; if ((left left-num T-t) || (right right-num T-t)) { int richR 0; if (right) richR 1; if (left right) richR (right-num left-num) ? 1 : 0; if (right right-num T-t richR) { //borrow from next child-keys[child-num] node-keys[idx]; child-values[child-num] node-values[idx]; child-childrens[child-num 1] right-childrens[0]; child-num; node-keys[idx] right-keys[0]; node-values[idx] right-values[0]; for (i 0; i right-num - 1; i) { right-keys[i] right-keys[i 1]; right-values[i] right-values[i 1]; right-childrens[i] right-childrens[i 1]; } right-keys[right-num - 1] 0; right-values[right-num - 1] 0; right-childrens[right-num - 1] right-childrens[right-num]; right-childrens[right-num] NULL; right-num--; } else { //borrow from prev for (i child-num; i 0; i--) { child-keys[i] child-keys[i - 1]; child-values[i] child-values[i - 1]; child-childrens[i 1] child-childrens[i]; } child-childrens[1] child-childrens[0]; child-childrens[0] left-childrens[left-num]; child-keys[0] node-keys[idx - 1]; child-values[0] node-values[idx - 1]; child-num; node-keys[idx - 1] left-keys[left-num - 1]; node-values[idx - 1] left-values[left-num - 1]; left-keys[left-num - 1] NULL; left-values[left-num - 1] NULL; left-childrens[left-num] NULL; left-num--; } } else if ((!left || (left-num T-t - 1)) (!right || (right-num T-t - 1))) { if (left left-num T-t - 1) { btree_merge(T, node, idx - 1); child left; } else if (right right-num T-t - 1) { btree_merge(T, node, idx); } } } btree_delete_key(T, child, key); } } int btree_delete(btree *T, KEY_TYPE key) { if (!T-root) return -1; btree_delete_key(T, T-root, key); T-node_count--; return 0; } // 节点数量 int btree_node_count(btree *T) { return T-node_count; } // 根据key查找value KEY_TYPE btree_search(btree *T, KEY_TYPE key) { if (!T || !T-root) return NULL; btree_node *node T-root; int idx 0; while (node ! NULL) { idx 0; // 在当前节点中查找key的位置 #ifdef KEY_TYPE_INT while (idx node-num key node-keys[idx]) { idx; } // 如果找到返回value if (idx node-num key node-keys[idx]) { return node-values[idx]; } #endif #ifdef KEY_TYPE_CHAR while (idx node-num strcmp(key, node-keys[idx]) 0) { idx; } // 如果找到返回value if (idx node-num strcmp(key, node-keys[idx]) 0) { return node-values[idx]; } #endif // 如果是叶子节点没找到 if (node-leaf) { break; } // 否则进入相应的子节点继续查找 node node-childrens[idx]; } return NULL; // 没找到 } // 根据key修改value int btree_update(btree *T, KEY_TYPE key, KEY_TYPE new_value) { if (!T || !T-root) return -1; btree_node *node T-root; int idx 0; int found 0; while (node ! NULL !found) { idx 0; // 在当前节点中查找key的位置 #ifdef KEY_TYPE_INT while (idx node-num key node-keys[idx]) { idx; } if (idx node-num key node-keys[idx]) { found 1; } #endif #ifdef KEY_TYPE_CHAR while (idx node-num strcmp(key, node-keys[idx]) 0) { idx; } if (idx node-num strcmp(key, node-keys[idx]) 0) { found 1; } #endif if (found) { // 找到key更新value #ifdef KEY_TYPE_CHAR // 对于字符串类型需要先释放原来的内存再分配新内存 if (node-values[idx] ! NULL) { free(node-values[idx]); } node-values[idx] strdup(new_value); #else // 对于整数类型直接赋值 node-values[idx] new_value; #endif return 0; // 修改成功 } // 如果是叶子节点没找到 if (node-leaf) { break; } // 否则进入相应的子节点继续查找 node node-childrens[idx]; } return -1; // 没找到key } /******************测试************************/ void btree_print(btree *T, btree_node *node, int layer) { btree_node* p node; int i; if (p) { printf(\nlayer %d keynum %d is_leaf %d\n, layer, p-num, p-leaf); for (i 0; i node-num; i) #ifdef KEY_TYPE_INT printf(key:%c value:%c, p-keys[i], p-values[i]); #endif #ifdef KEY_TYPE_CHAR printf(key:%s value:%s , p-keys[i], p-values[i]); #endif printf(\n); layer; for (i 0; i p-num; i) if (p-childrens[i]) btree_print(T, p-childrens[i], layer); } else printf(the tree is empty\n); } /****************** TEST FUNCTIONS ******************/ // 此测试代码由AI生成 void test_insert_search_update_delete() { printf(\n B-TREE TEST (INSERT/SEARCH/UPDATE/DELETE) \n); btree T {0}; btree_create(T, SUB_M); // Test data char *keys[] {dog, cat, fish, bird, snake, cow, sheep, horse}; char *values[] {bark, meow, bubble, tweet, hiss, moo, baa, neigh}; int n sizeof(keys) / sizeof(keys[0]); printf(\n--- 1. INSERT TEST ---\n); for (int i 0; i n; i) { printf(insert: key%s, value%s\n, keys[i], values[i]); btree_insert(T, keys[i], values[i]); } printf(\nTotal nodes: %d\n, btree_node_count(T)); printf(\n--- B-tree structure after insert ---\n); btree_print(T, T.root, 0); printf(\n--- 2. SEARCH TEST ---\n); char *search_keys[] {cat, horse, lion, dog, tiger}; for (int i 0; i 5; i) { char *result btree_search(T, search_keys[i]); if (result) { printf(search key%s, found value%s\n, search_keys[i], result); } else { printf(search key%s, not found\n, search_keys[i]); } } printf(\n--- 3. UPDATE TEST ---\n); printf(before update - cat: %s\n, btree_search(T, cat)); printf(updating cat value to purr\n); btree_update(T, cat, purr); printf(after update - cat: %s\n, btree_search(T, cat)); printf(\nbefore update - dog: %s\n, btree_search(T, dog)); printf(updating dog value to woof\n); btree_update(T, dog, woof); printf(after update - dog: %s\n, btree_search(T, dog)); printf(\ntrying to update non-existing key elephant:\n); int ret btree_update(T, elephant, trumpet); if (ret -1) { printf(update failed, key not found\n); } printf(\n--- B-tree structure after update ---\n); btree_print(T, T.root, 0); printf(\n--- 4. DELETE TEST ---\n); printf(deleting key: cat\n); btree_delete(T, cat); printf(search cat after delete: %s\n, btree_search(T, cat) ? found : not found); printf(\ndeleting key: fish\n); btree_delete(T, fish); printf(search fish after delete: %s\n, btree_search(T, fish) ? found : not found); printf(\ndeleting key: horse\n); btree_delete(T, horse); printf(search horse after delete: %s\n, btree_search(T, horse) ? found : not found); printf(\n--- B-tree structure after delete ---\n); btree_print(T, T.root, 0); printf(\n--- 5. FINAL SEARCH TEST ---\n); char *final_keys[] {dog, bird, snake, cow, sheep}; for (int i 0; i 5; i) { char *result btree_search(T, final_keys[i]); if (result) { printf(key%s, value%s\n, final_keys[i], result); } else { printf(key%s, not found\n, final_keys[i]); } } printf(\n--- Clean up ---\n); btree_destroy_node(T.root); printf(Test completed\n); } int main() { btree T { 0 }; btree_create(T, SUB_M); srand(48); int i 0; #ifdef KEY_TYPE_INT char key[30] ABCDEFGHIJKLMNOPQRSTUVWXYZ; char value[30] abcdefghijklmnopqrstuvwxyz; for (i 0; i 26; i) { //key[i] rand() % 1000; printf(insert key:%c value:%c, key[i], value[i]); btree_insert(T, key[i], value[i]); //btree_print(T, T.root, 0); //printf(---------------------------------\n); } btree_print(T, T.root, 0); for (i 0; i 26; i) { printf(\n del: %c---------------------------------\n,key[25 - i]); btree_delete(T, key[25 - i]); //btree_traverse(T.root); btree_print(T, T.root, 0); } #endif #ifdef KEY_TYPE_CHAR #if 0 char *keys[26] { aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, ll, mm, nn, oo, pp, qq, rr, ss, tt, uu, vv, ww, xx, yy, zz }; char *values[26] { Vaa, Vbb, Vcc, Vdd, Vee, Vff, Vgg, Vhh, Vii, Vjj, Vkk, Vll, Vmm, Vnn, Voo, Vpp, Vqq, Vrr, Vss, Vtt, Vuu, Vvv, Vww, Vxx, Vyy, Vzz }; for (i 0; i 26; i) { printf(insert key:%s value:%s\n, keys[i], values[i]); btree_insert(T, keys[i], values[i]); } printf(trv begin---------------------------------\n\n); btree_print(T, T.root, 0); printf(trv end---------------------------------\n\n); for (i 0; i 26; i) { printf(del: %s\n,keys[i]); btree_delete(T, keys[i]); printf(trv begin---------------------------------\n\n); btree_print(T, T.root, 0); printf(trv end---------------------------------\n\n); } #else test_insert_search_update_delete(); #endif #endif return 0; }