数据结构：B-树源代码

#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 << “Empty Tree“ << endl;
        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[