本文共 5012 字，大约阅读时间需要 16 分钟。
#include#include using namespace std;//定义b树的阶数const int m = 4;template struct BTNode{ BTNode ():keyNum(0),key(new T[m+1]),parent(nullptr) { ptr = new BTNode*[m+2]; for(int i = 0; i < m+2; i++) { ptr[i] = nullptr; } } ~BTNode () { delete []key; delete []ptr; } int keyNum; //当前的元素个数 T *key; BTNode **ptr; //指向子节点 BTNode *parent; //指向父节点};template class CBtree{ public: CBtree() { mThead = new BTNode (); } ~CBtree() { delete mThead; } //插入时调整树的状态 void AdjustInsert(BTNode &pTmp); //插入数据 void insertVal(BTNode &pTmp, T val); //删除时的调整树状态 void AdjustDelete(BTNode &pTmp); //B树的删除操作 void deleteVal(BTNode &pTmp, T val); //删除时合并两个节点 void mergeNode(BTNode &left,int i); //B树的查找 BTNode *query(BTNode &pTmp, T val); //打印B树 中序打印，即按顺序打印 void Show(BTNode &pTmp); //返回B树的头节点 BTNode * getHead() { return mThead; }private: BTNode *mThead;};template BTNode *CBtree ::query(BTNode &pTmp, T val){ BTNode *p = &pTmp; while(p != nullptr) { int i = 0; for(; i < p->keyNum; i++) { if(val == p->key[i]) { return p; } else if(val < p->key[i]) { break; } } p = p->ptr[i]; } return nullptr;}template void CBtree ::Show(BTNode &pTmp){ if(pTmp.ptr[0] == nullptr) { for(int i = 0; i < pTmp.keyNum; i++) { cout << pTmp.key[i] << " "; } } else { int i = 0; for(; i < pTmp.keyNum; i++) { Show(*(pTmp.ptr[i])); cout << pTmp.key[i] << " "; } Show(*(pTmp.ptr[i])); }}template void CBtree ::AdjustInsert(BTNode &pTmp){ T val = pTmp.key[pTmp.keyNum/2]; BTNode *p = pTmp.parent; BTNode *rc = new BTNode ; if(p == nullptr) { p = new BTNode ; p->key[0] = val; p->keyNum++; p->ptr[0] = &pTmp; p->ptr[1] = rc; //更改头节点 mThead = p; //当前的pTmp节点的父节点变为新开辟的节点 pTmp.parent = p; } else { int i = p->keyNum-1; for(; i >= 0; i--) { if(p->key[i] > val) { p->key[i+1] = p->key[i]; p->ptr[i+2] = p->ptr[i+1]; } else { break; } } p->key[i+1] = val; p->ptr[i+2] = rc; p->keyNum++; } int j = 0; for(int i = pTmp.keyNum/2+1; i < pTmp.keyNum; i++) { rc->key[j++] = pTmp.key[i]; } pTmp.keyNum -= (j+1); rc->keyNum = j; //新产生的子节点域的父节点指向p rc->parent = p; //递归调整上一个节点 if(p->keyNum > m) { AdjustInsert(*p); }}template void CBtree ::insertVal(BTNode &pTmp, T val){ if(pTmp.ptr[0] == nullptr) { if(pTmp.keyNum == 0) { pTmp.key[0] = val; } //直接将元素插入 int i = pTmp.keyNum-1; for(; i >= 0; i--) { if(pTmp.key[i] > val) { pTmp.key[i+1] = pTmp.key[i]; } else { break; } } pTmp.key[i+1] = val; pTmp.keyNum++; //判断元素的个数是否达到上限 if(pTmp.keyNum > m) { AdjustInsert(pTmp); } //否则直接退出 } else { int i = 0; for(; i < pTmp.keyNum; i++) { if(val < pTmp.key[i]) { break; } } insertVal(*(pTmp.ptr[i]),val); }}template void CBtree ::mergeNode(BTNode &left,int i){ BTNode *p = left.parent; //将所有的元素放到左边的节点中 left.key[left.keyNum++] = p->key[i]; for(int j = 0; j < p->ptr[i+1]->keyNum; j++) { left.key[left.keyNum++] = p->ptr[i+1]->key[j]; } //释放右边的节点 delete p->ptr[i+1]; //修改父节点的指向 for(; i < p->keyNum-1; i++) { p->key[i] = p->key[i+1]; p->ptr[i+1] = p->ptr[i+2]; } //最后一个分支节点置为nullptr p->ptr[i+1] = nullptr; p->keyNum--;}template void CBtree ::AdjustDelete(BTNode &pTmp){ //如果该节点的兄弟节点的keyNum > m/2，则进行旋转操作 //调整节点的父节点一定存在，根节点少于m/2不进行调整 BTNode *p = pTmp.parent; //找到需要调整节点的兄弟节点 int i = 0; for(; i < p->keyNum; i++) { if(pTmp.key[0] < p->key[i]) { break; } } // i--; BTNode *left = nullptr; BTNode *right = nullptr; //判断pTmp是否存在右兄弟 if(i < p->keyNum-1) { //p->ptr[i+1]是pTmp节点 right = p->ptr[i+2]; } //判断pTmp是否存在左兄弟 if(i >= 0) { left = p->ptr[i]; } //如果该节点的所有的兄弟节点的keyNum == m/2; 将父节点与两个子节点中的左右元素合并到一起 //组成一个节点 if(left != nullptr && left->keyNum > m/2) { for(int j = pTmp.keyNum-1; j >= 0; j-- ) { pTmp.key[j+1] = pTmp.key[j]; } pTmp.key[0] = p->key[i]; pTmp.keyNum++; p->key[i] = left->key[left->keyNum-1]; left->keyNum--; } else if(right != nullptr && right->keyNum > m/2) { //向右边旋转 pTmp.key[pTmp.keyNum] = p->key[i+1]; pTmp.keyNum++; p->key[i+1] = right->key[0]; for(int j = 1; j < right->keyNum; j++) { right->key[j-1] = right->key[j]; } right->keyNum--; } else if(left != nullptr)//如果左兄弟存在，与左边合并 { mergeNode(*left,i); } else { mergeNode(pTmp,i+1); }}//删除一个元素template void CBtree ::deleteVal(BTNode &pTmp, T val){ BTNode *p = query(pTmp,val); if(p == nullptr) { return ; } //找到val对应的下标 int i = 0; for(;i < p->keyNum; i++) { if(val == p->key[i]) { break; } } //如果使非叶子节点，则从后向前移位 while(p->ptr[0] != nullptr) { p->key[i] = p->ptr[i+1]->key[0]; p = p->ptr[i+1]; i = 0; } //从后向前覆盖 for(; i < p->keyNum-1; i++) { p->key[i] = p->key[i+1]; } //最后一个叶子节点的元素个数减小1 p->keyNum--; //如果当前节点不是根节点，并且该节点的元素个数少于m/2个，则进行调整 if(p->keyNum < m/2 && p->parent != nullptr) { AdjustDelete(*p); //进行删除元素的调整 }}int main(){ srand((unsigned int)time(NULL)); CBtree bt; for(int i = 0; i < 10; i++) { //int data = rand()%1000; //cout << data << " "; bt.insertVal(*(bt.getHead()),i); } //bt.insertVal(*(bt.getHead()),1); BTNode *p = bt.query(*(bt.getHead()),1); if(p != nullptr) { cout << "存在" << endl; } bt.Show(*(bt.getHead())); cout << endl; bt.deleteVal(*(bt.getHead()),0); bt.Show(*(bt.getHead())); cout << endl; return 0;}
转载地址：http://uxnwi.baihongyu.com/