本文是針對[數據結構基礎系列(8)：查找]的實踐。

【項目 - B-樹的基本操作】
實現B-樹的基本操作。基于序列{4, 9, 0, 1, 8, 6, 3, 5, 2, 7}完成測試。
（1）創建對應的3階B-樹b，用括號法輸出b樹。
（2）從b中分別刪除關鍵字為8和1的節點，用括號法輸出刪除節點后的b樹。
[參考解答]

#include <stdio.h> #include <malloc.h> #define MAXM 10 //定義B-樹的最大的階數 typedef int KeyType; //KeyType為關鍵字類型 typedef struct node //B-樹結點類型定義 {int keynum; //結點當前擁有的關鍵字的個數KeyType key[MAXM]; //key[1..keynum]存放關鍵字,key[0]不用struct node *parent; //雙親結點指針struct node *ptr[MAXM]; //孩子結點指針數組ptr[0..keynum] } BTNode; typedef struct //B-樹的查找結果類型 {BTNode *pt; //指向找到的結點int i; //1..m,在結點中的關鍵字序號int tag; //1:查找成功,O:查找失敗 } Result; int m; //m階B-樹,為全局變量 int Max; //m階B-樹中每個結點的至多關鍵字個數,Max=m-1 int Min; //m階B-樹中非葉子結點的至少關鍵字個數,Min=(m-1)/2 int Search(BTNode *p,KeyType k) {//在p->key[1..keynum]中查找i,使得p->key[i]<=k<p->key[i+1]int i=0;for(i=0; i<p->keynum && p->key[i+1]<=k; i++);return i; } Result SearchBTree(BTNode *t,KeyType k) {/*在m階t樹t上查找關鍵字k,返回結果(pt,i,tag)。若查找成功,則特征值tag=1,指針pt所指結點中第i個關鍵字等于k；否則特征值tag=0,等于k的關鍵字應插入在指針Pt所指結點中第i和第i+1個關鍵字之間*/BTNode *p=t,*q=NULL; //初始化,p指向待查結點,q指向p的雙親int found=0,i=0;Result r;while (p!=NULL && found==0){i=Search(p,k); //在p->key[1..keynum]中查找i,使得p->key[i]<=k<p->key[i+1]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的位置(或插入位置) } void Insert(BTNode *&q,int i,KeyType x,BTNode *ap) {//將x和ap分別插入到q->key[i+1]和q->ptr[i+1]中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++; } void Split(BTNode *&q,BTNode *&ap) {//將結點q分裂成兩個結點,前一半保留,后一半移入新生結點apint i,s=(m+1)/2;ap=(BTNode *)malloc(sizeof(BTNode)); //生成新結點*apap->ptr[0]=q->ptr[s]; //后一半移入apfor (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 } void NewRoot(BTNode *&t,BTNode *p,KeyType x,BTNode *ap) {//生成含信息(T,x,ap)的新的根結點*t,原t和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; } void InsertBTree(BTNode *&t, KeyType k, BTNode *q, int i) {/*在m階t樹t上結點*q的key[i]與key[i+1]之間插入關鍵字k。若引起結點過大,則沿雙親鏈進行必要的結點分裂調整,使t仍是m階t樹。*/BTNode *ap;int finished,needNewRoot,s;KeyType x;if (q==NULL) //t是空樹(參數q初值為NULL)NewRoot(t,NULL,k,NULL); //生成僅含關鍵字k的根結點*telse{x=k;ap=NULL;finished=needNewRoot=0;while (needNewRoot==0 && finished==0){Insert(q,i,x,ap); //將x和ap分別插入到q->key[i+1]和q->ptr[i+1]if (q->keynum<=Max) finished=1; //插入完成else{//分裂結點*q,將q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新結點*aps=(m+1)/2;Split(q,ap);x=q->key[s];if (q->parent) //在雙親結點*q中查找x的插入位置{q=q->parent;i=Search(q, x);}else needNewRoot=1;}}if (needNewRoot==1) //根結點已分裂為結點*q和*apNewRoot(t,q,x,ap); //生成新根結點*t,q和ap為子樹指針} } void DispBTree(BTNode *t) //以括號表示法輸出B-樹 {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(")"); //至少有一個子樹時輸出")"號}} } void Remove(BTNode *p,int i) //從*p結點刪除key[i]和它的孩子指針ptr[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--; } void Successor(BTNode *p,int i) //查找被刪關鍵字p->key[i](在非葉子結點中)的替代葉子結點 {BTNode *q;for (q=p->ptr[i]; q->ptr[0]!=NULL; q=q->ptr[0]);p->key[i]=q->key[1]; //復制關鍵字值 } 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--; } 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];} } void Combine(BTNode *p,int i) //將三個結點合并到一個結點中 {int c;BTNode *q=p->ptr[i]; //指向右結點,它將被置空和刪除BTNode *l=p->ptr[i-1];l->keynum++; //l指向左結點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); //釋放空右結點的空間 } void Restore(BTNode *p,int i) //關鍵字刪除后,調整B-樹,找到一個關鍵字將其插入到p->ptr[i]中 {if (i==0) //為最左邊關鍵字的情況if (p->ptr[1]->keynum>Min)MoveLeft(p,1);elseCombine(p,1);else if (i==p->keynum) //為最右邊關鍵字的情況if (p->ptr[i-1]->keynum>Min)MoveRight(p,i);elseCombine(p,i);else if (p->ptr[i-1]->keynum>Min) //為其他情況MoveRight(p,i);else if (p->ptr[i+1]->keynum>Min)MoveLeft(p,i+1);elseCombine(p,i); } int SearchNode(KeyType k,BTNode *p,int &i) //在結點p中找關鍵字為k的位置i,成功時返回1,否則返回0 {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]);} } int RecDelete(KeyType k,BTNode *p) //查找并刪除關鍵字k {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]在葉子結點中}elseRemove(p,i); //從*p結點中位置i處刪除關鍵字}elsefound=RecDelete(k,p->ptr[i]); //沿孩子結點遞歸查找并刪除關鍵字kif (p->ptr[i]!=NULL)if (p->ptr[i]->keynum<Min) //刪除后關鍵字個數小于MINRestore(p,i);return found;} } void DeleteBTree(KeyType k,BTNode *&root) //從B-樹root中刪除關鍵字k,若在一個結點中刪除指定的關鍵字,不再有其他關鍵字,則刪除該結點 {BTNode *p; //用于釋放一個空的rootif (RecDelete(k,root)==0)printf(" 關鍵字%d不在B-樹中\n",k);else if (root->keynum==0){p=root;root=root->ptr[0];free(p);} } int 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("創建一棵%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(" 結果B-樹: ");DispBTree(t);printf("\n");printf("刪除操作:\n");k=8;DeleteBTree(k,t);printf(" 刪除%d: ",k);printf("B-樹: ");DispBTree(t);printf("\n");k=1;DeleteBTree(k,t);printf(" 刪除%d: ",k);printf("B-樹: ");DispBTree(t);printf("\n");return 0; }

總結

以上是生活随笔為你收集整理的数据结构实践——B-树的基本操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。