在这里实现的是在主存中的操作，没有进行文件的存储和修改。
头文件btree.h：
1#ifndef _BTREE_H 2#define _BTREE_H 3 4#define MIN_T 3 5#define MAX_T (MIN_T * 2) 6 7typedef struct BTreeNodedata BTreeNodedata; 8typedef struct BTreeNodedata *BTreeNode; 9typedef struct BTreedata BTreedata; 10typedef struct BTreedata *BTree; 11 12/* 13 * B树结点结构体 14 */ 15struct BTreeNodedata 16{ 17 int n; //关键字个数 18 int leaf; 是否是叶子结点，1为叶子结点，0反之 19 int key[MAX_T - 1]; //关键字，这里的关键字为了简便编程设为int 20 BTreeNode child[MAX_T]; //子结点 21}; 22 23/* 24 * B树的结构体 25 */ 26struct BTreedata 27{ 28 BTreeNode root; //B树的根结点 29}; 30 31#define BTREE_NODE_SIZE sizeof(BTreeNodedata) 32#define BTREE_SIZE sizeof(BTreedata) 33 34BTreeNode allocate_node(); //为结点分配空间 35void btree_create(BTree tree); //初始化树 36void btree_search(BTreeNode node, int key); //寻找关键字位置 37void btree_split_child(BTreeNode node, int location); //分裂子结点 38void btree_insert_nonfull(BTreeNode node, int key); //向未满结点插入关键字 39void btree_insert(BTree tree, int key); //向树插入关键字 40void display_node(BTreeNode *node_first, int n); //显示以结点node_first为父结点的树 41void display_btree(BTree tree); //显示整棵树 42BTreeNode btree_minimum(BTreeNode node); //以node为根结点，寻找最小关键字 43BTreeNode btree_maximum(BTreeNode node); //以node为根结点，寻找最大关键字 44void btree_min(BTree tree); //在整棵树中寻找最小关键字 45void btree_max(BTree tree); //在整棵树中寻找最大关键字 46void btree_left(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location); //将父结点、右兄弟、该结点的关键字调整 47void btree_right(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location); //将父结点、左兄弟、该结点的关键字调整 48int btree_merge_child(BTreeNode parent, int location); //合并子结点，并返回下降子结点的位置 49void btree_delete_leaf(BTreeNode node, int location); //删除叶子结点关键字 50int btree_delete_node_in(BTreeNode r_node, int i); //删除内结点关键字，并返回下降子结点的位置 51void btree_delete_node(BTreeNode r_node, int key); //删除以r_node为根结点的树中关键字 52void btree_delete(BTree tree, int key); //删除树中的关键字 53 54#endif
程序btree.c：
1#include "btree.h" 2#include <stdio.h> 3#include <stdlib.h> 4#include <memory.h> 5#include <assert.h> 6 7/* 8 * 为新结点分配空间 9 */ 10BTreeNode 11allocate_node() 12{ 13 BTreeNode node = (BTreeNode) malloc (BTREE_NODE_SIZE); 14 15 return node; 16} 17 18/* 19 * 生成一棵空树 20 * 关键字个数为0，且为叶子结点 21 */ 22void 23btree_create(BTree tree) 24{ 25 BTreeNode r_node = allocate_node(); 26 27 (r_node)->n = 0; 28 (r_node)->leaf = 1; 29 30 (tree)->root = r_node; 31} 32 33/* 34 * 在以node为根结点的树中，寻找关键字位置 35 * 返回关键字所在结点，并将关键字位置保存在location 36 */ 37void 38btree_search(BTreeNode node, int key) 39{ 40 41 int j = 0; 42 43 /* 44 * 遍历当前结点，寻找恰当的关键字，如果找到相等的关键字，返回结点并将关键字位置保存在location 45 * 如果没找到相等结点，且该结点为叶子结点，则报错 46 * 否则递归寻找 47 */ 48 while(j < node->n && key > node->key[j]) 49 j++; 50 if(j < node->n && key == node->key[j]) 51 { 52 printf("the %d key's location is %d in the node %p\n", key, j, node); 53 } 54 else if(node->leaf) 55 { 56 printf("error:there is no a key\n"); 57 } 58 else btree_search(node->child[j], key); 59} 60 61/* 62 * 分裂父结点node中位置为location的子结点的满结点 63 */ 64void 65btree_split_child(BTreeNode node, int location) 66{ 67 /* 建立新的空结点 */ 68 BTreeNode newnode = allocate_node(); 69 BTreeNode childnode = node->child[location]; 70 71 int i = 0; 72 73 /* 初始化空结点newnode，将子结点childnode的信息复制到新结点node中 */ 74 newnode->leaf = childnode->leaf; 75 newnode->n = MIN_T - 1; 76 77 /* 将子结点childnode后T-1个关键字复制到新结点中，并改变子结点的n值 */ 78 for(i = 0;i <= MIN_T - 2;i++) 79 newnode->key[i] = childnode->key[i + MIN_T]; 80 81 childnode->n = MIN_T - 1; 82 83 /* 如果子结点非叶子结点，则相应的将子结点的结点点复制到新结点中 */ 84 if(!childnode->leaf) 85 for(i = 0;i <= MIN_T - 1;i++) 86 newnode->child[i] = childnode->child[i + MIN_T]; 87 88 /* 将父结点对应的关键字以及子结点位置向后移动一位 */ 89 for(i = node->n;i > location;i--) 90 { 91 node->key[i] = node->key[i - 1]; 92 node->child[i+1] = node->child[i]; 93 } 94 95 /* 为父结点增加新的关键字和子结点，并修改n值 */ 96 node->child[location + 1] = newnode; 97 node->key[location] = childnode->key[MIN_T - 1]; 98 node->n = node->n + 1; 99 100} 101 102/* 103 * 对非满结点进行插入关键字 104 */ 105void 106btree_insert_nonfull(BTreeNode node, int key) 107{ 108 int i = node->n - 1; 109 110 if(node->leaf) 111 { 112 /* 该结点为叶子结点时，找到对应位置，将关键字插入，并对结点node做出修改 */ 113 while(i >=0 && key < node->key[i]) 114 { 115 node->key[i+1] = node->key[i]; 116 i--; 117 } 118 119 node->key[i+1] = key; 120 node->n = node->n + 1; 121 } 122 else 123 { 124 /* 非叶子结点时，查找对应子结点，判断其是否为满结点，是，则分裂，否递归插入 */ 125 while(i >=0 && key < node->key[i]) 126 i--; 127 i++; 128 if(node->child[i]->n == MAX_T - 1) 129 { 130 btree_split_child(node, i); 131 if(key > node->key[i]) 132 i++; 133 } 134 135 btree_insert_nonfull(node->child[i], key); 136 } 137} 138 139/* 140 * 对整棵树进行插入关键字 141 * 当树为有且只有一个关键字，且已满时，需要建立新的结点作为树的根结点， 142 * 而当原树的根结点作为新结点的子结点，进行分裂操作 143 * 否则，直接进行非满结点插入操作 144 */ 145void 146btree_insert(BTree tree, int key) 147{ 148 BTreeNode r_node = tree->root; 149 150 if(r_node->n == MAX_T - 1) 151 { 152 BTreeNode r_node_new = allocate_node(); 153 154 r_node_new->leaf = 0; 155 r_node_new->n = 0; 156 r_node_new->child[0] = r_node; 157 tree->root = r_node_new; 158 btree_split_child(r_node_new, 0); 159 btree_insert_nonfull(r_node_new, key); 160 } 161 else btree_insert_nonfull(r_node, key); 162} 163 164/* 165 * 为了验证插入以及删除结果正确，添加输出函数 166 * 输出以parent为父结点的子树的所有关键字 167 * 这里将所有的同一层的结点放入到一个数组中，方便输出 168 * 第一个参数node_first作为每一层结点数组的起始地址 169 * n为该层结点数 170 */ 171void 172display_node(BTreeNode *node_first, int n) 173{ 174 int i = 0, j = 0, k = 0,all = 0; 175 BTreeNode *node = node_first; 176 177 /* 将该层的结点所有的关键字输出，不同结点以“ ”为分隔，每层以“$$”为分隔 */ 178 for(i = 0; i < n; i++) 179 { 180 for(j = 0; j < (*(node + i))->n; j++) 181 { 182 printf("%d ", (*(node + i))->key[j]); 183 } 184 all = all + (*(node + i))->n + 1; 185 //printf(" %p ", *(node + i)); 186 printf(" "); 187 } 188 printf("$$\n"); 189 190 if(!(*node)->leaf) 191 { 192 BTreeNode nodes[all]; 193 i = 0; 194 for(j = 0; j < n; j++) 195 { 196 for(k = 0; k <= (*(node + j))->n; k++) 197 { 198 nodes[i] = (*(node + j))->child[k]; 199 i++; 200 } 201 } 202 display_node(nodes, all); 203 } 204} 205 206 207/* 208 * 为了验证插入和删除操作的正确性，添加输出函数 209 * 将整棵树输出 210 */ 211void 212display_btree(BTree tree) 213{ 214 BTreeNode r_node = tree->root; 215 216 display_node(&r_node, 1); 217} 218 219/* 220 * 返回以node为根结点树的最小关键字的结点，关键字的位置肯定为0 221 */ 222BTreeNode 223btree_minimum(BTreeNode node) 224{ 225 BTreeNode newnode = node; 226 227 if(newnode->n < 1) 228 { 229 printf("this is null tree\n"); 230 return NULL; 231 } 232 233 if(node->leaf) 234 return newnode; 235 else 236 newnode = btree_minimum(node->child[0]); 237 238 return newnode; 239} 240 241 242/* 243 * 返回以node为根结点树的最大关键字的结点，关键字的位置肯定为该结点的n-1值 244 */ 245BTreeNode 246btree_maximum(BTreeNode node) 247{ 248 BTreeNode newnode = node; 249 250 if(newnode->n < 1) 251 { 252 printf("this is null tree\n"); 253 return NULL; 254 } 255 256 if(node->leaf) 257 return newnode; 258 else 259 newnode = btree_maximum(node->child[node->n]); 260 261 return newnode; 262} 263 264/* 265 * 输出整棵树的最小关键字 266 */ 267void 268btree_min(BTree tree) 269{ 270 BTreeNode r_node = tree->root; 271 BTreeNode n_node = btree_minimum(r_node); 272 273 printf("the min is %d\n", n_node->key[0]); 274} 275 276/* 277 * 输出整棵树的最大关键字 278 */ 279void 280btree_max(BTree tree) 281{ 282 BTreeNode r_node = tree->root; 283 BTreeNode n_node = btree_maximum(r_node); 284 285 printf("the max is %d\n", n_node->key[n_node->n - 1]); 286} 287 288/* 289 * 当下降的结点node的关键字个数为T-1时， 290 * 为了满足下降过程中，遇到的结点的关键字个数大于等于T， 291 * 对结点parent、node、othernode三个结点的关键字做调整。 292 * 当node在other左侧时，即node的右结点时（父结点的右子结点）， * 在T+1位置，增加一个关键字，其值为父结点对应的关键字值， 293 * 将父结点对应关键字值赋值为右子结点中的第一个关键字。 294 * 将右子结点的关键字和子结点（如果有的话）向前移动一位 295 * 修改右子结点以及该结点的n值 296 */ 297void 298btree_left(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location) 299{ 300 int i = 0; 301 node->key[node->n] = parent->key[location]; 302 parent->key[location] = othernode->key[0]; 303 304 for(i = 0; i <= othernode->n - 2; i++) 305 othernode->key[i] = othernode->key[i + 1]; 306 307 if(!othernode->leaf) 308 { 309 node->child[node->n + 1] = othernode->child[0]; 310 for(i = 0; i <= othernode->n - 1; i++) 311 othernode->child[i] = othernode->child[i + 1]; 312 313 } 314 315 node->n = node->n + 1; 316 othernode->n = othernode->n - 1; 317} 318 319/* 320 * 当下降的结点node的关键字个数为T-1时， 321 * 为了满足下降过程中，遇到的结点的关键字个数大于等于T， 322 * 对结点parent、node、othernode三个结点的关键字做调整。 323 * 当node在other右侧时，即node的左结点时（父结点的左子结点）， 324 * node结点的关键字和子结点（如果有的话）向后移动一位, 325 * 在第一个位置增加一个关键字，其值为父结点对应的关键字值， 326 * 将父结点对应关键字值赋值为左子结点中的最后一个关键字。 327 * 修改左子结点和该结点的n值 328 */ 329void 330btree_right(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location) 331{ 332 int i = 0; 333 334 for(i = node->n - 1; i >= 0; i--) 335 othernode->key[i+1] = othernode->key[i]; 336 337 node->key[0] = parent->key[location]; 338 parent->key[location] = othernode->key[othernode->n]; 339 340 if(!node->leaf) 341 { 342 node->child[0] = othernode->child[othernode->n + 1]; 343 for(i = othernode->n; i >= 0; i--) 344 othernode->child[i + 1] = othernode->child[i]; 345 346 } 347 348 node->n = node->n + 1; 349 othernode->n = othernode->n - 1; 350} 351 352/* 353 * 合并两个关键字个数为T-1父结点为parent位置为location的子结点 354 * 以父结点对应的关键字为中间值连接两个子结点 355 * 并返回需要下降的子结点位置 356 */ 357int 358btree_merge_child(BTreeNode parent, int location) 359{ 360 int i; 361 BTreeNode lnode = NULL; 362 BTreeNode rnode = NULL; 363 364 if(location == parent->n) 365 location--; 366 367 lnode = parent->child[location]; 368 rnode = parent->child[location + 1]; 369 370 /* 将父结点对应的关键字以及右兄弟所有的关键字复制该结点，同时修改左子的n值 */ 371 lnode->key[lnode->n] = parent->key[location]; 372 for(i = 0; i < rnode->n; i++) 373 { 374 lnode->key[MIN_T + i] = rnode->key[i]; 375 lnode->n++; 376 } 377 378 /* 如果有子结点同样复制到该结点 */ 379 if(!rnode->leaf) 380 for(i = 0; i <= rnode->n; i++) 381 lnode->child[MIN_T + i] = rnode->child[i]; 382 383 rnode->n= 0; 384 lnode->n = MAX_T - 1; 385 386 /* 对父结点相应的关键字和子结点位置发生变化 */ 387 for(i = location; i < parent->n - 1; i++) 388 { 389 parent->key[i] = parent->key[i + 1]; 390 parent->child[i + 1] = parent->child[i + 2]; 391 } 392 393 /* 调整父结点的n值 */ 394 parent->n = parent->n - 1; 395 rnode = NULL; 396 397 return location; 398} 399 400/* 401 * 对叶子结点node位置为location的关键字删除 402 * 直接将位置location后的关键字向前移动一位 403 */ 404void 405btree_delete_leaf(BTreeNode node, int location) 406{ 407 int i = 0; 408 409 for(i = location; i < node->n - 1; i++) 410 node->key[i] = node->key[i + 1]; 411 412 node->n = node->n - 1; 413} 414 415/* 416 * 删除该层数组坐标为i的关键字 417 */ 418int 419btree_delete_node_in(BTreeNode r_node, int i) 420{ 421 422 BTreeNode lnode = r_node->child[i]; 423 BTreeNode rnode = r_node->child[i + 1]; 424 int temp = 0; 425 426 /* 427 * 当前于该位置的关键字的左子结点关键字个数大于等于T时， 428 * 寻找该位置的关键的前驱（左子结点的最大关键字） 429 */ 430 if(lnode->n >= MIN_T) 431 { 432 BTreeNode newnode = btree_maximum(lnode); 433 temp = r_node->key[i]; 434 r_node->key[i] = newnode->key[newnode->n - 1]; 435 newnode->key[newnode->n - 1] = temp; 436 } 437 /* 438 * 相反的，若右子结点符合条件，则找寻后继（即右子结点的最小关键字） 439 */ 440 else if(rnode->n >= MIN_T) 441 { 442 BTreeNode newnode = btree_minimum(rnode); 443 temp = r_node->key[i]; 444 r_node->key[i] = newnode->key[0]; 445 newnode->key[0] = temp; 446 447 i++; 448 } 449 /* 450 * 当左右子结点都不符合条件，则合并两个子结点 451 */ 452 else i = btree_merge_child(r_node, i); 453 454 return i; 455} 456 457/* 458 * 删除以r_node为根结点的树的关键字key 459 */ 460void 461btree_delete_node(BTreeNode r_node, int key) 462{ 463 int i = 0; 464 465 466 /* 寻找关键字位置，或者下降的子结点位置 */ 467 while(i < r_node->n && key > r_node->key[i]) 468 i++; 469 470 /* 若再该层且为叶子结点删除结点，否则下降寻找结点删除 */ 471 if(i < r_node->n && key == r_node->key[i]) 472 if(r_node->leaf) 473 btree_delete_leaf(r_node, i); 474 else 475 { 476 i = btree_delete_node_in(r_node, i); 477 478 btree_delete_node(r_node->child[i], key); 479 } 480 else 481 { 482 if(r_node->leaf) 483 printf("there is no the key %d!!\n", key); 484 else 485 { 486 if(r_node->child[i]->n >= MIN_T){ 487 btree_delete_node(r_node->child[i], key);} 488 else 489 { 490 if(i > 0 && r_node->child[i - 1]->n >= MIN_T) 491 { 492 btree_right(r_node, r_node->child[i], r_node->child[i - 1], i);} 493 else if(i < r_node->n && r_node->child[i + 1]->n >= MIN_T) 494 btree_left(r_node, r_node->child[i], r_node->child[i + 1], i); 495 else 496 i = btree_merge_child(r_node, i); 497 498 btree_delete_node(r_node->child[i], key); 499 } 500 } 501 } 502} 503 504/* 505 * 删除树内的关键字key，如果根结点为空，则替换根结点 506 */ 507void 508btree_delete(BTree tree, int key) 509{ 510 BTreeNode r_node = tree->root; 511 btree_delete_node(r_node, key); 512 if(tree->root->n == 0 && tree->root->leaf == 0) 513 tree->root = tree->root->child[0]; 514}
这是实现B树的详细C代码。
为了验证结果我以1-100数字作为关键字插入到树中，并且查找5，33的位置，删除100，94，81，36，42，下面看一下结果：
1int main() 2{ 3 BTree tree = (BTree) malloc (BTREE_SIZE); 4 tree->root = (BTreeNode) malloc (BTREE_NODE_SIZE); 5 6 int keys[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,24,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40, 741,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80, 882,81,83,84,85,86,87,88,89,90,91,92,99,94,93,95,96,97,98,100}; 9 int i = 0; 10 11 btree_create(tree); 12 for(i = 0; i <= 99; i++){ 13 btree_insert(tree, keys[i]); 14 //display_btree(&tree); 15 } 16btree_max(tree); 17 display_btree(tree); 18 btree_max(tree); 19 btree_min(tree); 20 btree_search(tree->root,5); 21 22 btree_search(tree->root,33); 23 24 25 btree_delete(tree, 100); 26 display_btree(tree); 27 btree_delete(tree, 94); 28 display_btree(tree); 29 btree_delete(tree, 81); 30 display_btree(tree); 31 btree_delete(tree, 36); 32 display_btree(tree); 33 34btree_delete(tree, 42); 35 36 display_btree(tree); 37 btree_max(tree); 38 btree_min(tree); 39 40 free(tree); 41 return 0; 42} 43 44 45 46 47 48[root@localhost ~]# gcc -o btree btree.c -Wall 49[root@localhost ~]# ./btree 50the max is 100
输出完全插入后的树：
127 54 $$ 29 18 36 45 63 72 81 90 $$ 33 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 84 87 93 96 $$ 41 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 94 95 97 98 99 100 $$
输出关键字的做大最小值：
1the max is 100 2the min is 1
输出5，33的位置
1the 5 key's location is 1 in the node 0x9ff50c0 2the 33 key's location is 1 in the node 0x9ff53d0
删除100后的树：
127 54 $$ 29 18 36 45 63 72 81 $$ 33 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 84 87 90 93 96 $$ 41 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 94 95 97 98 99 $$
删除94后的树：
127 54 $$ 29 18 36 45 63 72 81 $$ 33 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 84 87 90 93 97 $$ 41 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 95 96 98 99 $$
删除81后的树：
127 54 $$ 29 18 36 45 63 72 82 $$ 33 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 87 90 93 97 $$ 41 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 83 84 85 86 88 89 91 92 95 96 98 99 $$
删除36后的树：
127 63 $$ 29 18 45 54 72 82 $$ 33 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 87 90 93 97 $$ 41 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 83 84 85 86 88 89 91 92 95 96 98 99 $$
删除42后的树：
127 $$ 29 18 45 54 63 72 82 $$ 33 6 12 15 21 24 30 33 39 48 51 57 60 66 69 75 78 87 90 93 97 $$ 41 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 83 84 85 86 88 89 91 92 95 96 98 99 $$
最后再输出一次最大最小值：
1the max is 99 2the min is 1