算法14---B树

  1 #include <stdlib.h>  2 #include <stdio.h>  3 #include <assert.h>  4   5 //参考地址：http://www.xuebuyuan.com/509072.html  6   7   8   9 //实现对order序(阶)的B-TREE结构基本操作的封装。 10 //查找：search，插入：insert，删除：remove。 11 //创建：create，销毁：destory，打印：print。 12  13  14  15 ////* 定义m序(阶)B 树的最小度数BTree_D=ceil(m)*/ 16 /// 在这里定义每个节点中关键字的最大数目为:2 * BTree_D - 1，即序(阶)：2 * BTree_D. 17 #define BTree_D        2 18 #define ORDER        (BTree_D * 2) //定义为4阶B-tree,2-3-4树。最简单为3阶B-tree,2-3树。 19 //#define ORDER        (BTree_T * 2-1)    //最简单为3阶B-tree,2-3树。 20  21     typedef int KeyType; 22     typedef struct BTNode{ 23         int keynum;                        /// 结点中关键字的个数，keynum <= BTree_N 24         KeyType key[ORDER-1];                /// 关键字向量为key[0..keynum - 1] 25         struct BTNode* child[ORDER];        /// 孩子指针向量为child[0..keynum] 26         bool isLeaf;                    /// 是否是叶子节点的标志 27     }BTNode; 28  29     typedef BTNode* BTree;    ///定义BTree 30  31     ///给定数据集data,创建BTree。 32     void BTree_create(BTree* tree, const KeyType* data, int length); 33  34     ///销毁BTree，释放内存空间。 35     void BTree_destroy(BTree* tree); 36  37     ///在BTree中插入关键字key。 38     void BTree_insert(BTree* tree, KeyType key); 39  40     ///在BTree中移除关键字key。 41     void BTree_remove(BTree* tree, KeyType key); 42  43     ///深度遍历BTree打印各层结点信息。 44     void BTree_print(const BTree tree, int layer=1); 45  46     /// 在BTree中查找关键字 key， 47     /// 成功时返回找到的节点的地址及 key 在其中的位置 *pos 48     /// 失败时返回 NULL 及查找失败时扫描到的节点位置 *pos 49     BTNode* BTree_search(const BTree tree, int key, int* pos); 50  51  52  53 #define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比较a，b大小 54 #define DEBUG_BTREE 55  56  57  58 // 模拟向磁盘写入节点 59 void disk_write(BTNode* node) 60 { 61 //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。 62     printf("向磁盘写入节点"); 63     for(int i=0;i<ORDER-1;i++){ 64         printf("%c",node->key[i]); 65     } 66     printf("\n"); 67 } 68  69  70 // 模拟从磁盘读取节点 71 void disk_read(BTNode** node) 72 { 73 //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。 74     printf("向磁盘读取节点"); 75     for(int i=0;i<ORDER-1;i++){ 76         printf("%c",(*node)->key[i]); 77     } 78     printf("\n"); 79 } 80  81  82 // 按层次打印 B 树 83 void BTree_print(const BTree tree, int layer) 84 { 85     int i; 86     BTNode* node = tree; 87  88     if (node) { 89         printf("第 %d 层， %d node : ", layer, node->keynum); 90  91         //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。 92         for (i = 0; i < ORDER-1; ++i) { 93         //for (i = 0; i < node->keynum; ++i) { 94             printf("%c ", node->key[i]); 95         } 96  97         printf("\n"); 98  99         ++layer;100         for (i = 0 ; i <= node->keynum; i++) {101             if (node->child[i]) {102                 BTree_print(node->child[i], layer);103             }104         }105     }106     else {107         printf("树为空。\n");108     }109 }110 111 112 // 结点node内对关键字进行二分查找。113 int binarySearch(BTNode* node, int low, int high, KeyType Fkey)114 {115     int mid;116     while (low<=high)117     {118         mid = low + (high-low)/2;119         if (Fkey<node->key[mid])120         {121             high = mid-1;122         }123         if (Fkey>node->key[mid])124         {125             low = mid+1;126         }127         if (Fkey==node->key[mid])128         {129             return mid;//返回下标。130         }131     }132     return 0;//未找到返回0.133 }134 135 //insert136 /***************************************************************************************137    将分裂的结点中的一半元素给新建的结点，并且将分裂结点中的中间关键字元素上移至父节点中。138    parent 是一个非满的父节点139    node 是 tree 孩子表中下标为 index 的孩子节点，且是满的，需分裂。140 *******************************************************************/141 void BTree_split_child(BTNode* parent, int index, BTNode* node)142 {143 #ifdef DEBUG_BTREE144     printf("BTree_split_child!\n");145 #endif146     assert(parent && node);147     int i;148 149     // 创建新节点，存储 node 中后半部分的数据150     BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1);151     if (!newNode) {152         printf("Error! out of memory!\n");153         return;154     }155 156     newNode->isLeaf = node->isLeaf;157     newNode->keynum = BTree_D - 1;158 159     // 拷贝 node 后半部分关键字,然后将node后半部分置为0。160     for (i = 0; i < newNode->keynum; ++i){161         newNode->key[i] = node->key[BTree_D + i];162         node->key[BTree_D + i] = 0;163     }164 165     // 如果 node 不是叶子节点，拷贝 node 后半部分的指向孩子节点的指针，然后将node后半部分指向孩子节点的指针置为NULL。166     if (!node->isLeaf) {167         for (i = 0; i < BTree_D; i++) {168             newNode->child[i] = node->child[BTree_D + i];169             node->child[BTree_D + i] = NULL;170         }171     }172 173     // 将 node 分裂出 newNode 之后，里面的数据减半174     node->keynum = BTree_D - 1;175 176     // 调整父节点中的指向孩子的指针和关键字元素。分裂时父节点增加指向孩子的指针和关键元素。177     for (i = parent->keynum; i > index; --i) {178         parent->child[i + 1] = parent->child[i];179     }180 181     parent->child[index + 1] = newNode;182 183     for (i = parent->keynum - 1; i >= index; --i) {184         parent->key[i + 1] = parent->key[i];185     }186 187     parent->key[index] = node->key[BTree_D - 1];188     ++parent->keynum;189 190     node->key[BTree_D - 1] = 0;191 192     // 写入磁盘193      disk_write(parent);194      disk_write(newNode);195      disk_write(node);196 }197 198 void BTree_insert_nonfull(BTNode* node, KeyType key)199 {200     assert(node);201 202     int i;203 204     // 节点是叶子节点，直接插入205     if (node->isLeaf) {206         i = node->keynum - 1;207         while (i >= 0 && key < node->key[i]) {208             node->key[i + 1] = node->key[i];209             --i;210         }211 212         node->key[i + 1] = key;213         ++node->keynum;214 215         // 写入磁盘216         disk_write(node);217     }218 219     // 节点是内部节点220     else {221         /* 查找插入的位置*/222         i = node->keynum - 1;223         while (i >= 0 && key < node->key[i]) {224             --i;225         }226 227         ++i;228 229         // 从磁盘读取孩子节点230         disk_read(&node->child[i]);231 232         // 如果该孩子节点已满，分裂调整值233         if (node->child[i]->keynum == (ORDER-1)) {234             BTree_split_child(node, i, node->child[i]);235             // 如果待插入的关键字大于该分裂结点中上移到父节点的关键字，在该关键字的右孩子结点中进行插入操作。236             if (key > node->key[i]) {237                 ++i;238             }239         }240         BTree_insert_nonfull(node->child[i], key);241     }242 }243 244 void BTree_insert(BTree* tree, KeyType key)245 {246 #ifdef DEBUG_BTREE247     printf("BTree_insert:\n");248 #endif249     BTNode* node;250     BTNode* root = *tree;251 252     // 树为空253     if (NULL == root) {254         root = (BTNode*)calloc(sizeof(BTNode), 1);255         if (!root) {256             printf("Error! out of memory!\n");257             return;258         }259         root->isLeaf = true;260         root->keynum = 1;261         root->key[0] = key;262 263         *tree = root;264 265         // 写入磁盘266         disk_write(root);267 268         return;269     }270 271     // 根节点已满，插入前需要进行分裂调整272     if (root->keynum == (ORDER-1)) {273         // 产生新节点当作根274         node = (BTNode*)calloc(sizeof(BTNode), 1);275         if (!node) {276             printf("Error! out of memory!\n");277             return;278         }279 280         *tree = node;281         node->isLeaf = false;282         node->keynum = 0;283         node->child[0] = root;284 285         BTree_split_child(node, 0, root);286 287         BTree_insert_nonfull(node, key);288     }289 290     // 根节点未满，在当前节点中插入 key291     else {292         BTree_insert_nonfull(root, key);293     }294 }295 296 297 298 299 300 //remove301 // 对 tree 中的节点 node 进行合并孩子节点处理.302 // 注意：孩子节点的 keynum 必须均已达到下限，即均等于 BTree_D - 1303 // 将 tree 中索引为 index 的 key 下移至左孩子结点中，304 // 将 node 中索引为 index + 1 的孩子节点合并到索引为 index 的孩子节点中，右孩子合并到左孩子结点中。305 // 并调相关的 key 和指针。306 307 void BTree_merge_child(BTree* tree, BTNode* node, int index)308 {309 #ifdef DEBUG_BTREE310     printf("BTree_merge_child!\n");311 #endif312     assert(tree && node && index >= 0 && index < node->keynum);313 314     int i;315 316     KeyType key = node->key[index];317     BTNode* leftChild = node->child[index];318     BTNode* rightChild = node->child[index + 1];319 320     assert(leftChild && leftChild->keynum == BTree_D - 1321         && rightChild && rightChild->keynum == BTree_D - 1);322 323     // 将 node中关键字下标为index 的 key 下移至左孩子结点中，该key所对应的右孩子结点指向node的右孩子结点中的第一个孩子。324     leftChild->key[leftChild->keynum] = key;325     leftChild->child[leftChild->keynum + 1] = rightChild->child[0];326     ++leftChild->keynum;327 328     // 右孩子的元素合并到左孩子结点中。329     for (i = 0; i < rightChild->keynum; ++i) {330         leftChild->key[leftChild->keynum] = rightChild->key[i];331         leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1];332         ++leftChild->keynum;333     }334 335     // 在 node 中下移的 key后面的元素前移336     for (i = index; i < node->keynum - 1; ++i) {337         node->key[i] = node->key[i + 1];338         node->child[i + 1] = node->child[i + 2];339     }340     node->key[node->keynum - 1] = 0;341     node->child[node->keynum] = NULL;342     --node->keynum;343 344     // 如果根节点没有 key 了，并将根节点调整为合并后的左孩子节点；然后删除释放空间。345     if (node->keynum == 0) {346         if (*tree == node) {347             *tree = leftChild;348         }349 350         free(node);351         node = NULL;352     }353 354     free(rightChild);355     rightChild = NULL;356 }357 358 void BTree_recursive_remove(BTree* tree, KeyType key)359 {360     // B-数的保持条件之一：361     // 非根节点的内部节点的关键字数目不能少于 BTree_D - 1362 363     int i, j, index;364     BTNode *root = *tree;365     BTNode *node = root;366 367     if (!root) {368         printf("Failed to remove %c, it is not in the tree!\n", key);369         return;370     }371 372     // 结点中找key。373     index = 0;374     while (index < node->keynum && key > node->key[index]) {375         ++index;376     }377 378 /*======================含有key的当前结点时的情况====================379 node:380 index of Key:             i-1  i  i+1381                         +---+---+---+---+382                           *  key   *383                     +---+---+---+---+---+384                            /     385 index of Child:              i         i+1386                          /           387                     +---+---+       +---+---+388                       *   *              *   *   389                 +---+---+---+  +---+---+---+390                     leftChild      rightChild391 ============================================================*/392     /*一、结点中找到了关键字key的情况.*/393     BTNode *leftChild, *rightChild;394     KeyType leftKey, rightKey;395     if (index < node->keynum && node->key[index] == key) {396         /* 1，所在节点是叶子节点，直接删除*/397         if (node->isLeaf) {398             for (i = index; i < node->keynum-1; ++i) {399                 node->key[i] = node->key[i + 1];400                 //node->child[i + 1] = node->child[i + 2];叶子节点的孩子结点为空，无需移动处理。401             }402             node->key[node->keynum-1] = 0;403             //node->child[node->keynum] = NULL;404             --node->keynum;405 406             if (node->keynum == 0) {407                 assert(node == *tree);408                 free(node);409                 *tree = NULL;410             }411 412             return;413         }414         /*2.选择脱贫致富的孩子结点。*/415         // 2a，选择相对富有的左孩子结点。416         // 如果位于 key 前的左孩子结点的 key 数目 >= BTree_D，417         // 在其中找 key 的左孩子结点的最后一个元素上移至父节点key的位置。418         // 然后在左孩子节点中递归删除元素leftKey。419         else if (node->child[index]->keynum >= BTree_D) {420             leftChild = node->child[index];421             leftKey = leftChild->key[leftChild->keynum - 1];422             node->key[index] = leftKey;423 424             BTree_recursive_remove(&leftChild, leftKey);425         }426         // 2b，选择相对富有的右孩子结点。427         // 如果位于 key 后的右孩子结点的 key 数目 >= BTree_D，428         // 在其中找 key 的右孩子结点的第一个元素上移至父节点key的位置429         // 然后在右孩子节点中递归删除元素rightKey。430         else if (node->child[index + 1]->keynum >= BTree_D) {431             rightChild = node->child[index + 1];432             rightKey = rightChild->key[0];433             node->key[index] = rightKey;434 435             BTree_recursive_remove(&rightChild, rightKey);436         }437         /*左右孩子结点都刚脱贫。删除前需要孩子结点的合并操作*/438         // 2c，左右孩子结点只包含 BTree_D - 1 个节点，439         // 合并是将 key 下移至左孩子节点，并将右孩子节点合并到左孩子节点中，440         // 删除右孩子节点，在父节点node中移除 key 和指向右孩子节点的指针，441         // 然后在合并了的左孩子节点中递归删除元素key。442         else if (node->child[index]->keynum == BTree_D - 1443             && node->child[index + 1]->keynum == BTree_D - 1){444             leftChild = node->child[index];445 446             BTree_merge_child(tree, node, index);447 448             // 在合并了的左孩子节点中递归删除 key449             BTree_recursive_remove(&leftChild, key);450         }451     }452 453 /*======================未含有key的当前结点时的情况====================454 node:455 index of Key:             i-1  i  i+1456                         +---+---+---+---+457                           *  keyi *458                     +---+---+---+---+---+459                        /    |    460 index of Child:         i-1    i     i+1461                      /        |       462             +---+---+    +---+---+       +---+---+463              *   *          *   *             *   *   464         +---+---+---+   +---+---+---+  +---+---+---+465         leftSibling          Child           rightSibling   466 ============================================================*/467     /*二、结点中未找到了关键字key的情况.*/468     else {469         BTNode *leftSibling, *rightSibling, *child;470         // 3. key 不在内节点 node 中，则应当在某个包含 key 的子节点中。471         //  key < node->key[index], 所以 key 应当在孩子节点 node->child[index] 中472         child = node->child[index];473         if (!child) {474             printf("Failed to remove %c, it is not in the tree!\n", key);475             return;476         }477         /*所需查找的该孩子结点刚脱贫的情况*/478         if (child->keynum == BTree_D - 1) {479             leftSibling = NULL;480             rightSibling = NULL;481 482             if (index - 1 >= 0) {483                 leftSibling = node->child[index - 1];484             }485 486             if (index + 1 <= node->keynum) {487                 rightSibling = node->child[index + 1];488             }489             /*选择致富的相邻兄弟结点。*/490             // 3a，如果所在孩子节点相邻的兄弟节点中有节点至少包含 BTree_D 个关键字491             // 将 node 的一个关键字key[index]下移到 child 中，将相对富有的相邻兄弟节点中一个关键字上移到492             // node 中，然后在 child 孩子节点中递归删除 key。493             if ((leftSibling && leftSibling->keynum >= BTree_D)494                 || (rightSibling && rightSibling->keynum >= BTree_D)) {495                 int richR = 0;496                 if(rightSibling) richR = 1;497                 if(leftSibling && rightSibling) {498                     richR = cmp(rightSibling->keynum,leftSibling->keynum);499                 }500                 if (rightSibling && rightSibling->keynum >= BTree_D && richR) {501         //相邻右兄弟相对富有，则该孩子先向父节点借一个元素，右兄弟中的第一个元素上移至父节点所借位置，并进行相应调整。502                     child->key[child->keynum] = node->key[index];503                     child->child[child->keynum + 1] = rightSibling->child[0];504                     ++child->keynum;505 506                     node->key[index] = rightSibling->key[0];507 508                     for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移509                         rightSibling->key[j] = rightSibling->key[j + 1];510                         rightSibling->child[j] = rightSibling->child[j + 1];511                     }512                     rightSibling->key[rightSibling->keynum-1] = 0;513                     rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum];514                     rightSibling->child[rightSibling->keynum] = NULL;515                     --rightSibling->keynum;516                 }517                 else {//相邻左兄弟相对富有，则该孩子向父节点借一个元素，左兄弟中的最后元素上移至父节点所借位置，并进行相应调整。518                     for (j = child->keynum; j > 0; --j) {//元素后移519                         child->key[j] = child->key[j - 1];520                         child->child[j + 1] = child->child[j];521                     }522                     child->child[1] = child->child[0];523                     child->child[0] = leftSibling->child[leftSibling->keynum];524                     child->key[0] = node->key[index - 1];525                     ++child->keynum;526 527                     node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1];528 529                     leftSibling->key[leftSibling->keynum - 1] = 0;530                     leftSibling->child[leftSibling->keynum] = NULL;531 532                     --leftSibling->keynum;533                 }534             }535             /*相邻兄弟结点都刚脱贫。删除前需要兄弟结点的合并操作,*/536             // 3b, 如果所在孩子节点相邻的兄弟节点都只包含 BTree_D - 1 个关键字，537             // 将 child 与其一相邻节点合并，并将 node 中的一个关键字下降到合并节点中，538             // 再在 node 中删除那个关键字和相关指针，若 node 的 key 为空，删之，并调整根为合并结点。539             // 最后，在相关孩子节点child中递归删除 key。540             else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1))541                 && (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) {542                 if (leftSibling && leftSibling->keynum == BTree_D - 1) {543 544                     BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合并到左孩子中。545 546                     child = leftSibling;547                 }548 549                 else if (rightSibling && rightSibling->keynum == BTree_D - 1) {550 551                     BTree_merge_child(tree, node, index);//node中的右孩子元素合并到左孩子中。552                 }553             }554         }555 556         BTree_recursive_remove(&child, key);//调整后，在key所在孩子结点中继续递归删除key。557     }558 }559 560 void BTree_remove(BTree* tree, KeyType key)561 {562 #ifdef DEBUG_BTREE563     printf("BTree_remove:\n");564 #endif565     if (*tree==NULL)566     {   567         printf("BTree is NULL!\n");568         return;569     }570 571     BTree_recursive_remove(tree, key);572 }573 574 575 576 //=====================================search====================================577 578 BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)579 {580     int i = 0;581 582     while (i < tree->keynum && key > tree->key[i]) {583         ++i;584     }585 586     // Find the key.587     if (i < tree->keynum && tree->key[i] == key) {588         *pos = i;589         return tree;590     }591 592     // tree 为叶子节点，找不到 key，查找失败返回593     if (tree->isLeaf) {594         return NULL;595     }596 597     // 节点内查找失败，但 tree->key[i - 1]< key < tree->key[i]，598     // 下一个查找的结点应为 child[i]599 600     // 从磁盘读取第 i 个孩子的数据601     disk_read(&tree->child[i]);602 603     // 递归地继续查找于树 tree->child[i]604     return BTree_recursive_search(tree->child[i], key, pos);605 }606 607 BTNode* BTree_search(const BTree tree, KeyType key, int* pos)608 {609 #ifdef DEBUG_BTREE610     printf("BTree_search:\n");611 #endif612     if (!tree) {613         printf("BTree is NULL!\n");614         return NULL;615     }616     *pos = -1;617     return BTree_recursive_search(tree,key,pos);618 }619 620 //===============================create===============================621 void BTree_create(BTree* tree, const KeyType* data, int length)622 {623     assert(tree);624 625     int i;626 627 #ifdef DEBUG_BTREE628     printf("\n 开始创建 B-树，关键字为:\n");629     for (i = 0; i < length; i++) {630         printf(" %c ", data[i]);631     }632     printf("\n");633 #endif634 635     for (i = 0; i < length; i++) {636 #ifdef DEBUG_BTREE637         printf("\n插入关键字 %c:\n", data[i]);638 #endif639         int pos = -1;640         BTree_search(*tree,data[i],&pos);//树的递归搜索。641         if (pos!=-1)642         {643             printf("this key %c is in the B-tree,not to insert.\n",data[i]);644         }else{645             BTree_insert(tree, data[i]);//插入元素到BTree中。646         }647 648 #ifdef DEBUG_BTREE649         BTree_print(*tree);//树的深度遍历。650 #endif651     }652 653     printf("\n");654 }655 656 657 658 659 660 //===============================destroy===============================661 void BTree_destroy(BTree* tree)662 {663     int i;664     BTNode* node = *tree;665 666     if (node) {667         for (i = 0; i <= node->keynum; i++) {668             BTree_destroy(&node->child[i]);669         }670 671         free(node);672     }673 674     *tree = NULL;675 }676 677 678 679 680 681 //================以下是测试的部分===================682 683 void test_BTree_search(BTree tree, KeyType key)684 {685     int pos = -1;686     BTNode*    node = BTree_search(tree, key, &pos);687     if (node) {688         printf("在%s节点（包含 %d 个关键字）中找到关键字 %c，其索引为 %d\n",689             node->isLeaf ? "叶子" : "非叶子",690             node->keynum, key, pos);691     }692     else {693         printf("在树中找不到关键字 %c\n", key);694     }695 }696 697 void test_BTree_remove(BTree* tree, KeyType key)698 {699     printf("\n移除关键字 %c \n", key);700     BTree_remove(tree, key);701     BTree_print(*tree);702     printf("\n");703 }704 705 void test_btree()706 {707 708     KeyType array[] = {709         ‘G‘,‘G‘, ‘M‘, ‘P‘, ‘X‘, ‘A‘, ‘C‘, ‘D‘, ‘E‘, ‘J‘, ‘K‘,710         ‘N‘, ‘O‘, ‘R‘, ‘S‘, ‘T‘, ‘U‘, ‘V‘, ‘Y‘, ‘Z‘, ‘F‘, ‘X‘711     };712     const int length = sizeof(array)/sizeof(KeyType);713     BTree tree = NULL;714     BTNode* node = NULL;715     int pos = -1;716     KeyType key1 = ‘R‘;        // in the tree.717     KeyType key2 = ‘B‘;        // not in the tree.718 719     // 创建720     BTree_create(&tree, array, length);721 722     printf("\n=== 创建 B- 树 ===\n");723     BTree_print(tree);724     printf("\n");725 726     // 查找727     test_BTree_search(tree, key1);728     printf("\n");729     test_BTree_search(tree, key2);730 731     // 移除不在B树中的元素732     test_BTree_remove(&tree, key2);733     printf("\n");734 735     // 插入关键字736     printf("\n插入关键字 %c \n", key2);737     BTree_insert(&tree, key2);738     BTree_print(tree);739     printf("\n");740 741     test_BTree_search(tree, key2);742 743     // 移除关键字744     test_BTree_remove(&tree, key2);745     test_BTree_search(tree, key2);746 747     key2 = ‘M‘;748     test_BTree_remove(&tree, key2);749     test_BTree_search(tree, key2);750 751     key2 = ‘E‘;752     test_BTree_remove(&tree, key2);753     test_BTree_search(tree, key2);754 755     key2 = ‘G‘;756     test_BTree_remove(&tree, key2);757     test_BTree_search(tree, key2);758 759     key2 = ‘A‘;760     test_BTree_remove(&tree, key2);761     test_BTree_search(tree, key2);762 763     key2 = ‘D‘;764     test_BTree_remove(&tree, key2);765     test_BTree_search(tree, key2);766 767     key2 = ‘K‘;768     test_BTree_remove(&tree, key2);769     test_BTree_search(tree, key2);770 771     key2 = ‘P‘;772     test_BTree_remove(&tree, key2);773     test_BTree_search(tree, key2);774 775     key2 = ‘J‘;776     test_BTree_remove(&tree, key2);777     test_BTree_search(tree, key2);778 779     key2 = ‘C‘;780     test_BTree_remove(&tree, key2);781     test_BTree_search(tree, key2);782 783     key2 = ‘X‘;784     test_BTree_remove(&tree, key2);785     test_BTree_search(tree, key2);786 787     key2 = ‘O‘;788     test_BTree_remove(&tree, key2);789     test_BTree_search(tree, key2);790 791     key2 = ‘V‘;792     test_BTree_remove(&tree, key2);793     test_BTree_search(tree, key2);794 795     key2 = ‘R‘;796     test_BTree_remove(&tree, key2);797     test_BTree_search(tree, key2);798 799     key2 = ‘U‘;800     test_BTree_remove(&tree, key2);801     test_BTree_search(tree, key2);802 803     key2 = ‘T‘;804     test_BTree_remove(&tree, key2);805     test_BTree_search(tree, key2);806 807     key2 = ‘N‘;808     test_BTree_remove(&tree, key2);809     test_BTree_search(tree, key2);810     key2 = ‘S‘;811     test_BTree_remove(&tree, key2);812     test_BTree_search(tree, key2);813     key2 = ‘Y‘;814     test_BTree_remove(&tree, key2);815     test_BTree_search(tree, key2);816     key2 = ‘F‘;817     test_BTree_remove(&tree, key2);818     test_BTree_search(tree, key2);819     key2 = ‘Z‘;820     test_BTree_remove(&tree, key2);821     test_BTree_search(tree, key2);822 823     // 销毁824     BTree_destroy(&tree);825 }826 827 int main()828 {829     test_btree();830 831     return 0;832 }