头文件
#pragma on #include<stdio.h> #include<iostream> #include<stdlib.h> #include<string.h> #include<assert.h> using namespace std; #define M 5//阶数 typedef struct btnode { int keynum; // 当前关键字数量 int keys[M]; // 关键字数组（下标0开始使用，keys[keynum]作为哨兵） struct btnode* parent; // 父节点指针 struct btnode* ptr[M + 1]; // 子树指针数组（ptr[keynum]作为哨兵） } btnode; // B-树结构 typedef struct btree { btnode* root; // 根节点 int size; // 树中关键字总数（可选） } btree; // 查找结果结构 typedef struct Result { btnode* pNode; // 找到的节点 int index; // 关键字位置（或应该插入的位置） bool found; // 是否找到 } Result; //工具函数 //1.申请Result结构体变量，用于节点查找结构的返回 Result* Buy_ResultNode(); //2.购买新节点，用于分裂 btnode* Buy_Node(); //3.插入的调整函数(可能不止一次的上溢出，所以分裂也可能不止一次) void Insert_Adjust(btree* pTree, btnode* node); //4.插入的单次分裂(上溢出了，需要一次分裂) btnode* SplitNode(btree* pTree, btnode* node); //普通函数 //1.初始化 void Init_btree(btree* pTree); //2.查找 Result* Search_btree(btree* pTree, int val); //3.插入 bool Insert_btree(btree* pTree, int val); //4.打印(中序遍历) void Show_InOrder(btnode* root);//递归 //5.删除 bool Delete_btree(btree* pTree, int val); //6.删除的调整函数 void Delete_Adjust(btree* pTree, btnode* Node); //问兄弟借元素(通用的)//pp是，当前节点和借的兄弟节点的父节点 index：当前节点和借的兄弟节点夹住的父节点的元素下标 //7.从左兄弟借 void BorrowFrom_LeftBro(btnode* pp, int index); //8.从右兄弟借 void BorrowFrom_RightBro(btnode* pp, int index); //问兄弟借操作，父节点不会少元素，所以不需要进行连续的下溢出判断 //但是和兄弟合并操作，父节点会少一个元素，所以需要进行连续的下溢出判断 //9.和左兄弟合并 (把合并之后的节点返回出来) btnode* Merge_LeftBro(btnode* pp, int index); //10.和右兄弟合并 btnode* Merge_RightBro(btnode* pp, int index);
源文件
#include"b-树.h" //工具函数 //1.申请Result结构体变量，用于节点查找结构的返回 Result* Buy_ResultNode() { Result* res = (Result*)malloc(sizeof(Result)); if (!res) { perror("Failed to allocate result"); exit(EXIT_FAILURE); } res->pNode = nullptr; res->index = -1; res->found = false; return res; } //2.购买新节点，用于分裂 btnode* Buy_Node() { btnode* newnode = (btnode*)malloc(sizeof(btnode)); if (newnode == nullptr) { cout << "buynode err" << endl; return nullptr; } newnode->keynum = 0; newnode->parent = nullptr; for (int i = 0; i <= M; i++) { newnode->ptr[i] = NULL; } return newnode; } //普通函数 //1.初始化 void Init_btree(btree* pTree) { assert(pTree != nullptr); pTree->root = nullptr; pTree->size = 0; } // 在节点中查找关键字位置（二分查找优化） int FindPos(btnode* node, int val) { int left = 0, right = node->keynum - 1; while (left <= right) { int mid = left + (right - left) / 2; if (node->keys[mid] == val) { return mid; } else if (node->keys[mid] < val) { left = mid + 1; } else { right = mid - 1; } } return left; // 返回应该插入的位置 } //2.查找 Result* Search_btree(btree* pTree, int val) { assert(pTree != nullptr); Result* res = Buy_ResultNode(); btnode* cur = pTree->root; while (cur) { int pos = FindPos(cur, val); if (pos < cur->keynum && cur->keys[pos] == val) { res->pNode = cur; res->index = pos; res->found = true; return res; } res->pNode = cur; res->index = pos; // 继续向下查找 cur = cur->ptr[pos]; } // 没找到 res->found = false; return res; } //3.插入 bool Insert_btree(btree* pTree, int val) { assert(pTree != nullptr); if (pTree->root == NULL) { btnode* new_node = Buy_Node(); new_node->keys[0] = val; new_node->keynum = 1; pTree->root = new_node; pTree->size++; return true; } // 查找插入位置 Result* res = Search_btree(pTree, val); if (res->found) { free(res); return false; // 关键字已存在 } // 在叶子节点插入 btnode* leaf = res->pNode; int pos = res->index; free(res); // 移动关键字，腾出位置 for (int i = leaf->keynum; i > pos; i--) { leaf->keys[i] = leaf->keys[i - 1]; } leaf->keys[pos] = val; leaf->keynum++; pTree->size++; if (leaf->keynum == M) { // 节点已满（上溢） Insert_Adjust(pTree, leaf); } return true; } //插入的调整函数(可能不止一次的上溢出，所以分裂也可能不止一次) void Insert_Adjust(btree* pTree, btnode* node) { assert(pTree != nullptr && node != nullptr); while (node != nullptr && node->keynum == M) { btnode* right = SplitNode(pTree, node); int mid_key = node->keys[M / 2];//中间关键字(要提升) // 更新原节点关键字数（去掉中间关键字） node->keynum = M / 2; // 如果node是根节点 if (node->parent == NULL) { btnode* new_root = Buy_Node(); new_root->keys[0] = mid_key; new_root->keynum = 1; new_root->ptr[0] = node; new_root->ptr[1] = right; node->parent = new_root; right->parent = new_root; pTree->root = new_root; break; } // node有父节点 else { btnode* parent = node->parent; int pos = FindPos(parent, mid_key); // 在父节点中插入中间关键字 for (int i = parent->keynum; i > pos; i--) { parent->keys[i] = parent->keys[i - 1]; parent->ptr[i + 1] = parent->ptr[i]; } parent->keys[pos] = mid_key; parent->ptr[pos] = node; // 左子树 parent->ptr[pos + 1] = right; // 右子树 parent->keynum++; // 设置父指针 right->parent = parent; // 继续向上检查 node = parent; } } } //插入的单次分裂(上溢出了，需要一次分裂) btnode* SplitNode(btree* pTree, btnode* node) { int mid = M / 2; // 创建右节点 btnode* right = Buy_Node(); right->parent = node->parent; // 将右半部分关键字移到新节点（跳过中间关键字） int j = 0; for (int i = mid + 1; i < M; i++) { right->keys[j] = node->keys[i]; j++; } right->keynum = j; // 如果不是叶子节点，复制子树指针 if (node->ptr[0] != nullptr) { j = 0; for (int i = mid + 1; i <= M; i++) { right->ptr[j] = node->ptr[i]; if (right->ptr[j]) { right->ptr[j]->parent = right; } j++; } } return right; } //4.打印(中序遍历) void Show_InOrder(btnode* root){//递归 if (root == nullptr) return; for (int i = 0; i < root->keynum; i++) { // 先遍历左子树 if (root->ptr[i] != NULL) { Show_InOrder(root->ptr[i]); } // 访问当前关键字 printf("%d ", root->keys[i]); } // 最后遍历最右边的子树 if (root->ptr[root->keynum] != NULL) { Show_InOrder(root->ptr[root->keynum]); } } //5.删除 bool Delete_btree(btree* pTree, int val) { assert(pTree != nullptr); Result* res = Search_btree(pTree, val); if (!res->found) { free(res); return false; } btnode* node = res->pNode; int index = res->index; free(res); // 情况1：在叶子节点 if (node->ptr[0] == NULL) { // 直接删除关键字 for (int i = index; i < node->keynum - 1; i++) { node->keys[i] = node->keys[i + 1]; } node->keynum--; pTree->size--; // 检查下溢 if (node->keynum < (M + 1) / 2 - 1 && node != pTree->root) { Delete_Adjust(pTree, node); } // 如果根节点变空 if (pTree->root->keynum == 0) { btnode* old_root = pTree->root; if (pTree->root->ptr[0]) { pTree->root = pTree->root->ptr[0]; pTree->root->parent = NULL; } else { pTree->root = NULL; } free(old_root); } return true; } // 情况2：在内部节点 else { // 找到前驱（左子树的最大值） btnode* pred_node = node->ptr[index]; while (pred_node->ptr[pred_node->keynum] != NULL) { pred_node = pred_node->ptr[pred_node->keynum]; } int pred_val = pred_node->keys[pred_node->keynum - 1]; // 用前驱替换要删除的关键字 node->keys[index] = pred_val; // 删除前驱（递归调用） return Delete_btree(pTree, pred_val); } } //6.删除的调整函数 void Delete_Adjust(btree* pTree, btnode* node) { assert(pTree != nullptr && node != nullptr); if (node == pTree->root || node->keynum >= (M + 1) / 2 - 1) { return; // 根节点或关键字足够 } btnode* parent = node->parent; if (!parent) return; // 找到node在父节点中的位置 int index = 0; while (index <= parent->keynum && parent->ptr[index] != node) { index++; } // 尝试从左兄弟借 if (index > 0) { btnode* left_bro = parent->ptr[index - 1]; if (left_bro->keynum > (M + 1) / 2 - 1) { BorrowFrom_LeftBro(parent, index); return; } } // 尝试从右兄弟借 if (index < parent->keynum) { btnode* right_bro = parent->ptr[index + 1]; if (right_bro->keynum > (M + 1) / 2 - 1) { BorrowFrom_RightBro(parent, index); return; } } // 合并操作 btnode* merged; if (index > 0) { // 与左兄弟合并 merged = Merge_LeftBro(parent, index); } else { // 与右兄弟合并 merged = Merge_RightBro(parent, index); } // 检查父节点是否需要调整 Delete_Adjust(pTree, parent); } //问兄弟借元素(通用的) //pp是，当前节点和借的兄弟节点的父节点 //index：当前节点和借的兄弟节点夹住的父节点的元素下标 //7.从左兄弟借 void BorrowFrom_LeftBro(btnode* pp, int index) { assert(pp != nullptr); btnode* left_bro = pp->ptr[index - 1]; btnode* cur = pp->ptr[index]; // cur右移关键字腾出位置 for (int i = cur->keynum; i > 0; i--) { cur->keys[i] = cur->keys[i - 1]; } for (int i = cur->keynum + 1; i > 0; i--) { cur->ptr[i] = cur->ptr[i - 1]; } // 父节点关键字下移 cur->keys[0] = pp->keys[index - 1]; cur->keynum++; // 左兄弟最后一个关键字上移 pp->keys[index - 1] = left_bro->keys[left_bro->keynum - 1]; // 左兄弟最后一个子树移到cur if (!left_bro->ptr[0]) { // 如果不是叶子节点 cur->ptr[0] = left_bro->ptr[left_bro->keynum]; if (cur->ptr[0]) { cur->ptr[0]->parent = cur; } } left_bro->keynum--; } //8.从右兄弟借 void BorrowFrom_RightBro(btnode* pp, int index) { assert(pp != nullptr); btnode* cur = pp->ptr[index]; btnode* right_bro = pp->ptr[index + 1]; // 父节点关键字下移 cur->keys[cur->keynum] = pp->keys[index]; cur->keynum++; // 右兄弟第一个关键字上移 pp->keys[index] = right_bro->keys[0]; // 右兄弟关键字左移 for (int i = 0; i < right_bro->keynum - 1; i++) { right_bro->keys[i] = right_bro->keys[i + 1]; } // 右兄弟子树左移 if (!right_bro->ptr[0]) { // 如果不是叶子节点 cur->ptr[cur->keynum] = right_bro->ptr[0]; if (cur->ptr[cur->keynum]) { cur->ptr[cur->keynum]->parent = cur; } for (int i = 0; i < right_bro->keynum; i++) { right_bro->ptr[i] = right_bro->ptr[i + 1]; } } right_bro->keynum--; } //问兄弟借操作，父节点不会少元素，所以不需要进行连续的下溢出判断 //但是和兄弟合并操作，父节点会少一个元素，所以需要进行连续的下溢出判断 //9.和左兄弟合并 (把合并之后的节点返回出来) btnode* Merge_LeftBro(btnode* pp, int index) { btnode* left_bro = pp->ptr[index - 1]; btnode* cur = pp->ptr[index]; // 父节点关键字下移 left_bro->keys[left_bro->keynum] = pp->keys[index - 1]; left_bro->keynum++; // 复制cur的关键字到左兄弟 for (int i = 0; i < cur->keynum; i++) { left_bro->keys[left_bro->keynum + i] = cur->keys[i]; } // 复制cur的子树到左兄弟（如果不是叶子节点） if (!cur->ptr[0]) { for (int i = 0; i <= cur->keynum; i++) { left_bro->ptr[left_bro->keynum + i] = cur->ptr[i]; if (left_bro->ptr[left_bro->keynum + i]) { left_bro->ptr[left_bro->keynum + i]->parent = left_bro; } } } left_bro->keynum += cur->keynum; // 父节点关键字左移 for (int i = index - 1; i < pp->keynum - 1; i++) { pp->keys[i] = pp->keys[i + 1]; } // 父节点子树左移 for (int i = index; i < pp->keynum; i++) { pp->ptr[i] = pp->ptr[i + 1]; } pp->keynum--; // 释放cur节点 free(cur); return left_bro; } //10.和右兄弟合并 btnode* Merge_RightBro(btnode* pp, int index) { assert(pp != nullptr); btnode* cur = pp->ptr[index]; btnode* right_bro = pp->ptr[index + 1]; // 父节点关键字下移 cur->keys[cur->keynum] = pp->keys[index]; cur->keynum++; // 复制右兄弟的关键字 for (int i = 0; i < right_bro->keynum; i++) { cur->keys[cur->keynum + i] = right_bro->keys[i]; } // 复制右兄弟的子树（如果不是叶子节点） if (!right_bro->ptr[0]) { for (int i = 0; i <= right_bro->keynum; i++) { cur->ptr[cur->keynum + i] = right_bro->ptr[i]; if (cur->ptr[cur->keynum + i]) { cur->ptr[cur->keynum + i]->parent = cur; } } } cur->keynum += right_bro->keynum; // 父节点关键字左移 for (int i = index; i < pp->keynum - 1; i++) { pp->keys[i] = pp->keys[i + 1]; } // 父节点子树左移 for (int i = index + 1; i < pp->keynum; i++) { pp->ptr[i] = pp->ptr[i + 1]; } pp->keynum--; // 释放右兄弟节点 free(right_bro); return cur; }
