#include“BTREE.h“
#include?
#include?
#include??


Status?InitBTree（BTree?&t）{
//初始化B樹?
????t=NULL;
????return?OK;
}


int?SearchBTNode（BTNode?*pKeyType?k）{
//在結點p中查找關鍵字k的插入位置i?
????int?i=0;
????for（i=0;ikeynum&&p->key[i+1]<=k;i++）;
????return?i;
}


Result?SearchBTree（BTree?tKeyType?k）{
/*在樹t上查找關鍵字k返回結果（ptitag）。若查找成功則特征值
tag=1關鍵字k是指針pt所指結點中第i個關鍵字；否則特征值tag=0
關鍵字k的插入位置為pt結點的第i個*/

????BTNode?*p=t*q=NULL;?							//初始化結點p和結點qp指向待查結點q指向p的雙親
????int?found_tag=0;????????????????????????		//設定查找成功與否標志?
	int?i=0;?????????????????
????Result?r;?????????????????????????????			//設定返回的查找結果?
????
????while（p!=NULL&&found_tag==0）{
????????i=SearchBTNode（pk）;??????????????			//在結點p中查找關鍵字k使得p->key[i]<=kkey[i+1]
????????if（i>0&&p->key[i]==k）????		??			//找到待查關鍵字
????????????found_tag=1;????????????????????		//查找成功?
????????else{???????????????????????????????		//查找失敗?
????????????q=p;????????????????????????????
????????????p=p->ptr[i];
????????}
????}

????if（found_tag==1）{???????????????????			//查找成功
????????r.pt=p;
????????r.i=i;
????????r.tag=1;
????}
????else{????????????????????????????				//查找失敗
????????r.pt=q;
		r.i=i;
????????r.tag=0;
????}
????return?r;???????????????????????				//返回關鍵字k的位置（或插入位置）
}


void?InsertBTNode（BTNode?*&pint?iKeyType?kBTNode?*q）{
//將關鍵字k和結點q分別插入到p->key[i+1]和p->ptr[i+1]中
????int?j;
????for（j=p->keynum;j>i;j--）{??						//整體后移空出一個位置
????????p->key[j+1]=p->key[j];
????????p->ptr[j+1]=p->ptr[j];
????}
????p->key[i+1]=k;
????p->ptr[i+1]=q;
????if（q!=NULL）?
		q->parent=p;
????p->keynum++;
}


void?SplitBTNode（BTNode?*&pBTNode?*&q）{
//將結點p分裂成兩個結點前一半保留后一半移入結點q
????int?i;
	int?s=（m+1）/2;
????q=（BTNode?*）malloc（sizeof（BTNode））;????			//給結點q分配空間
	?
????q->ptr[0]=p->ptr[s];???????????????????			//后一半移入結點q
????for（i=s+1;i<=m;i++）{
????????q->key[i-s]=p->key[i];
????????q->ptr[i-s]=p->ptr[i];
????}
????q->keynum=p->keynum-s;????????????????
????q->parent=p->parent;
????for（i=0;i<=p->keynum-s;i++）?					//修改雙親指針?
????????if（q->ptr[i]!=NULL）?
			q->ptr[i]->parent=q;
????p->keynum=s-1;?????????????????					//結點p的前一半保留修改結點p的keynum
}


void?NewRoot（BTNode?*&tKeyType?kBTNode?*pBTNode?*q）{
//生成新的根結點t原p和q為子樹指針
????t=（BTNode?*）malloc（sizeof（BTNode））;???????		//分配空間?
????t->keynum=1;
????t->ptr[0]=p;
????t->ptr[1]=q;
????t->key[1]=k;
????if（p!=NULL）?									//調整結點p和結點q的雙親指針?
		p->parent=t;
????if（q!=NULL）?
		q->parent=t;
????t->parent=NULL;
}


void?InsertBTree（BTree?&tint?iKeyType?kBTNode?*p）{
/*在樹t上結點q的key[i]與key[i+1]之間插入關鍵字k。若引起
結點過大則沿雙親鏈進行必要的結點分裂調整使t仍是B樹*/
????BTNode?*q;
????int?finish_tagnewroot_tags;???????????????????//設定需要新結點標志和插入完成標志?
????KeyType?x;
????if（p==NULL）??????????????????????				//t是空樹
????????NewRoot（tkNULLNULL）;?????????			//生成僅含關鍵字k的根結點t
????else{
????????x=k;
????????q=NULL;
????????finish_tag=0;???????
????????newroot_tag=0;
????????while（finis

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-01-07?01:39??BTree\
?????目錄???????????0??2017-12-28?00:12??BTree\.git\
?????文件???????????6??2017-12-25?12:00??BTree\.git\COMMIT_EDITMSG
?????文件?????????307??2017-12-25?12:01??BTree\.git\config
?????文件??????????73??2017-12-25?12:00??BTree\.git\description
?????文件??????????23??2017-12-25?12:00??BTree\.git\HEAD
?????目錄???????????0??2017-12-28?00:12??BTree\.git\hooks\
?????文件?????????478??2017-12-25?12:00??BTree\.git\hooks\applypatch-msg.sample
?????文件?????????896??2017-12-25?12:00??BTree\.git\hooks\commit-msg.sample
?????文件?????????189??2017-12-25?12:00??BTree\.git\hooks\post-update.sample
?????文件?????????424??2017-12-25?12:00??BTree\.git\hooks\pre-applypatch.sample
?????文件????????1642??2017-12-25?12:00??BTree\.git\hooks\pre-commit.sample
?????文件????????1348??2017-12-25?12:00??BTree\.git\hooks\pre-push.sample
?????文件????????4898??2017-12-25?12:00??BTree\.git\hooks\pre-rebase.sample
?????文件?????????544??2017-12-25?12:00??BTree\.git\hooks\pre-receive.sample
?????文件????????1492??2017-12-25?12:00??BTree\.git\hooks\prepare-commit-msg.sample
?????文件????????3610??2017-12-25?12:00??BTree\.git\hooks\update.sample
?????文件?????????361??2017-12-25?12:00??BTree\.git\index
?????目錄???????????0??2017-12-28?00:12??BTree\.git\info\
?????文件?????????240??2017-12-25?12:00??BTree\.git\info\exclude
?????目錄???????????0??2017-12-28?00:12??BTree\.git\logs\
?????文件?????????154??2017-12-25?12:00??BTree\.git\logs\HEAD
?????目錄???????????0??2017-12-28?00:12??BTree\.git\logs\refs\
?????目錄???????????0??2017-12-28?00:12??BTree\.git\logs\refs\heads\
?????文件?????????154??2017-12-25?12:00??BTree\.git\logs\refs\heads\master
?????目錄???????????0??2017-12-28?00:12??BTree\.git\logs\refs\remotes\
?????目錄???????????0??2017-12-28?00:12??BTree\.git\logs\refs\remotes\origin\
?????文件?????????145??2017-12-25?12:01??BTree\.git\logs\refs\remotes\origin\master
?????目錄???????????0??2017-12-28?00:12??BTree\.git\objects\
?????目錄???????????0??2017-12-28?00:12??BTree\.git\objects\47\
?????文件?????????139??2017-12-25?12:00??BTree\.git\objects\47\2915c74ddb456a6d6c9bb344b4e7b1f5b24a28
............此處省略24個文件信息