#include<stdio.h>
#include<malloc.h>
#define MAXM 10  //B-樹最大階數

typedef int KeyType;  //keyType是關鍵字類型
typedef struct node
{
 int keynum;  //當前擁有關鍵字個數
 KeyType key[MAXM];  //key[1,2,...,keynum]存放關鍵字的個數
 struct node *parent;  //雙親指針節點
 struct node *ptr[MAXM];  //孩子節點指針數組ptr[0...keynum]
}BTNode;

typedef struct  //B-樹的查找結果類型
{
 BTNode *pt;  //指向找到的節點
 int i;  //i...m在節點中的關鍵字序號
 int tag;  //1：查找成功 0：查找失敗
}Result;

int m;  //m階B-樹作為全局變量
int Max;  //m階B-樹中每個節點的最多關鍵字個數，Max=m-1
int Min;  //m階B-樹中非葉子節點的最少關鍵字個數，Min=（m-1）/2

/*1.在p->key[1...keynum]中查找i，使得p->key[i]<=k<p->key[i+1]*/
int Search(BTNode *p,KeyType k)
{
 for(int i=0; i<p->keynum && p->key[i+1]<=k; i++);
 return i;
}

/*
2.在m階t樹t上查找關鍵字k，返回結果（pt，i，tag）。
若查找成功，則特征值tag=1，指針pt所指節點中第i個關鍵字=k；
否則特征值tag=0，等于k的光劍子應該插入在指針pt所指節點中第i和第i+1個關鍵字之間
*/
Result SearchBTree(BTNode *t,KeyType k)
{
 BTNode *p=t,*q=NULL;  //初始化，p指向帶查看節點，q指向p的雙親
 int found=0,i=0;
 Result r;
 while(p!=NULL && found==0)
 {
  /*在p->key[i..keynum]中查找i，使得p->key[i]<=k<p->key[i+1]*/
  i=Search(p,k);
  if(i>0 && p->key[i]==k)
   found=1;
  else
  {
   q=p;
   p=p->ptr[i];
  }
 }

 r.i=i;
 if(found==1)  //查找成功
 {
  r.pt=p;
  r.tag=1;
 }
 else  //查找失敗，返回k的插入位置信息
 {
  r.pt=q;
  r.tag=0;
 }
 return r;  //返回k的位置，或者插入的位置
}

/*3.將x和ap分別插入到q->key[i+1]和q->ptr[i+1]中*/
void Insert(BTNode * &q,int i,KeyType x,BTNode *ap)
{
 int j;
 for(j=q->keynum; j>i; j--)  //空出一個位置
 {
  q->key[j+1]=q->key[j];
  q->ptr[j+1]=q->ptr[j];
 }
 q->key[i+1]=x;
 q->ptr[i+1]=ap;
 if(ap!=NULL)
  ap->parent=q;
 q->keynum++;
}

/*4.將節點q分裂成兩個節點，前一半保留，后一半移入新生節點ap*/
void Split(BTNode * &q,BTNode * &ap)
{
 int i,s=(m+1)/2;
 ap=(BTNode *)malloc(sizeof(BTNode));  //生成新節點ap
 ap->ptr[0]=q->ptr[s];  //后一半移入ap
 for(i=s+1; i<=m; i++)
 {
  ap->key[i-s]=q->key[i];
  ap->ptr[i-s]=q->ptr[i];
  if(ap->ptr[i-s]!=NULL)
   ap->ptr[i-s]->parent=ap;
 }
 ap->keynum=q->keynum-s;
 ap->parent=q->parent;
 for(i=0; i<=q->keynum-s; i++)  //修改指向雙親節點的指針
  if(ap->ptr[i]!=NULL)
   ap->ptr[i]->parent=ap;
  q->keynum=s-1;  //q的前一半保留，修改keynum
}

/*5.生成含信息（t，x，ap）的新的根結點*t，原t和ap為子樹指針*/
void NewRoot(BTNode * &t,BTNode *p,KeyType x,BTNode *ap)
{
 t=(BTNode *)malloc(sizeof(BTNode));
 t->keynum=1; t->ptr[0]=p; t->ptr[1]=ap; t->key[1]=x;
 if(p!=NULL) p->parent=t;
 if(ap!=NULL) ap->parent=t;
 t->parent=NULL;
}

/*
6.在m階t樹t上結點*q的key[i]與key[i+1]之間插入關鍵字k。
若引起結點過大，則沿雙親鏈進行必要的節點分裂調整，使得t荏苒是m階t樹
*/
void InsertBTree(BTNode * &t,KeyType k,BTNode *q,int i)
{
 BTNode *ap;
 int finished,needNewRoot,s;
 KeyType x;
 if(q==NULL)  //t是空樹，參數q的初值為NULL
  NewRoot(t,NULL,k,NULL);  //生成僅含關鍵字k的根節點*t
 else
 {
  x=k; ap=NULL; finished=needNewRoot=0;
  while(needNewRoot==0 && finished==0)
  {
   /*將x和ap分別插入到q->key[i+1]he q->ptr[i+1]*/
   Insert(q,i,x,ap);
   if(q->keynum<=Max) finished=1;  //插入完成
   else
   {
    /*
    分裂節點*p，將q->key[s+1..m]，q->ptr[s..m]
        和q->recptr[s+1..m]移入新結點*ap
    */
    s=(m+1)/2;
    Split(q,ap);
    x=q->key[s];
    if(q->parent)  //在雙親節點*p中查找x的插入位置
    {
     q=q->parent;
     i=Search(q,x);
    }
    else
     needNewRoot=1;
   }
  }
  if(needNewRoot==1)  //根結點已經分裂成為結點*q和*ap
   NewRoot(t,q,x,ap);  //生成新節點*t，q和ap為子樹指針
 }
}

/*7以括號表示法輸出B-樹*/
void DispBTree(BTNode *t)
{
 int i;
 if(t!=NULL)
 {
  printf("[");  //輸出當前節點關鍵字
  for(i=1; i<t->keynum; i++)
   printf("%d",t->key[i]);
  printf("%d",t->key[i]);
  printf("]");
  if(t->keynum>0)
  {
   if(t->ptr[0]!=0) printf("(");  //至少有一個子樹時輸出“(”號
   for(i=0; i<t->keynum; i++)  //對每個子樹進行遞歸調用
   {
    DispBTree(t->ptr[i]);
    if(t->ptr[i+1]!=NULL) printf(",");
   }
   DispBTree(t->ptr[t->keynum]);
   if(t->ptr[0]!=0) printf(")");  //至少有一個子樹時輸出")"號
  }
 }
}

/*8.從結點p刪除key[i]和它的孩子指針ptr[i]*/
void Remove(BTNode *p,int i)
{
 int j;
 for(j=i+1; j<=p->keynum; j++)  //前移刪除key[i]和ptr[i]
 {
  p->key[j-1]=p->key[j];
  p->ptr[j-1]=p->ptr[j];
 }
 p->keynum--;
}

/*9.查找被刪除關鍵字p->key[i](在非葉子結點中)的替代葉子結點*/
void Successor(BTNode *p,int i)
{
 BTNode *q;
 for(q=p->ptr[i]; q->ptr[0]!=NULL; q=q->ptr[0]);
 p->key[i]=q->key[1];  //復制關鍵字值
}

/*10.把一個關鍵字移動到右兄弟中*/
void MoveRight(BTNode *p,int i)
{
 int c;
 BTNode *t=p->ptr[i];
 for(c=t->keynum; c>0; c--)
 {
  t->key[c+1]=t->key[c];
  t->ptr[c+1]=t->ptr[c];
 }
 t->ptr[1]=t->ptr[0];  //從雙親結點移動關鍵字到右兄弟中
 t->keynum++;
 t->key[1]=p->key[i];
 t=p->ptr[i-1];  //將左兄弟中最后一個關鍵字移動到雙親節點中
 p->key[i]=t->key[t->keynum];
 p->ptr[i]->ptr[0]=t->ptr[t->keynum];
 t->keynum--;
}

/*11.把一個關鍵字移動的左兄弟中*/
void MoveLeft(BTNode *p,int i)
{
 int c;
 BTNode *t;
 t=p->ptr[i-1];  //把雙親結點中的關鍵字移動到雙親節點中
 t->keynum++;
 t->key[t->keynum]=p->key[i];
 t->ptr[t->keynum]=p->ptr[i]->ptr[0];
 t=p->ptr[i];  //把右兄弟中的關鍵字移動到雙親結點中
 p->key[i]=t->key[1];
 p->ptr[0]=t->ptr[1];
 t->keynum--;
 for(c=1; c<=t->keynum; c++)  //將右兄弟中的所有關鍵字移動一位
 {
  t->key[c]=t->key[c+1];
  t->ptr[c]=t->ptr[c+1];
 }
}

/*12.將3個結點合并到一個節點中*/
void Combine(BTNode *p,int i)
{
 int c;
 BTNode *q=p->ptr[i];  //指向右結點，它將被置空和刪除
 BTNode *l=p->ptr[i-1];
 l->keynum++;
 l->key[l->keynum]=p->key[i];
 l->ptr[l->keynum]=q->ptr[0];
 for(c=1; c<=q->keynum; c++)  //插入右結點中的所有關鍵字
 {
  l->keynum++;
  l->key[l->keynum]=q->key[c];
  l->ptr[l->keynum]=q->ptr[c];
 }
 for(c=i; c<p->keynum; c++)  //刪除父結點的所有關鍵字
 {
  p->key[c]=p->key[c+1];
  p->ptr[c]=p->ptr[c+1];
 }
 p->keynum--;
 free(q);  //釋放空右結點的空間
}

/*13.關鍵字刪除以后，調整B-樹，找到一個關鍵字將其插入到p->ptr[i]中*/
void Restore(BTNode *p,int i)
{
 if(i==0)  //在最左邊關鍵字的情況
  if(p->ptr[1]->keynum>Min)
   MoveLeft(p,1);
  else
   Combine(p,1);
 else if(i==p->keynum)  //最右邊關鍵字情況
  if(p->ptr[i-1]->keynum>Min)
   MoveRight(p,i);
  else
   Combine(p,i);
 else if(p->ptr[i-1]->keynum>Min)  //其它情況
  MoveLeft(p,i);
 else if(p->ptr[i+1]->keynum>Min)
  MoveLeft(p,i+1);
 else
  Combine(p,i);
}

/*14.在結點p中找關鍵字為k的位置i，成功時返回1，失敗返回0*/
int SearchNode(KeyType k,BTNode *p,int &i)
{
 if(k<p->key[1])  //k小于*p結點的最小關鍵字時返回0
 {
  i=0;
  return 0;
 }
 else  //在*p結點中查找
 {
  i=p->keynum;
  while(k<p->key[i] && i>1)
   i--;
  return(k==p->key[i]);
 }
}

/*15.查找并刪除關鍵字k*/
int RecDelete(KeyType k,BTNode *p)
{
 int i;
 int found;
 if(p==NULL)
  return 0;
 else
 {
  if((found=SearchNode(k,p,i)==1))  //查找關鍵字k
  {
   if(p->ptr[i-1]!=NULL)  //若為非葉子結點
   {
    Successor(p,i);  //由其它后繼代替它
    RecDelete(p->key[i],p->ptr[i]);  //p->key[i]在葉子結點中
   }
   else
    Remove(p,i);
  }
  else
   found=RecDelete(k,p->ptr[i]);  //沿孩子結點遞歸查找并刪除關鍵字k
  if(p->ptr[i]!=NULL)
   if(p->ptr[i]->keynum<Min)  //刪除后關鍵字個數小于Min
     Restore(p,i);
   return found;
 }
}

/*16.從B-樹root中刪除關鍵字k，若在一個結點中刪除指定的關鍵字，不再有其它關鍵字，則刪除該結點*/
void DeleteBTree(KeyType k,BTNode * &root)
{
 BTNode *p;  //用于釋放一個空的root
 if(RecDelete(k,root)==0)
  printf("  關鍵字 %d 不在B-樹中\n",k);
 else if(root->keynum==0)
 {
  p=root;
  root=root->ptr[0];
  free(p);
 }
}

void main()
{
 BTNode *t=NULL;
 Result s;
 int j,n=10;
 KeyType a[]={4,9,0,1,8,6,3,5,2,7},k;
 m=3;  //3階B+樹
 Max=m-1;
 Min=(m-1)/2;
 printf("\n創建一顆 %d 階B-樹:\n",m);
 for(j=0; j<n; j++)  //創建一顆3階B-樹t
 {
  s=SearchBTree(t,a[j]);
  if(s.tag==0)
   InsertBTree(t,a[j],s.pt,s.i);
  printf("第 %d 步，插入 %d:",j+1,a[j]);
  DispBTree(t);
  printf("\n");
 }

 printf("刪除操作:\n");
 k=8;
 DeleteBTree(k,t);
 printf("刪除 %d ",k);
 DispBTree(t);
 printf("\n");
 k=1;
 DeleteBTree(k,t);
 printf("刪除 %d ",k);
 DispBTree(t);
 printf("\n\n");

}