#include 
  
   
#include 
   
     #include 
    
      using namespace std; class BTree{ static const int M = 2; struct BTNode{ int keyNum; int key[2 * M - 1]; //关键字数组 struct BTNode* child[2 * M];//孩子结点数组 bool isLeaf; }; BTNode* root; //在插入时，保证pNode结点的关键字少于2*M-1个 void InsertNonFull(BTNode* pNode, int key); //当child结点有2M-1个关键字时，分裂此结点 void SplitChild(BTNode* parent, int i, BTNode* child); //两个M-1个元素的结点合并 void merge(BTNode* parent, BTNode* pNode1, BTNode* pNode2, int index); //找到比pNode结点第一个关键字小的最大的关键字，也就是前继结点 int predecessor(BTNode* pNode); //找到后继结点 int successor(BTNode* pNode); //pNode1向parent要一个结点key[index]，parent向pNode0要一个结点，pNode1关键字个数为M-1 void ExchangeLeftNode(BTNode *parent, BTNode* pNode0, BTNode* pNode1, int index); void ExchangeRightNode(BTNode* parent, BTNode* pNode1, BTNode *pNode2, int index); //删除，结点关键字个数不少于M void RemoveNonLess(BTNode* pNode, int key); void DiskWrite(BTNode* pNode); void DiskRead(BTNode *pNode); BTNode* Search(BTNode* pNode, int key, int &index); public: BTree(); ~BTree(); BTNode* search(int key, int &index); void insert(int key); void remove(int key); //按层级打印。 void PrintRow(); }; BTree::BTree() { root = new BTNode(); root->isLeaf = true; root->keyNum = 0; DiskWrite(root); } BTree::~BTree() { struct BTNode* pNode; queue
     
       q; q.push(root); while (!q.empty()){ pNode = q.front(); q.pop(); if (pNode->isLeaf) continue; for (int i = 0; i <= pNode->keyNum; i++) q.push(pNode->child[i]); delete pNode; } } void BTree::DiskWrite(BTNode* pNode) { } void BTree::DiskRead(BTNode *pNode) { } BTree::BTNode* BTree::Search(BTNode* pNode, int key, int &index) { int i = 0; while (i
      
       keyNum&&key>pNode->key[i])//找到第一个大于等于key的下标 i++; if (i < pNode->keyNum&&key == pNode->key[i]){//如果找到关键字，返回 index = i; return pNode; } if (pNode->isLeaf)//已经搜到叶子结点，不存在 return NULL; else{ DiskRead(pNode->child[i]); return Search(pNode->child[i], key, index);//在第一个大于key值的孩子节点中递归搜索 } } void BTree::InsertNonFull(BTNode* pNode, int key) { int i = pNode->keyNum - 1; if (pNode->isLeaf){//如果是叶子结点，直接插入 while (i >= 0 && key < pNode->key[i]){ pNode->key[i + 1] = pNode->key[i]; i--; } pNode->key[i + 1] = key; pNode->keyNum++; DiskWrite(pNode); } else { while (i >= 0 && key < pNode->key[i]) i--;//找到第一个小于等于key的下标 i++; DiskRead(pNode->child[i]); if (pNode->child[i]->keyNum == 2 * M - 1){//判断孩子结点是否有2*M-1个关键字，有就需要分裂 SplitChild(pNode, i, pNode->child[i]); if (key>pNode->key[i])//如果key比上移到父节点的元素大 i++; } InsertNonFull(pNode->child[i], key);//已保证孩子结点关键字个数少于2*M-1个 } } void BTree::SplitChild(BTNode* parent, int i, BTNode* child) { int j; struct BTNode* pNode = new BTNode(); pNode->isLeaf = child->isLeaf; pNode->keyNum = M - 1; for (j = 0; j < M - 1; j++)//将child结点的后M-1个关键字赋给新节点 pNode->key[j] = child->key[j + M]; if (!child->isLeaf){//如果child不是叶子结点，将其后M个孩子结点赋给新节点。 for (j = 0; j < M; j++) pNode->child[j] = child->child[j + M]; } child->keyNum = M - 1; for (j = parent->keyNum; j > i; j--) parent->child[j + 1] = parent->child[j];//将child结点的父节点parent下标i以后的结点指针都向后移动一位， parent->child[j + 1] = pNode;//将新生成的结点当成parent的一个孩子 for (j = parent->keyNum - 1; j >= i; j--) //将i后面的关键字都向后移动一位 parent->key[j + 1] = parent->key[j]; parent->key[j + 1] = child->key[M - 1];//将孩子结点的中间结点移到父节点的指定位置 parent->keyNum++; DiskWrite(parent); DiskWrite(pNode); DiskWrite(child); } void BTree::merge(BTNode* parent, BTNode* pNode1, BTNode* pNode2, int index) { pNode1->key[M - 1] = parent->key[index]; for (int i = 0; i < M - 1; i++)//将pNode2的关键字移到pNode1中 pNode1->key[i + M] = pNode2->key[i]; pNode1->keyNum = 2 * M - 1; if (!pNode1->isLeaf){//如果不是叶子，将pNode2的孩子指针也移到pNode1中 for (int i = 0; i < M; i++) pNode1->child[i