不得不说，这个我写了两天。第一天晚上想移植一篇博客的，后来经过四个小时发现是错了谁懂啊！今天早上又找了一篇，大错误我都改了，有一个潜在的小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 keyNum; index++) 7 if (data 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 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 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 else73 {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 //将右兄弟移入LC13 int m = LC->keyNum;14 for (int i = 1; i 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 childNum; ++i)21 {22 LC->children[ n+ i] = RC->children[i];23 ++LC->childNum;24 }25 26 for (int i = pos + 1; i keyNum; ++i)27 {28 P->keys[i] = P->keys[i + 1];29 }30 for (int i = pos + 1; i 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 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 keyNum && T->keys[i-1] == key) 20 {// 删除键值在该节点中 21 if (T->childNum==0) 22 {// 叶子节点，删除 23 for (int k=i-1; i 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 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 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 keyNum - 1; ++k) 97 RB->keys[k] = RB->keys[k + 1]; 98 99 for (int k = 0; k 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 // 树根被借走，树高 -1118 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 keyNum; i++) 9 {10 if (data == node->keys[i])11 return 1;12 if (data keys[i])//如果比i小，查询孩子13 return enquirytree(node->children[i - 1],data);14 }15 //比最后的大16 return enquirytree(node->children[node->keyNum], data);17 }