不得不说，这个我写了两天。第一天晚上想移植一篇博客的，后来经过四个小时发现是错了谁懂啊！今天早上又找了一篇，大错误我都改了，有一个潜在的小bug是自己调试跳出来的，谁懂啊！得找阅读量高的才行！
先把刚刚的小错误放一下
也不知道博主怎么想的，同时i和keynum++，害，害我好找！！！
改后就好了
由于老师要求的数据规模太大，我小小的vs承受不起，我只能想法设法减少我开辟的空间，连数组都不要了（哭）
结构（这是我采取的数据结构）
1 //关键字索引 0（不记录） 1 2 3 4（不记录具体数值） 2 //孩子的索引 0 1 2 3 4 3 4 //树结点信息 5 typedef struct Treenode 6 { 7 int level;//树的阶数 8 int keyNum;//关键字的个数 9 int childNum;//孩子的个数 10 int* keys;//关键字数组 11 struct Treenode** children;//孩子数组 12 struct Treenode* parent;//父亲指针 13 };
对应的初始化代码
1 //初始化结点 2 Treenode* initNode(int level) 3 { 4 Treenode* node = (Treenode*)malloc(sizeof(Treenode)); 5 node->level = level; 6 node->keyNum = 0; 7 node->childNum = 0; 8 node->keys = (int*)malloc(sizeof(int) * (level+1));//索引，从1开始记录 9 node->children = (Treenode**)malloc(sizeof(Treenode*) * level); 10 node->parent = NULL; 11 for (int i = 0; i < level; i++) 12 { 13 node->keys[i] = 0; 14 node->children[i] = NULL; 15 } 16 node->keys[level] = 0;//并没有实际用途，只是为了方便返回孩子的索引 17 return node; 18 }
插入
其实我感觉插入很简单，总结下来就是，找到要插入的叶子！！！结点（也就是最下面），然后如果超出m-1那就取中间进行分裂就好！
调整的步骤在代码注释中也有
//判断该结点是否进行分裂。调整主要三个方面
//1.找出中间结点，把结点前面的键值给新的左孩子，后面的键值给新的右孩子
//2.将该节点的孩子分给新的左孩子和右孩子
//3.将中间结点插入该节点的父亲关键字数组中，并将新的左孩子和右孩子插入父亲节点的孩子数组
由最底层逐层向上调整（这可能也是为什么左右子树高度相等的原因吧）
1 //在节点处寻找合适的插入索引 2 int findSuiteIndex(Treenode* node, int data) 3 { 4 int index; 5 //索引从1开始，因为0是没有用的边界 6 for (index = 1; index <= node->keyNum; index++) 7 if (data < node->keys[index]) 8 break; 9 return index; 10 }
1 //找到合适的叶子结点，先插入叶子（没有孩子的结点）结点再做调整 2 Treenode* findSuiteLeafNode(Treenode* T, int data) 3 { 4 if (T->childNum == 0) 5 return T; 6 else 7 { 8 int index = findSuiteIndex(T, data); 9 //找到对应的（索引+1），再去该子节点去搜索,见前面注释 10 return findSuiteLeafNode(T->children[index-1], data); 11 } 12 }
1 //插入结点函数 2 void insert(Treenode** T, int data) 3 { 4 Treenode* node = findSuiteLeafNode(*T,data); 5 //找到要插入的叶子结点 6 addData(node, data, T);//插入树 7 }
这些基本函数封装好了，剩下就是add的实现了
1 //插入数据到B树 2 void addData(Treenode* node, int data,Treenode**T) 3 { 4 //先找到索引，将data放入关键字数组 5 int index = findSuiteIndex(node, data); 6 //后面元素后移动，因为本来就预留了多余的空间 7 for (int i = node->keyNum; i >= index; i--) 8 node->keys[i + 1] = node->keys[i]; 9 node->keys[index] = data; 10 node->keyNum++; 11 12 //判断该结点是否进行分裂。调整主要三个方面 13 //1.找出中间结点，把结点前面的给新的左孩子，后面的给新的右孩子 14 //2.将该节点的孩子分给新的左孩子和右孩子 15 //3.将中间结点插入该节点的父亲关键字数组中，并将新的左孩子和右孩子插入父亲节点的孩子数组 16 if (node->keyNum == node->level) 17 { 18 //取中间节点 19 int mid = node->level / 2 + node->level % 2; 20 21 //生成新的左右孩子 22 Treenode* lchild = initNode(node->level); 23 Treenode* rchild = initNode(node->level); 24 25 //将mid左边的赋给左孩子关键字数组 26 for (int i = 1; i < mid; i++) 27 addData(lchild, node->keys[i], T); 28 29 //将mid右边的赋给右孩子关键字数组 30 for (int i = mid + 1; i <= node->keyNum; i++) 31 addData(rchild, node->keys[i], T); 32 33 //把该结点下面对应的孩子赋给左孩子的孩子数组 34 for (int i = 0; i < mid; i++) 35 { 36 lchild->children[i] = node->children[i]; 37 //如果该孩子结点不为空，需要改变孩子的某些信息 38 if (node->children[i] != NULL) 39 { 40 node->children[i]->parent = lchild; 41 lchild->childNum++; 42 } 43 } 44 45 //把该结点下面对应的孩子赋给右孩子的孩子数组 46 int k = 0;//右孩子数组的索引值 47 for (int i = mid; i < node->childNum; i++) 48 { 49 rchild->children[k++] = node->children[i]; 50 //如果该孩子结点不为空，需要改变孩子的某些信息 51 if (node->children[i] != NULL) 52 { 53 node->children[i]->parent = rchild; 54 rchild->childNum++; 55 } 56 } 57 58 //将中间结点插入该节点的父亲关键字数组中，并将新的左孩子和右孩子插入父亲节点的孩子数组 59 //node是根节点的时候，分裂会改变根节点 60 if (node->parent == NULL) 61 { 62 //生成新的根结点 63 Treenode* newParent = initNode(node->level); 64 addData(newParent, node->keys[mid], T); 65 newParent->children[0] = lchild; 66 newParent->children[1] = rchild; 67 newParent->childNum = 2; 68 lchild->parent = newParent; 69 rchild->parent = newParent; 70 *T = newParent; 71 } 72 else 73 { 74 //找到mid结点应该插入的node父亲的关键字数组的索引 75 int indexparent = findSuiteIndex(node->parent, node->keys[mid]); 76 77 lchild->parent = node->parent; 78 rchild->parent = node->parent; 79 //node原来所有的元素都比index要小，所以之间把左孩子插入index-1，右孩子应该在index的位置 80 node->parent->children[indexparent - 1] = lchild; 81 //插入新的右孩子前，如果index处有，需要整体后移 82 if (node->parent->children[indexparent] != NULL) 83 { 84 for (int i = node->parent->childNum - 1; i >= indexparent; i--) 85 node->parent->children[i + 1] = node->parent->children[i]; 86 } 87 node->parent->children[indexparent] = rchild; 88 node->parent->childNum++; 89 //将mid插入父节点位置 90 addData(node->parent, node->keys[mid],T); 91 } 92 } 93 }
删除
删除其实分两种：1.非叶子结点：就选择它左孩子最大值或右孩子最小值进行替代，然后归结为删除叶子结点
2.叶子结点就比较复杂了：（1）左兄弟富有或者右兄弟富有（键值个数大于【m/2】-1），就旋转一下（比如：左兄弟富有，将parent该键值给该结点1号键值处，然后将左兄弟最大键值给parent就好了！！！别看它看起来是这样，实现不容易啊！特别别忘了左兄弟的最大的孩子也要给该结点成为他的第一个孩子！！！之前博主就是少了这个）
（2）都很穷的时候,将parent处键值，左（右）兄弟（键值和孩子），自己合并成一个结点，在插入回parent结点处，别忘了对parent相关值进行改动哦！
和插入一样，需要从底层往跟进行调整，我采用栈比较好理解啦
我的实现是，将跟到待删除的叶子！！！结点入栈，然后一个一个取出来（叶子----跟）进行判断是否需要调整就好了
1 // 合并操作 2 void merge(Treenode* P, int pos) 3 { 4 // pos+1(P) 5 // pos(LC) pos+1(RC) 6 Treenode* LC = P->children[pos]; 7 Treenode* RC = P->children[pos + 1]; 8 9 LC->keys[LC->keyNum + 1] = P->keys[pos + 1]; 10 ++LC->keyNum; 11 12 //将右兄弟移入LC 13 int m = LC->keyNum; 14 for (int i = 1; i <= RC->keyNum; ++i) 15 { 16 LC->keys[m + i] = RC->keys[i]; 17 ++LC->keyNum; 18 } 19 int n = LC->childNum; 20 for (int i = 0; i < RC->childNum; ++i) 21 { 22 LC->children[ n+ i] = RC->children[i]; 23 ++LC->childNum; 24 } 25 26 for (int i = pos + 1; i < P->keyNum; ++i) 27 { 28 P->keys[i] = P->keys[i + 1]; 29 } 30 for (int i = pos + 1; i < P->childNum-1; ++i) 31 { 32 P->children[i] = P->children[i + 1]; 33 } 34 --P->keyNum; 35 --P->childNum; 36 }
1 //删除键值 2 bool deleteKey(int key, Treenode** Root) 3 { 4 //如果根节点为空或者没有键值时 5 if (NULL == *Root || 0 == (*Root)->keyNum) return false; 6 7 Treenode* T = *Root;//复制一份 8 9 stack<Treenode*> NODE;//存储调整的那棵子树 10 11 while (T) 12 { 13 NODE.push(T); 14 //找到第一个比他大的索引 15 int i = findSuiteIndex(T, key); 16 // i-1(可能相等的点） i(key比它小） 17 //孩子 i-2 i-1 i 18 19 if (i-1 <= T->keyNum && T->keys[i-1] == key) 20 {// 删除键值在该节点中 21 if (T->childNum==0) 22 {// 叶子节点，删除 23 for (int k=i-1; i <= T->keyNum - 1; ++i) 24 T->keys[k] = T->keys[k + 1]; 25 --T->keyNum; 26 break; 27 } 28 else 29 {// 非叶子节点，找后继/也可以找前驱（必存在） 30 Treenode* RC = T->children[i - 1];// 右孩子 31 //找右孩子最小值 32 while (RC->childNum!=0) RC = RC->children[0]; 33 34 T->keys[i-1] = RC->keys[1];//替换 35 key = RC->keys[1];//改变待删除值 36 T = T->children[i - 1]; 37 } 38 } 39 else // 删除节点不在该节点中 40 T = T->children[i-1]; 41 } 42 // 删除后调整 43 Treenode* P = NODE.top(); 44 NODE.pop(); 45 46 while (!NODE.empty()) 47 { 48 T = P; 49 P = NODE.top();//该节点根树 50 NODE.pop(); 51 52 //比最小键值数小，做调整 53 if (T->keyNum < 1) 54 { 55 //找到该结点属于该根节点的第几个孩子 56 int i = 0; 57 for (; i <T->childNum; ++i) 58 if (T == P->children[i]) break; 59 60 //找该节点两边的兄弟结点 61 Treenode* LB = i > 0 ? P->children[i - 1] : NULL; 62 Treenode* RB = i < P->childNum-1 ? P->children[i + 1] : NULL; 63 64 if (LB && LB->keyNum > 1) 65 {// 左兄弟存在且键值富余 66 // i(P) 67 // i-1(LB) i(T) 68 //T中键值往后移动，便于插入 69 for (int k = T->keyNum + 1; k > 1; --k) 70 T->keys[k] = T->keys[k - 1]; 71 72 for (int k = T->childNum; k > 0; --k) 73 T->children[k] = T->children[k - 1]; 74 75 //旋转 76 T->keys[1] = P->keys[i]; 77 T->children[0] = LB->children[LB->childNum - 1]; 78 ++T->keyNum; 79 ++T->childNum; 80 81 P->keys[i] = LB->keys[LB->keyNum]; 82 //LB->children[LB->childNum - 1] = NULL; 83 --LB->childNum; 84 --LB->keyNum; 85 } 86 else if (RB && RB->keyNum > 1) 87 {// 右兄弟存在且键值富余 88 // i+1(P) 89 // i(T) i+1(RB) 90 T->keys[T->keyNum+1] = P->keys[i+1]; 91 T->children[T->childNum] = RB->children[0]; 92 ++T->keyNum; 93 ++T->childNum; 94 95 P->keys[i+1] = RB->keys[1]; 96 for (int k = 1; k <= RB->keyNum - 1; ++k) 97 RB->keys[k] = RB->keys[k + 1]; 98 99 for (int k = 0; k < RB->childNum - 1; ++k) 100 RB->children[k] = RB->children[k + 1]; 101 102 --RB->keyNum; 103 --RB->childNum; 104 } 105 else if (LB) 106 { // 左兄弟存在但不富余 107 merge(P, i - 1); 108 T = P->children[i - 1]; 109 } 110 else if (RB) 111 {// 右兄弟存在但不富余 112 merge(P, i); 113 T = P->children[i]; 114 } 115 } 116 } 117 // 树根被借走，树高 -1 118 if (*Root == P && P->keyNum == 0) 119 { 120 *Root = P->children[0]; 121 122 } 123 return true; 124 }
查询
搜索到位空就好
1 //查询该节点 2 bool enquirytree(Treenode* node, int data) 3 { 4 //如果该节点没有值就没有这个data 5 if (node == NULL) 6 return 0; 7 //查询该结点的关键字索引 8 for (int i = 1; i <= node->keyNum; i++) 9 { 10 if (data == node->keys[i]) 11 return 1; 12 if (data < node->keys[i])//如果比i小，查询孩子 13 return enquirytree(node->children[i - 1],data); 14 } 15 //比最后的大 16 return enquirytree(node->children[node->keyNum], data); 17 }