【正文】 { //rp指向tp的右兄弟結點 rp=upptr[i+1]。 //修改tp結點 tpkeynum++。 tpkey[n+1]=upkey[i+1]。 tpptr[n+1]=rpptr[0]。 if(tpptr[n+1]!=NULL) tpptr[n+1]parent=tp。 tpkey[n+2]=MAXKEY。 //修改up結點 upkey[i+1]=rpkey[1]。 //修改rp結點 for(j=2。j=rpkeynum。j++){ rpkey[j1]=rpkey[j]。 } for(j=1。j=rpkeynum。j++) rpptr[j1]=rpptr[j]。 rpkey[rpkeynum]=MAXKEY。 rpkeynum。 //刪除成功返回真 return true。 } //tp結點同左兄弟結點lp合并 if(i0){ //lp指向tp結點的左兄弟 lp=upptr[i1]。 //把lp結點中關鍵字個數賦給n1 int n1=lpkeynum。 //修改lp結點 lpkey[n1+1]=upkey[i]。 for(j=1。j=n。j++){ lpkey[n1+1+j]=tpkey[j]。 } for(j=0。j=n。j++){ lpptr[n1+1+j]=tpptr[j]。 if(lpptr[n1+1+j]!=NULL) lpptr[n1+1+j]parent=lp。 } lpkey[n1+n+2]=MAXKEY。 lpkeynum=n1+n+1。 //刪除tp結點 delete tp。 //修改up結點 for(j=i+1。j=upkeynum。j++){ upkey[j1]=upkey[j]。 upptr[j1]=upptr[j]。 } upkey[upkeynum]=MAXKEY。 upkeynum。 //雙親結點成為被刪除關鍵字的節(jié)點，把它賦給tp tp=up。 } //tp結點同右兄弟結點rp合并，此時i必然為0，tp無左兄弟 else{ //rp指向tp結點的右兄弟 rp=upptr[1]。 //把rp結點中關鍵字個數賦n2 int n2=rpkeynum。 //把rp結點中的每個關鍵字后移n+1位置 for(j=n2。j=1。j){ rpkey[n+1+j]=rpkey[j]。 } for(j=n2。j=0。j) rpptr[n+1+j]=rpptr[j]。 //把雙親結點中的一個記錄的索引項下移 rpkey[n+1]=upkey[1]。 //把tp結點的每個關鍵字寫入到rp結點中空出的位置上 for(j=1。j=n。j++){ rpkey[j]=tpkey[j]。 } for(j=0。j=n。j++){ rpptr[j]=tpptr[j]。 if(rpptr[j]!=NULL) rpptr[j]parent=rp。 } //把最大關鍵之放入rp結點的所有關鍵字之后 rpkey[n2+n+2]=MAXKEY。 //修改rp結點的關鍵字個數 rpkeynum=n2+n+1。 //刪除tp節(jié)點 delete tp。 //修改up結點 for(j=2。j=upkeynum。j++){ upkey[j1]=upkey[j]。 } for(j=1。j=upkeynum。j++) upptr[j1]=upptr[j]。 upkey[upkeynum]=MAXKEY。 upkeynum。 tp=up。 } }} void Travel (MBNode MT) //中序遍歷輸出B_樹中的所有關鍵字 { if(MT!=NULL){ Travel (MTptr[0])。 for(int i=1。i=MTkeynum。i++){ coutMTkey[i]39。 39。 Travel (MTptr[i])。 } } } void PreTravel(MBNode MT) //前序遍歷B樹{ if(MT!=NULL) { for(int i=1。i=MTkeynum。i++) coutMTkey[i] 。 PreTravel(MTptr[0])。 for(int j=1。j=MTkeynum。j++) PreTravel (MTptr[j])。 }}void Show(MBNode mt) //按層次打印{ SQ que。 MBNode t。 InitQ(que)。 EnterQ(que,mt)。 while(!EmptyQ(que)) { DeleteQ(que,t)。 for(int i=0。i=tkeynum。i++) { cout|。 if(itkeynum) couttkey[i+1]。 {if(tptr[i]) EnterQ(que,tptr[i])。} } cout|\t。 }}void Clear (MBNode amp。 MT) //清除B_樹，使之變成一棵空樹 { if(MT!=NULL) { for(int i=0。i=MTkeynum。i++) Clear (MTptr[i])。 delete MT。 MT=NULL。 } } void main() { KeyType key。 //用于保存記錄的關鍵字 MBNode mt。 //定義指向B_樹結點的指針 Init (mt)。 //初始化mt bool Tag。 while(1){ cout功能菜單：endl。 cout\tendl。 cout\tendl。 cout\tendl。 cout\tendl。 cout\tendl。 cout\tendl。 cout\tendl。 cout\t，即回收B_樹中的所有結點endl。 cout\tendl。 coutendl。 int m。 cout輸入你的選擇（18）：。 cinm。 switch(m){ case 1: coutendl。 cout從鍵盤上輸入一組關鍵字的個數：。 int i,n。cinn。 cout從鍵盤上輸入n個關鍵字（以空格為界）：endl。 for(i=0。in。i++){ cinkey。 Insert (mt,key)。 } coutendl。 break。 case 2: coutendl。 cout從鍵盤上輸入一個待插入的關鍵字：。 cinkey。 Insert (mt,key)。 coutendl。 break。 case 3: coutendl。 cout從鍵盤上輸入要刪除的關鍵字的個數：。 int m。cinm。 cout從鍵盤上輸入m個關鍵字（以空格為界）：endl。 for(i=0。im。i++){ cinkey。 Tag=Delete(mt,key)。 coutendl。 if(Tag) cout刪除成功！endl。 else cout刪除失?。ndl。 coutendl。 } break。 case 4: coutendl。 cout從鍵盤上輸入一條帶刪除記錄的關鍵字：。 cinkey。 Tag=Delete (mt,key)。 coutendl。 if(Tag) cout刪除成功！endl。 else cout刪除失敗！endl。 break。 case 5: coutendl。 PreTravel(mt)。 coutendl。 break。 case 6: coutendl。 Travel (mt)。 coutendl。 break。 case 7: coutendl。 Show (mt)。 coutendl。 break。 case 8: Clear (mt)。 cout已完成！endl。 break。 default: Clear(mt)。 cout運行程序結束，再見！endlendl。 return。 } } } 五、 程序調試以及運行結果 調試結果及截圖 報告總結報告總結通過對B樹的程序實現，更加熟知了B樹的結構和特性。B樹的整個設計過程遇到了很多問題，主要是對樹的結構方面不了解所產生的邏輯錯誤，經過不斷地查閱資料，解決問題，所建立的樹形可以確認正確，部分功能可以實現，但有些功能仍需要