/* bo9-4.c 動態查找表(B樹)的基本操作 */
 Status InitDSTable(BTree *DT)
 { /* 操作結果: 構造一個空的動態查找表DT */
   *DT=NULL;
   return OK;
 }

 void DestroyDSTable(BTree *DT)
 { /* 初始條件: 動態查找表DT存在。操作結果: 銷毀動態查找表DT */
   int i;
   if(*DT) /* 非空樹 */
   {
     for(i=0;i<=(*DT)->keynum;i++)
       DestroyDSTable(&(*DT)->node[i].ptr); /* 依次銷毀第i棵子樹 */
     free(*DT); /* 釋放根結點 */
     *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上查找關鍵字K，返回結果(pt,i,tag)。若查找成功，則特征值 */
   /* tag=1，指針pt所指結點中第i個關鍵字等于K；否則特征值tag=0，等于K的 */
   /* 關鍵字應插入在指針Pt所指結點中第i和第i+1個關鍵字之間。算法9.13 */
   BTree p=T,q=NULL; /* 初始化，p指向待查結點，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) /* 找到待查關鍵字 */
       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)
 { /* 將結點q分裂成兩個結點，前一半保留，后一半移入新生結點ap */
   int i,s=(m+1)/2;
   *ap=(BTree)malloc(sizeof(BTNode)); /* 生成新結點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)的新的根結點*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上結點*q的key[i]與key[i+1]之間插入關鍵字K的指針r。若引起 */
   /* 結點過大,則沿雙親鏈進行必要的結點分裂調整,使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
     { /* 分裂結點*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]移入新結點*ap */
       q=q->parent;
       if(q)
         i=Search(q,rx->key); /* 在雙親結點*q中查找rx->key的插入位置 */
     }
   }
   if(!finished) /* T是空樹(參數q初值為NULL)或根結點已分裂為結點*q和*ap */
     NewRoot(T,rx,ap); /* 生成含信息(T,rx,ap)的新的根結點*T，原T和ap為子樹指針 */
 }

 void TraverseDSTable(BTree DT,void(*Visit)(BTNode,int))
 { /* 初始條件: 動態查找表DT存在，Visit是對結點操作的應用函數 */
   /* 操作結果: 按關鍵字的順序對DT的每個結點調用函數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);
     }
   }
 }