import?java.util.*;


//////?DisposeRoot?///////中的key參數有些問題

public?class?BTree?{
??//用于記錄每個節點中的鍵值數量
??public?int?keyAmount;
??//樹的根節點
??public?Node?root;

??public?BTree（int?keyAmount）?{
????this.keyAmount?=?keyAmount;
????this.root?=?new?Node（keyAmount）;
??}



??//在B樹中插入葉節點/////////////////////////////////////////////////////////////
??public?void?insert（long?keyobject?pointer）
??{
????//找到應該插入的節點，即找到葉子節點
????Node?theNode?=?search（keyroot）;

????//在葉節點中找到空閑空間，有的話就把鍵放在那里
????if（?!isFull（theNode）?）
????{
??????putKeyToNode（keypointertheNode）;
????}else{
??????//如果在適當的葉節點沒有空間，就把該葉節點分裂成兩個，并正確分配鍵值
??????Node?newNode?=?separateLeaf（keypointertheNode）;
??????//如果分裂的是根節點，就新建一個新的根節點將新建的節點作為他的根節點
	??//原來的根節點，和分裂的節點分別作為新根節點的左右孩子，此時新根只有一個元素
??????if（?isRoot（theNode）?）
??????{
????????DisposeRoot（theNodenewNodenewNode.keys[0]）;
??????}else{
????????//將新建立的節點的指針插入到上層節點
????????insertToInnerNode（theNode.parentnewNodenewNode.keys[0]）;
??????}
????}
??}




??//用于尋找鍵值key所在的或key應該插入的節點
??//key為鍵值curNode為當前節點--一般從root節點開始
??public?Node?search（long?keyNode?curNode）
??{
????if?（isLeaf（curNode））
??????return?curNode;

????for?（int?i?=?0;?i?????{
????????if?（key???????????return?search（key?（Node）?curNode.pointer[i]）;
????????else?if?（key?>=?curNode.keys[i]）?{
??????????if?（i?==?curNode.keyAmount?-?1）?//如果后面沒有值
??????????{
????????????//如果key比最后一個鍵值大則給出最后一個指針進行遞歸查詢
????????????return?search（key（Node）?curNode.pointer[curNode.keyAmount]）;
??????????}
??????????else?{
????????????if?（key???????????????return?search（key?（Node）?curNode.pointer[i?+?1]）;
??????????}
????????}
????}
????//永遠也不會到達這里
????return?null;
??}




	//把鍵值放到葉節點中--這個函數不進行越界檢查////////////////////////////////////////
??private?void?putKeyToNode（long?keyobject?pointerNode?theNode）
??{
????int?position?=?getInsertPosition（keytheNode）;
????//進行搬遷動作--------葉節點的搬遷
????if（?isLeaf（theNode）?）
????{
????????if（theNode.keyAmount?<=?position）
????????{
???????????theNode.add（keypointer）;
???????????return;
????????}
????????else{
????????????for?（int?j?=?theNode.keyAmount?-?1;?j?>=?position;?j--）?{
??????????????theNode.keys[j?+?1]?=?theNode.keys[j];
??????????????theNode.pointer[j?+?1]?=?theNode.pointer[j];
????????????}
????????????theNode.keys[position]?=?key;
????????????theNode.pointer[position]?=?pointer;
????????}
?????}else{
??????????//內部節點的搬遷----有一定的插入策略：
??????????//指針的插入比數據的插入多出一位
??????????for?（int?j?=?theNode.keyAmount?-?1;?j?>=?position;?j--）?{
????????????theNode.keys[j?+?1]?=?theNode.keys[j];
????????????theNode.pointer[j?+?2]?=?theNode.pointer[j+1];
??????????}
??????????theNode.keys[position]?=?key;
??????????theNode.pointer[position+1]?=?pointer;
????????}
????//鍵值數量加1
????theNode.keyAmount++;
??}



?//將對應的葉節點進行分裂并正確分配鍵值，返回新建的節點///////////////////////////////
??private?Node?separateLeaf

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????9016??2011-11-07?20:53??BTree.java

?????文件????????972??2011-11-07?20:41??Node.java

?????文件???????1424??2011-11-07?20:21??Test.java

?????文件???????1623??2011-11-07?11:07??TreePrinter.java

-----------?---------??----------?-----??----

????????????????13035????????????????????4