不得不说，这个我写了两天。第一天晚上想移植一篇博客的，后来经过四个小时发现是错了谁懂啊！今天早上又找了一篇，大错误我都改了，有一个潜在的小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 }
标签：node,结点,删除,int,创建,keys,keyNum,children From： https://www.cnblogs.com/saucerdish/p/17865332.html