#include<stdio.h>
#include<stdlib.h>typedef struct Node
{int level;//树的阶数int keyNum;//关键字的数量int childNum;//孩子数量int* keys;//关键字数组struct Node** children;//孩子数组struct Node* parent;//父亲指针
}Node;//初始化
Node* initNode(int level)
{Node* node = (Node*)malloc(sizeof(Node));//空的根节点申请空间node->level = level;node->keyNum = 0;node->childNum = 0;node->keys = (int*)malloc(sizeof(int) * (level + 1));//0号单元不使用，然后1-level单元是关键字存放，level+1单元是用来分裂的时候node->children = (Node**)malloc(sizeof(Node*) * level);node->parent = NULL;int i;for (i = 0; i < level; i++){//关键字数组和孩子数组申请空间后需要初始化node->keys[i] = 0;node->children[i] = NULL;}//node->keys[i] = 0;//申请空间是level+1的，所以i位置单元需要初始化return node;
}//在结点中寻找合适的插入索引
int findSuiteIndex(Node* node, int data)
{int index;//为什么从1开始，关键字数组keys是从1开始，0号单元不使用，在keys关键组数组找到合适的左右范围内进行插入关键字for (index = 1; index <= node->keyNum; index++){if (data < node->keys[index]){break;//找到这里区间了，就退出，然后就在不大于这个区间进行插入操作 OK?}}return index;//返回这个下标索引(此时index的索引对应的keys[index]值是大于data的，所以你插入需要插入keys[index]的左边，故遇到index-1的时候需要理解过来，因为返回的是index，但是你的位置需要放在index-1)
}//找到合适的叶子结点
Node* findSuiteLeafNode(Node* T, int data)
{if (T->childNum == 0){return T;//孩子数量为0。证明此时就是叶子节点，那就直接返回T}else {//寻找索引 需-1int index = findSuiteIndex(T, data);//返回的肯定是左边的 所以index需要-1//不懂的回去看findSuiteIndex函数的最后一条注释return findSuiteLeafNode(T->children[index - 1], data);}
}void addData(Node* node, int data,Node** T)//Node** T插入函数有可能会改变根结点，所以先引入
{int index = findSuiteIndex(node, data);//mid//找到合适的关键字索引，腾出位置给它，(level+1)就体现了for (int i = node->keyNum; i >= index; i--){node->keys[i + 1] = node->keys[i];}node->keys[index] = data;node->keyNum = node->keyNum + 1;//判断是否进行分裂if (node->keyNum == node->level)//当前关键字数量max == m阶树，那就需要分裂{//找到分裂的位置int mid = node->level / 2 + node->level % 2;//分裂过程Node* lchild = initNode(node->level);Node* rchild = initNode(node->level);//两个新申请的空间 要将mid左右的关键字赋回给他们这两个新申请的空间（int i = 1 关键字是从1开始//左for (int i = 1; i < mid; i++){//lchild->keys[i] = node->keys[i];//左边的空间拿回mid前半部分数据//lchild->keyNum++;addData(lchild, node->keys[i], T);//看不懂的就用前两个注释的代码}//右for (int i = mid + 1; i <= node->keyNum; i++){//rchild->keys[i] = node->keys[i];//rchild->keyNum++;addData(rchild, node->keys[i], T);//看不懂的就用前两个注释的代码}//左右新申请的空间拿回各自的关键字之后，也要拿回连着的孩子//左for (int i = 0; i < mid; i++)//i = 0孩子是从0开始{lchild->children[i] = node->children[i];//给孩子//如果说分裂出去的关键字连有孩子，那么就给左关键字管if (node->children[i] != NULL){node->children[i]->parent = lchild;lchild->childNum++;}}//右int index = 0;for (int i = mid; i < node->childNum; i++){rchild->children[index++] = node->children[i];if (node->children[i] != NULL){node->children[i]->parent = rchild;rchild->childNum++;}}//对父亲进行判断if (node->parent == NULL){//如果此时插入的关键字并没有根节点Node* newParent = initNode(node->level);addData(newParent, node->keys[mid], T);newParent->children[0] = lchild;newParent->children[1] = rchild;newParent->childNum = 2;lchild->parent = newParent;rchild->parent = newParent;*T = newParent;}else//若{//找到mid应处于 node->parent 的哪个区间里int index = findSuiteIndex(node->parent, node->keys[mid]);//上一层//mid是分裂出去上一层，所以lchild 和rchild的parent都是要指向mid的 求index是为了得到mid在这一层（分裂上去之后的这一层）的区间位置lchild->parent = node->parent;rchild->parent = node->parent;//mid的左孩子就是nodenode->parent->children[index - 1] = lchild;//判断mid的右孩子是否有值if (node->parent->children[index] != NULL){//node->parent->childNum - 1实际上就是mid的孩子数量 childNum - 1取得最后(右)的孩子下标，孩子是从0开始的，关键字才是1开始for (int i = node->parent->childNum - 1; i >= index; i--){node->parent->children[i + 1] = node->parent->children[i];//index这个下标索引就空出一个，供rchild插入}}node->parent->children[index] = rchild;//左孩子是本身就连着的，rchild呢才是新增的孩子，故+1就好了childNumnode->parent->childNum++;addData(node->parent, node->keys[mid], T);}}
}
void insert(Node** T, int data)
{Node* node = findSuiteLeafNode(*T, data);addData(node, data, T);	
}
void printTree(Node* T)
{if (T != NULL){for (int i = 1; i <= T->keyNum; i++){printf("%d ", T->keys[i]);}printf("\n");for (int i = 0; i < T->childNum; i++){printTree(T->children[i]);}}}
//查找
Node* find(Node* node, int data)
{if (node == NULL){return NULL;}for (int i = 1; i <= node->keyNum; i++){if (data == node->keys[i]){return node;}else if (data < node->keys[i]){return find(node->children[i - 1], data);}else{if (node->keyNum != i && data < node->keys[i + 1]){return find(node->children[i], data);}}}return find(node->children[node->keyNum], data);
}
int main()
{Node* T = initNode(5);insert(&T, 1);insert(&T, 2);insert(&T, 6);insert(&T, 7);insert(&T, 11);insert(&T, 4);insert(&T, 8);insert(&T, 13);insert(&T, 10);insert(&T, 5);insert(&T, 17);insert(&T, 9);insert(&T, 16);insert(&T, 20);insert(&T, 3);insert(&T, 12);insert(&T, 14);insert(&T, 18);insert(&T, 19);insert(&T, 15);printf("遍历的情况如下:\n");printTree(T);printf("查找如下:\n");Node* node = find(T, 7);if (node){for (int i = 1; i <= node->keyNum; i++) {printf("%d ", node->keys[i]);}}return 0;
}