#include
#include
using?namespace?std;
#include
#include
#include
#include
#define?m?3//2-3樹?
#define?KeyType?int//關鍵字類型?
#define?Record?char//記錄?
#define?INFINITY?INT_MAX//初始化用?
typedef?struct?BTNode{
????int?keynum;//結點中關鍵字個數
????struct?BTNode?*parent;//指向雙親結點?
????KeyType?key[m+1];//關鍵字向量0號單元未用
????struct?BTNode?*ptr[m+1];//子樹指針向量，0號單元用于輔助使用??
????Record?*recptr[m+1];//記錄指針向量，0號單元未用?
}BTNode*BTree;
typedef?struct{
????BTNode?*pt;//指向找到的結點?
????int?i;//在結點中的關鍵字序號?
????int?tag;//1：查找成功?0：查找失敗?
}Result;//B-樹的查找結果類型?

//-------------------------函數部分----------------------------------//?
void?InitialBTree（BTree?&T）{?
//開辟新結點，并對結點進行初始化?
????int?i;
????T=（BTree）malloc（sizeof（BTNode））;
????if（!T）exit（0）;
????T->parent=NULL;
????T->keynum=0;
????for（i=0;i<=m;i++）
????{
????????T->ptr[i]=NULL;
????????T->key[i]=INFINITY;//初始化關鍵字為無窮大?
????????T->recptr[i]=NULL;
????}
}?

int?Search（BTree?pKeyType?K）{?
//在p->key[1...keynum]中查找，使i滿足key[i]<=k<=key[i+1]?
????int?i;
????if（p->key[1]==INFINITY）
????{
????????return?1;//新結點?
????}????
????if（K<=p->key[1]）?
????{
????????return?1;//查找值小于等于結點中最小關鍵字?
????}????
????for（i=1;ikeynum;i++）
????{
????????if（p->key[i]<=K&&p->key[i+1]>=K）
????????return?i+1;//返回要查找的位置?
????}????
????return?i+1;//找不到滿足條件的關鍵字，返回要插入的地方?
}????
Result?SearchBTree（BTree?TKeyType?K）
{
????if（!T）
????{
????????cout?<????????getch（）;
????}????
????Result?res;//用于接收返回結果?
????BTree?pcheck=T;//pcheck指向待查結點，從根開始找?
????BTree?ppa=pcheck->parent;//ppa指向pcheck的雙親?
????int?found=false;//初始化?
????int?position=0;
????while（pcheck&&!found）//找到了或者到葉子了退出循環?
????{?
????????position=Search（pcheckK）;//找到K值的位置，若沒有則為K要插入的位置?
????????if（pcheck->key[position]==K）found=true;//找到待查關鍵字?
????????else
????????{
????????????ppa=pcheck;//ppa指向pcheck的雙親?
????????????pcheck=pcheck->ptr[position];//在孩子中找?
????????}
????}
????if（found）//查找成功?
????{
????????res.pt=pcheck;//返回結點?
????????res.i=position;//返回找到的位置?
????????res.tag=1;//指示查找成功?
????????return?res;
????}?????
????else?
????{
????????res.pt=ppa;//子結點為空，返回雙親?
????????res.i=position;//返回要插入的位置?
????????res.tag=0;//指示查找失敗?
????????return?res;//查找不成功，返回k的插入位置信息?
????}????
}//SearchBTree
????
void?Insert（BTree?&qint?iKeyType?xBTree?ap）
{//在q結點中i處插入關鍵字X，通過插入建立B樹?
????int?j;
????if（q->key[i]!=INFINITY）
????{
???????for（j=3;j>i;j--）//為新關鍵字的插入留出空間?
???????{
???????????q->key[j]=q->key[j-1];
???????????q->ptr[j]=q->ptr[j-1];
???????????q->recptr[j]=q->recptr[j-1];?
???????}????
????}????
????q->key[i]=x;//將x信息插入key[i]?
????q->ptr[i]=ap;//q->ptr[i]接上ap結點?
????q->keynum++;//keynum記錄值增加??
}
void?Move（BTree?&paBTree?&apBTree?&qchar?status）//分裂結點時對應不同狀態的移動函數?
{
????switch（status）
????{
????????case?‘1‘://父結點關鍵字為1個時，左孩子分裂?
???????????????if（pa->ptr[2]）
?????????????????????{
?????????????????????????pa->recptr[3]=pa->recptr[