// bo9-4.cpp 動(dòng)態(tài)查找表(B樹)的基本操作
 Status InitDSTable(BTree &DT)
 { // 操作結(jié)果: 構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT
   DT=NULL;
   return OK;
 }

 void DestroyDSTable(BTree &DT)
 { // 初始條件: 動(dòng)態(tài)查找表DT存在。操作結(jié)果: 銷毀動(dòng)態(tài)查找表DT
   int i;
   if(DT) // 非空樹
   {
     for(i=0;i<=DT->keynum;i++)
       DestroyDSTable(DT->node[i].ptr); // 依次銷毀第i棵子樹
     free(DT); // 釋放根結(jié)點(diǎn)
     DT=NULL; // 空指針賦0
   }
 }

 int Search(BTree p, KeyType K)
 { // 在p->node[1..keynum].key中查找i,使得p->node[i].key≤K＜p->node[i+1].key
   int i=0,j;
   for(j=1;j<=p->keynum;j++)
     if(p->node[j].key<=K)
       i=j;
   return i;
 }

 Result SearchBTree(BTree T, KeyType K)
 { // 在m階B樹T上查找關(guān)鍵字K，返回結(jié)果(pt,i,tag)。若查找成功，則特征值
   // tag=1，指針pt所指結(jié)點(diǎn)中第i個(gè)關(guān)鍵字等于K；否則特征值tag=0，等于K的
   // 關(guān)鍵字應(yīng)插入在指針Pt所指結(jié)點(diǎn)中第i和第i+1個(gè)關(guān)鍵字之間。算法9.13
   BTree p=T,q=NULL; // 初始化，p指向待查結(jié)點(diǎn)，q指向p的雙親
   Status found=FALSE;
   int i=0;
   Result r;
   while(p&&!found)
   {
     i=Search(p,K); // p->node[i].key≤K<p->node[i+1].key
     if(i>0&&p->node[i].key==K) // 找到待查關(guān)鍵字
       found=TRUE;
     else
     {
       q=p;
       p=p->node[i].ptr;
     }
   }
   r.i=i;
   if(found) // 查找成功
   {
     r.pt=p;
     r.tag=1;
   }
   else //  查找不成功，返回K的插入位置信息
   {
     r.pt=q;
     r.tag=0;
   }
   return r;
 }

 void Insert(BTree &q,int i,Record *r,BTree ap)
 { // 將r->key、r和ap分別插入到q->key[i+1]、q->recptr[i+1]和q->ptr[i+1]中
   int j;
   for(j=q->keynum;j>i;j--) // 空出q->node[i+1]
     q->node[j+1]=q->node[j];
   q->node[i+1].key=r->key;
   q->node[i+1].ptr=ap;
   q->node[i+1].recptr=r;
   q->keynum++;
 }

 void split(BTree &q,BTree &ap)
 { // 將結(jié)點(diǎn)q分裂成兩個(gè)結(jié)點(diǎn)，前一半保留，后一半移入新生結(jié)點(diǎn)ap
   int i,s=(m+1)/2;
   ap=(BTree)malloc(sizeof(BTNode)); // 生成新結(jié)點(diǎn)ap
   ap->node[0].ptr=q->node[s].ptr; // 后一半移入ap
   for(i=s+1;i<=m;i++)
   {
     ap->node[i-s]=q->node[i];
     if(ap->node[i-s].ptr)
       ap->node[i-s].ptr->parent=ap;
   }
   ap->keynum=m-s;
   ap->parent=q->parent;
   q->keynum=s-1; // q的前一半保留，修改keynum
 }

 void NewRoot(BTree &T,Record *r,BTree ap)
 { // 生成含信息(T,r,ap)的新的根結(jié)點(diǎn)*T，原T和ap為子樹指針
   BTree p;
   p=(BTree)malloc(sizeof(BTNode));
   p->node[0].ptr=T;
   T=p;
   if(T->node[0].ptr)
     T->node[0].ptr->parent=T;
   T->parent=NULL;
   T->keynum=1;
   T->node[1].key=r->key;
   T->node[1].recptr=r;
   T->node[1].ptr=ap;
   if(T->node[1].ptr)
     T->node[1].ptr->parent=T;
 }

 void InsertBTree(BTree &T,Record *r,BTree q,int i)
 { // 在m階B樹T上結(jié)點(diǎn)*q的key[i]與key[i+1]之間插入關(guān)鍵字K的指針r。若引起
   // 結(jié)點(diǎn)過(guò)大,則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整,使T仍是m階B樹。算法9.14改
   BTree ap=NULL;
   Status finished=FALSE;
   int s;
   Record *rx;
   rx=r;
   while(q&&!finished)
   {
     Insert(q,i,rx,ap); // 將r->key、r和ap分別插入到q->key[i+1]、q->recptr[i+1]和q->ptr[i+1]中
     if(q->keynum<m)
       finished=TRUE; // 插入完成
     else
     { // 分裂結(jié)點(diǎn)*q
       s=(m+1)/2;
       rx=q->node[s].recptr;
       split(q,ap); // 將q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新結(jié)點(diǎn)*ap
       q=q->parent;
       if(q)
         i=Search(q,rx->key); // 在雙親結(jié)點(diǎn)*q中查找rx->key的插入位置
     }
   }
   if(!finished) // T是空樹(參數(shù)q初值為NULL)或根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)*q和*ap
     NewRoot(T,rx,ap); // 生成含信息(T,rx,ap)的新的根結(jié)點(diǎn)*T，原T和ap為子樹指針
 }

 void TraverseDSTable(BTree DT,void(*Visit)(BTNode,int))
 { // 初始條件: 動(dòng)態(tài)查找表DT存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)
   // 操作結(jié)果: 按關(guān)鍵字的順序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit()一次且至多一次
   int i;
   if(DT) // 非空樹
   {
     if(DT->node[0].ptr) // 有第0棵子樹
       TraverseDSTable(DT->node[0].ptr,Visit);
     for(i=1;i<=DT->keynum;i++)
     {
       Visit(*DT,i);
       if(DT->node[i].ptr) // 有第i棵子樹
         TraverseDSTable(DT->node[i].ptr,Visit);
     }
   }
 }