【正文】 B樹的刪除操作 /假若我們刪除關鍵字為非終端節(jié)點中的 Ki,則可以指針 Ai 所指子樹中的最小關鍵字 Y 代替 // Ki,然后在相應的結點中刪去 Y. 下面我們討論刪除最下層非終端節(jié)點中的關鍵字的： // 1. 被刪除的關鍵字所在節(jié)點中的關鍵字的數(shù)目不小于 (m+1)/ // 該關鍵字和相應的指針 Ai，樹的其它部分不變 // 2. 被刪除關鍵字所在節(jié)點中的關鍵字數(shù)目等于 (m+1)/21,而該節(jié)點相 鄰的有兄弟 // 或左兄弟節(jié)點中的關鍵字的個數(shù)大于（ m+1)/2 1,則只需將其兄弟節(jié)點中最?。ɑ蜃畲螅? // 的關鍵字上移至雙親節(jié)點中，而將雙親節(jié)點中小于（或大于）且緊靠上移關鍵字的關鍵字 // 下移至被刪除關鍵字所在的節(jié)點中。 if (q) i = Search(q, x)。 p = q。 split(q, s, ap)。 if (qkeynum m) flag = true。amp。 BTree ap = NULL, p = NULL。T, KeyType key, BTree q, int i) { KeyType x = key。 j++) { if (apptr[j]) apptr[j]parent = ap。 for (int j = 0。 if (q != NULL) qparent = T。 Tptr[0] = q。 Tkeynum = 1。 i++) Tptr[i] = NULL。 for (int i = 0。ap) { T = NULL。T, BTree amp。 apparent = pparent。 apkeynum = pkeynum s。 apptr[k] = pptr[i]。 i = pkeynum。 ap = (BTNode *) malloc( sizeof(BTNode) )。p, int s, BTree amp。 pkeynum++。 pptr[i + 1] = ap。 pptr[k] = pptr[k 1]。 k i + 1。 void insert (BTree amp。 // 在 m 階 B樹 T 上結點 *q 的 key[i]與 key[i+1]之間插入關鍵字 K // 若因起節(jié)點過大，則眼雙親鏈進行必要的節(jié)點分裂調(diào)整 ,保持 T 的特性 //插入操作 // 將 x和 ap 分別插入到 qkey[i+1]和 qptr[i+1] // 這里涉及到數(shù)組元素的移 動的問題，因為這里也是順序結構表示鍵值。 // 2）插入后，該結點的關鍵字個數(shù) n=m， 則需進行結點分裂， // 令 s = m+1/2，在原結點中保留 ( A0, K1, …… , Ks1, As1 )； // (備注：這里的 (m+1)/2 = (m+1) 1 和 m+1 除以 2 上取整同值可證 ) // 新建結點 (As,Ks+1,…… , Kn, An ).將 ( Ks, p ) 插入雙親結點。 } } // while return Result(flag ? p:q, i, flag)。 else { q = p。amp。 !flag) { i = Search (p, key)。 while (p amp。 bool flag = false。 } // for_i return pkeynum。 i = pkeynum。 // 在 m 階 B樹上查找關鍵字 K，返回結果 pt, i, tag // 若查找成功，則特征值 tag = 1，指針 pt 所指結點中第 i個關鍵字等于 K； // 否則特征值 tag = 0，等于 K 的關鍵字應插入在指針 pt 所指結點中第 i和 // 第 i+1 個關鍵字之間 //順序查找 // 在結點 pkey[1..keynum]中查找 ,返回 i： pkey[i] = key pkey[i+1] int Search(BTree amp。 // 定義一個結果全局變量 //B樹的基本操作實現(xiàn) //1B樹查找操作 // 查找過程：從根結點出發(fā)，沿指針搜索結點和在結點內(nèi)進行順序 // (或折半 )查找的兩個過程交叉進行。 tag = c。 // 1:查找成功； 0: 查找失敗 Result(BTNode *a=NULL, int b=0, bool c=0) { // 構造函數(shù) pt = a。 // 指向找到的結點 int i。 // 子樹指針向量 華東交通大學 08 級軟件工程（ 1）班 —— 張志福 5 } BTNode, *BTree。 // 指向雙親節(jié)點的指針 KeyType key[m+1]。 // 定義一個讀者全局變量 //3 B樹 BTree define m 3 // B樹的階，贊設為 3 define KeyType Book // B樹的關鍵字類型為 Book typedef struct BTNode { int keynum。 // 借書的數(shù)量 } book_list。 // 結構體內(nèi)部日期變量 struct Book_Lists { Book book[maxn]。 // 借書日期 int return_date。 // 定義一個書全局變量 //2讀者 Reader struct Reader { int lcid。p) const { // 重載運算符 return isbn。p) const { // 重載運算符 == return == isbn。p) const { // 重載運算符 return isbn。p) { // 重載運算符 = // return = isbn。 // Standing_Stocks int total_stocks。 // 用字符串表示著者 (只有一個著者 ) char book_name[maxc]。 //1書 BOOK struct Book { int isbn。 六、 代碼清單 include include include //存儲結構類型設計 const int maxn = 5。 5. 估計代碼不 會很長一個文件就 OK include include include 三、 流程圖概述 這里的流程圖主要放在兩個方面，一個是 B 樹的主要操作，還有一個就是圖書管理系統(tǒng)的主要操作 BTree的基本操作 查找 SearchBTree 插入 InsertBTree 刪除 DeleteBTree 銷毀： DestroyBTree 輸出 PrintBTree 圖書館里的基本操作 歸還： ReturnBooks 借閱： BorrowBooks 清除庫存： CleanOfStocks 采編入庫： CompileToStocks