#define  _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
/*B树：
*/#define m 3 //B树的阶
#define minn (m + 1) / 2 - 1//非根节点关键字个数的下限
//B树结构
typedef struct BTNode
{int key[m + 1];//关键字数组(从下标1开始)struct BTNode* ptr[m + 1];//指向孩子节点的指针数组(从下标0开始)int keynum;//关键字的实际个数struct BTNode* parent;//指向父亲节点的指针
}BTNode, *BTree;
//查找结果的节点结构
typedef struct
{BTNode* pt;//记录找到的节点int i;//记录关键词数组的下标bool tag;//记录是否查找成功
}Result;//这两个函数存在互相调用关系，因此在这里提前声明，其余函数都是单一调用，被调用函数的定义放在调用函数之前即可
void Restore(BTree& t, BTree& p);
void Merge(BTree& l, BTree& parent, BTree& r, BTree& t, int i);//查找操作
int Search(BTNode* cur, int key)//在SearchBTree定位到的节点中查找key
{//在cur节点中找第一个不小于key的数，返回数组下标int i = 1;while (i <= cur->keynum && key > cur->key[i]){i++;}return i;
}
void SearchBTree(BTree t, int key, Result &r)//定位key所在节点
{BTNode* cur = t;//遍历查找BTNode* pre = NULL;//指向查找过程中cur的父亲bool flag = false;//记录是否查找成功int i = 0;//记录查找到的节点的关键字数组下标while (cur != NULL && flag == false){i = Search(cur, key);//在cur节点中找第一个不小于key的数，返回数组下标if (i <= cur->keynum && key == cur->key[i]){flag = true;}else{pre = cur;cur = cur->ptr[i - 1];//指针下移}}//查找成功，说明key在B树中if (flag == true){r.pt = cur;r.i = i;r.tag = true;}else//查找失败，我们需要将其插入到pre指向的位置{r.pt = pre;r.i = i;r.tag = false;}
}//输出B树(用层次递进的方式)
void printBTree(BTree t, int num)//num表示第几层
{if (t == NULL){return;}//打印当前节点int i = 0;for (i = 1; i <= num; i++){cout << "\t";}for (i = 1; i <= t->keynum; i++){cout << t->key[i] << " ";}cout << endl;//递归打印孩子for (i = 0; i <= t->keynum; i++){printBTree(t->ptr[i], num + 1);}
}//插入操作（包含5个函数）
void newRoot(BTree& t, BTNode* p, int key, BTNode* ap)//生成新的根节点
{t = (BTNode*)malloc(sizeof(BTNode));if (t != NULL){t->keynum = 1;t->key[1] = key;t->ptr[0] = p;t->ptr[1] = ap;//不要忘记对节点父亲的处理if (p != NULL){p->parent = t;}if (ap != NULL){ap->parent = t;}t->parent = NULL;}
}
void Insert(BTree& q, int i, int key, BTNode* ap)
{//顺序表的中间位置插入int n = q->keynum;for (int j = n; j >= i; j--){q->key[j + 1] = q->key[j];q->ptr[j + 1] = q->ptr[j];}q->key[i] = key;q->ptr[i] = ap;if (ap != NULL){ap->parent = q;}q->keynum++;
}
void split(BTree& q, int s, BTree& ap)//将q以s位置为中心分成两个节点q和ap(孩子也需要合理分割)
{int n = q->keynum;ap = (BTNode*)malloc(sizeof(BTNode));if (ap != NULL){ap->ptr[0] = q->ptr[s];for (int i = s + 1, j = 1; i <= n; i++, j++)//i是q的下标，j是ap的下标{ap->key[j] = q->key[i];ap->ptr[j] = q->ptr[i];}ap->keynum = n - s;ap->parent = q->parent;q->keynum = s - 1;for (int i = 0; i <= ap->keynum; i++){if (ap->ptr[i] != NULL){ap->ptr[i]->parent = ap;}}}
}
void InsertBtree(BTree& t, int key, BTNode* q, int i)//在以t为根的B树中的q节点的第i个位置插入值为key的节点
{int x = key;//插入的关键字int s;//记录分裂位置BTNode* ap = NULL;//分裂产生的新的节点if (q == NULL)//如果是空树，则需要创建一个新的节点{newRoot(t, NULL, key, NULL);return;}bool needNewRoot = false;//记录是否创建了新的根节点bool finish = false;//记录是否回溯结束//回溯上传while (needNewRoot == false && finish == false){Insert(q, i, x, ap);//x和ap分别插入到q->key[i]和p->ptr[i]if (q->keynum < m){finish = true;//如果不需要调整，则改变finish变量，回溯结束}else//q->keynum == m(由于是一个一个插入，因此只可能相等){//此时需要分裂q节点s = (m + 1) / 2;//m / 2向上取整split(q, s, ap);//将q以s位置为中心分成两个节点x = q->key[s];//更新待插入的关键字if (q->parent != NULL)//如果q的父亲存在{q = q->parent;i = Search(q, x);}else//q的父亲不存在，说明需要创建一个新的根节点{needNewRoot = true;}}}if (needNewRoot == true){newRoot(t, q, x, ap);}
}
void insertKeyOperater(BTree& t)
{int key = 0;Result r;//保存查找结果while (1){cout << "请输入想要插入的关键字:" << endl;cin >> key;//查找key应该插入到的p节点的第i个位置SearchBTree(t, key, r);if (r.tag == true)//查找成功，说明B树中含有key元素{cout << "B树中已存在Key为：" << key << "的节点，插入失败！" << endl;}else//未找到Key的元素才需要执行插入操作{InsertBtree(t, key, r.pt, r.i);//在以t为根的B树中插入Keycout << "插入成功!" << endl;cout << "插入后的B树如下：" << endl;printBTree(t, 1);}cout << "是否继续新插入？(y/n)" << endl;char c;cin >> c;cout << endl;if (c == 'n' || c == 'N'){break;}}
}//删除操作（包含七个函数）
void Merge(BTree& l, BTree& parent, BTree& r, BTree& t, int i)//将r向l合并，根节点为t，r在parent->ptr数组的第i个位置
{//将父亲的第i个key给l（由于合并之后会少一个孩子，我们需要维持key的数目 == 孩子数目 - 1）l->key[l->keynum + 1] = parent->key[i];//由于key从下标1开始，ptr从下标0开始，为了节省代码量，我们可以先合并r的ptr[0]//然后r的key和ptr的移动就可以用一个for循环l->ptr[l->keynum + 1] = r->ptr[0];if (l->ptr[l->keynum + 1] != NULL){l->ptr[l->keynum + 1]->parent = l;}++l->keynum;for (int j = 1; j <= r->keynum; j++){l->key[l->keynum + j] = r->key[j];l->ptr[l->keynum + j] = r->ptr[j];if (l->ptr[l->keynum + j] != NULL){l->ptr[l->keynum + j]->parent = l;}++l->keynum;}//删除节点rparent->ptr[i] = NULL;free(r);r = NULL;//调整父亲节点//从第i + 1个元素开始，前移parent的key和ptr的元素，覆盖掉第i个位置for (int j = i; j < parent->keynum; j++){parent->key[j] = parent->key[j + 1];parent->ptr[j] = parent->ptr[j + 1];}--parent->keynum;//由于合并之后parent会少一个关键字，因此还需要根据parent的类型，判断parent关键字个数是否低于下限if (parent == t){//当parent是根节点，并且关键字个数减为0之后，parent的ptr数组中剩下的那个节点变成新的根节点if (parent->keynum == 0){for (int j = 0; j <= parent->keynum + 1; j++){if (parent->ptr[j] != NULL){t = parent->ptr[j];t->parent = NULL;break;}}}}else{//parent不是根节点，并且关键字个数少于minn（(m + 1) / 2 - 1），则需要递归调整(调用Restore函数)if (parent->keynum < minn){Restore(t, parent);}}
}
void Borrow(BTree& p, BTree& lbro, BTree& rbro, BTree& parent, int i)//借兄弟的关键字
{//谁有就借谁，都有任选其一//实现过程：父亲的关键字给p，兄弟的关键字给父亲if (lbro != NULL && lbro->keynum > minn){//后移p节点的key数组元素（借来的元素需要放到第一个位置，因此需要移动）for (int j = p->keynum + 1; j > 0; j--){if (j > 1)//牢记关键字数组下标从1开始{p->key[j] = p->key[j - 1];}p->ptr[j] = p->ptr[j - 1];}//父下兄上p->key[1] = parent->key[i];parent->key[i] = lbro->key[lbro->keynum];//维持好节点之间的关系p->ptr[0] = lbro->ptr[lbro->keynum];if (p->ptr[0] != NULL){p->ptr[0]->parent = p;}lbro->ptr[lbro->keynum] = NULL;//删除多余的孩子//维护节点内关键字的个数++p->keynum;--lbro->keynum;}else//否则向右兄弟借{//父下兄上p->key[p->keynum + 1] = parent->key[i + 1];parent->key[i + 1] = rbro->key[1];//维持好节点之间的关系p->ptr[p->keynum + 1] = rbro->ptr[0];if (p->ptr[p->keynum + 1] != NULL){p->ptr[p->keynum + 1]->parent = p;}//前移右兄弟的key数组元素（覆盖被借走的key）for (int j = 0; j < rbro->keynum; j++){if (j > 0) // 牢记关键字数组下标从1开始{rbro->key[j] = rbro->key[j + 1];}rbro->ptr[j] = rbro->ptr[j + 1];}rbro->ptr[rbro->keynum] = NULL;//删除多余的孩子//维护节点内关键字的个数++p->keynum;--rbro->keynum;}
}
void Restore(BTree& t, BTree& p)//在以t为根的B树中，调整p节点(删除后破坏了下限需要调整)
{//声明变量：p节点的父亲，左右兄弟(默认为空)BTree parent = p->parent, lbro = NULL, rbro = NULL;//通过寻找p在其父亲的ptr数组下标来确定p的左右兄弟int i = 0;//保存ptr数组下标for (i = 0; i <= parent->keynum; i++){if (parent->ptr[i] == p){break;}}//确定p的左兄弟if (i > 0){lbro = parent->ptr[i - 1];}//确定p的右兄弟if (i < parent->keynum){rbro = parent->ptr[i + 1];}//判断左右兄弟是否有多余的keyif ((lbro != NULL && lbro->keynum > minn)|| (rbro != NULL && rbro->keynum > minn)){Borrow(p, lbro, rbro, parent, i);//如果有，则向兄弟借}else//如果没有，则合并兄弟：谁存在合并谁，都有任选其一合并（这里合并左兄弟）{//我们可以统一让右侧节点向左侧节点合并，可以统一代码。//唯一需要注意的是最后一个参数是右侧节点的parent->ptr数组下标if (lbro != NULL){Merge(lbro, parent, p, t, i);//将p向lbro合并，t为根节点，p在parent->ptr数组的第i个位置}else if(rbro != NULL){Merge(p, parent, rbro, t, i + 1);//将rbro向p合并，t为根节点，rbro在parent->ptr数组的第i + 1个位置}}
}
void Remove(BTree& p, int i)//删除p节点中的key[i]
{//顺序表的删除int j = i;for (j = i; j < p->keynum; j++){p->key[j] = p->key[j + 1];p->ptr[j] = p->ptr[j + 1];}--p->keynum;
}
void Successor(BTree& p, int i)//在p的第i棵子树中找最靠左的节点，最后p指针指向待删除节点
{BTree leaf = p;if (p == NULL){return;}leaf = p->ptr[i];while (leaf->ptr[0] != NULL){leaf = leaf->ptr[0];//一直向左找}//用p保存待删除节点的信息p->key[i] = leaf->key[1];//关键字从下标1开始p = leaf;
}
void DeleteBTree(BTree& t, BTree& p, int i)//在以t为根节点的B树中删除p节点中第i个关键字
{if (p->ptr[i] != NULL)//如果p的第i个节点的孩子不为空，说明p不是终端节点{//找中序遍历前驱或后继（这里以后继为例）替代Successor(p, i);//在p的第i棵子树中找最靠左的节点i = 1;}//到这里p一定指向终端节点Remove(p, i);//删除p节点的key[i]//对于判断删除之后是否低于关键字的下限需要分类讨论//1.如果p是根节点，并且关键字个数少于1个if (p->parent == NULL && p->keynum == 0){t = NULL;}//2.p不是根节点，关键字个数低于下限if (p->parent != NULL && p->keynum < minn){Restore(t, p);//调整B树}
}
void deleteKeyOperater(BTree& t)
{Result r;//保存查找结果int key = 0;while (1){cout << "请输入想要删除的关键字:" << endl;cin >> key;SearchBTree(t, key, r);if (r.tag == true)//如果查找成功，则可以执行删除操作{DeleteBTree(t, r.pt, r.i);cout << "删除成功!" << endl;cout << "删除后的B树如下：" << endl;printBTree(t, 1);}else//如果B树中不存在key，则直接退出{cout << "B树中不存在Key为：" << key << "的节点，删除失败！" << endl;break;}}
}int main()
{BTree t = NULL;//B树的根指针insertKeyOperater(t);deleteKeyOperater(t);return 0;
}