//B-樹的操作B_Tree.cpp
#include<iostream.h>
#include<iomanip.h>

typedef int KeyType;
typedef int RecType;

#define m 5//定義B-樹的階樹
//B-樹的結(jié)點(diǎn)類型定義
typedef struct BTnode
{ int keynum;  //結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)
  struct BTnode *parent;//指向雙親結(jié)點(diǎn)的指針
  KeyType key[m+1];//組關(guān)鍵字向量
  struct BTnode *ptr[m+1];//子樹指針向量
  RecType *recptr[m+1];//記錄指針向量
}BTreeNode;
typedef BTreeNode *BTree;

//B-樹的查找算法
int BTSearch(BTree T,KeyType k,BTree *p);
//將關(guān)鍵碼k插入到B-樹T中,并返回樹根
BTree Insert(BTree T,KeyType k);
//結(jié)點(diǎn)*p中包含m個(gè)關(guān)鍵字,從中分裂出一個(gè)新結(jié)點(diǎn),并返回新結(jié)點(diǎn)指針
BTree split(BTree p);
//在B-樹T中刪除關(guān)鍵字的操作,情況(2)
int MoveKey(BTree p);
//在B-樹T中刪除關(guān)鍵字的操作,情況(3)
BTree merge(BTree p);
//在B-樹T中刪除關(guān)鍵字k,并返回樹根.
BTree Delete(BTree T,KeyType k);

//B-樹的查找算法
int BTSearch(BTree T,KeyType k,BTree *p)
{BTree q;
 int i;
 *p=q=T;
 while(q!=NULL)
 {*p=q;
  q->key[0]=k;   //設(shè)置哨兵
  for(i=q->keynum;k<q->key[i];i--)//在*q中查找k
   if(i>0&&q->key[i]==k) return i;//查找成功,返回i和p
  q=q->ptr[i];//沿q的第i個(gè)子樹繼續(xù)搜索
 }
 return 0;
}
//將關(guān)鍵碼k插入到B-樹T中,并返回樹根
BTree Insert(BTree T,KeyType k){
 BTree p,s1=NULL,s2=NULL;
 int i;
 if(BTSearch(T,k,&p))       //在樹中搜索k,若找到
  {cout<<setw(3)<<T->key[k];
   return T;               //直接返回,不進(jìn)行插入
  }
 while(p!=NULL){
   p->key[0]=k;            //設(shè)置哨兵
   for(i=p->keynum;k<p->key[i];i--)
    {p->key[i+1]=p->key[i];
     p->ptr[i+1]=p->ptr[i];}
   p->key[i]=k;     //插入關(guān)鍵碼k
   cout<<setw(2)<<p->key[i];
   p->ptr[i-1]=s1;  //置關(guān)鍵碼k的左邊孩子指針
   p->ptr[i]=s2;    //置關(guān)鍵碼k的右邊孩子指針
   if(++(p->keynum)<m)
     break;//若插入后關(guān)鍵碼個(gè)數(shù)小于m,則完成插入
   else {
    s2=split(p);//分裂*p,將分裂的新結(jié)點(diǎn)作為右邊孩子
    s1=p;       //將分裂后的*p作為左邊孩子
    k=p->key[p->keynum+1];//取出要插入到父結(jié)點(diǎn)的關(guān)鍵碼
    p=p->parent;
   }
  }
  if(p==NULL) //需要產(chǎn)生新的根結(jié)點(diǎn)
  {p=new BTreeNode;//申請(qǐng)新結(jié)點(diǎn)
   p->keynum=1;p->key[1]=k;
   p->ptr[0]=s1;p->ptr[1]=s2;
   return p;}
  else return T;
}
//在B-樹T中刪除關(guān)鍵字的操作,情況(2)
int MoveKey(BTree p)
{BTree b,f=p->parent;     //f指向*p的父結(jié)點(diǎn)
 int i,j;
 for(i=0;f->ptr[i]!=p;i++); //在*f中找出指向*p的指針位置
 if(i>0)                    //若*p有左鄰兄弟
  {b=f->ptr[i-1];           //b指向*p的左鄰兄弟
   if(b->keynum>(m-1)/2)    //左鄰兄弟有多余的關(guān)鍵字
    {for(j=p->keynum;j>=0;j--)//將*P中的關(guān)鍵字和指針后移
      {p->key[j+1]=p->key[j];
       p->ptr[j+1]=p->ptr[j];
      }
     p->key[1]=f->key[i];   //將*f中關(guān)鍵字下移到*p中
     f->key[i]=b->key[b->keynum];//將*b中的最大關(guān)鍵字上移到*f中
     p->ptr[0]=b->ptr[b->keynum];//將*b中的最右邊子樹移到*f的最左邊
     p->keynum++;b->keynum--;    //修改*p和*b中的關(guān)鍵字?jǐn)?shù)目
     return 1;                  //完成關(guān)鍵字移動(dòng),返回
    }
    if(i<f->keynum)             //若*p有右鄰兄弟
    {b=f->ptr[i+1];             //b指向*p的右鄰兄弟
     if(b->keynum>(m-1)/2)       //右鄰兄弟有多余的關(guān)鍵字
      {p->key[p->keynum]=f->key[i+1];//將*f中的關(guān)鍵字下移到*p中
       f->key[i+1]=b->key[1];     //將*b中的最小關(guān)鍵字上移到*f中
       p->ptr[p->keynum]=b->ptr[0];//將*b中的最左邊子樹移到*f的最右邊
       for(j=0;j<b->keynum;j++) //將*b中的關(guān)鍵字和指針前移
       {b->key[j]=b->key[j+1];
        b->ptr[j]=b->ptr[j+1];
       }
       p->keynum++;b->keynum--; //修改*p和*b中的關(guān)鍵字?jǐn)?shù)目
       return 1;               //完成關(guān)鍵字移動(dòng),返回
      }
    }}
  return 0;
}
//結(jié)點(diǎn)*p中包含m個(gè)關(guān)鍵字,從中分裂出一個(gè)新結(jié)點(diǎn),并返回新結(jié)點(diǎn)指針
BTree split(BTree p)
{BTree new1;
 int i,mid,j;
 new1=new BTreeNode;
 mid=(m+1)/2;
 new1->ptr[0]=p->ptr[mid];
 j=1;
 for(i=mid+1;i<=m;i++)
  {new1->key[j]==p->key[i];
   new1->ptr[j++]=p->ptr[i];
  }
 new1->keynum=m-mid;
 p->keynum=mid-1;
 return(new1);
}
//在B-樹T中刪除關(guān)鍵字的操作,情況(3)
BTree merge(BTree p)
{BTree b,f=p->parent;      //f指向*p的父結(jié)點(diǎn)
 int i,j;
 for(i=0;f->ptr[i]!=p;i++) ;//在*f中找出指向*p的指針位置
 if(i>0)                     //若*p有左鄰兄弟
  b=f->ptr[i-1];             //b指向*p的左鄰兄弟
 else {
  b=p;
  p=f->ptr[i+1];
 }           //p指向*p的右鄰兄弟
 b->key[++b->keynum]=f->key[i];//將*f中第i個(gè)關(guān)鍵字合并到*b中
 b->ptr[p->keynum]=p->ptr[0]; //將*p中的最左邊子樹移到*b的最右邊
 for(j=1;j<=b->keynum;j++)    //將*p中的關(guān)鍵字和指針移到*b中
 {b->key[++b->keynum]=p->key[j];
  b->ptr[b->keynum]=p->ptr[j];
 }
 free(p);
 for(j=i+1;j<f->keynum;j++)//將*f中第i個(gè)之后的關(guān)鍵字和指針前移
 {f->key[j-1]=f->key[j];
  f->ptr[j-1]=f->ptr[j];
 }
 f->keynum--;
 return b;
}
//在B-樹T中刪除關(guān)鍵字k,并返回樹根.
BTree Delete(BTree T,KeyType k)
{BTree p,s;
 int i,j;
 i=BTSearch(T,k,&p);    //在樹中搜索k
 if(i==0) return T;     //在B_樹中找不到k,直接返回
 if(p->ptr[i-1])        //當(dāng)p不是葉結(jié)點(diǎn)時(shí)
 {s=p->ptr[i-1];        //取關(guān)鍵字k的左鄰子樹
  while(s->ptr[s->keynum])//在子樹中找包含最大關(guān)鍵字的結(jié)點(diǎn)
   s=s->ptr[s->keynum];
  p->key[i]=s->key[s->keynum];//用子樹中最大關(guān)鍵字取代k
  p=s;i=s->keynum;
 }
 for(j=i+1;j<=p->keynum;j++)//從*p刪除第i個(gè)關(guān)鍵字
  p->key[j-1]=p->key[j];
 p->keynum--;
 while(p->keynum<(m-1)/2&&p->parent)//若*p的關(guān)鍵字?jǐn)?shù)目不夠
 {if(!MoveKey(p)) //按第(2)種情況處理,若不成功
   p=merge(p);    //合并結(jié)點(diǎn)
  p=p->parent;    //檢查父結(jié)點(diǎn)
 }
 if(p==T&&T->keynum==0)//若根結(jié)點(diǎn)中無關(guān)鍵字
 {T=T->ptr[0];//樹根下移一層
  free(p);    //釋放原來根結(jié)點(diǎn)
 }
 return T;
}
//B-樹的相關(guān)操作的測(cè)試
void main()
{cout<<"B_Tree.cpp運(yùn)行結(jié)果:\n";
 KeyType k=10;
 BTree t=new BTreeNode;
 t->keynum=1;t->parent=NULL;
 t->key[1]=1;t->ptr[1]=NULL;
 t->recptr[1]=NULL;
 cout<<"輸出插入關(guān)鍵字:\n";
 for(int i=1;i<k;i++)
  Insert(t,i);
 cout<<endl; 
 for(int i=2;i<k;i+=2)
  if(Delete(t,i)) cout<<"第"<<i<<"個(gè)關(guān)鍵字刪除成功!\n";
 cin.get();
}