#include<iostream.h>
#include<stdlib.h>
#include<math.h>


#include"B_Tree.h"


//初始化B_樹，即把樹根指針置空
void InitMBTree(MBNode *& MT)
{
	MT=NULL;
}

//判斷B_樹是否為空
bool MBTreeEmpty(MBNode * MT)
{
	return MT==NULL;
}

//從B_樹mt上查找關鍵字為K的插入位置，由Tp帶回指向K所在結點的指針，
//由Pos帶回插入K在Tp結點中的下標位置
void FindInsert(MBNode* mt,KeyType K,MBNode*& Tp,int& Pos)
{
	int i;
	MBNode * p;
	//查找K應該插入的結點和該結點中的下標位置
	while(mt!=NULL){
		i=1;
		while(K>mt->key[i]) i++;
		if(K==mt->key[i]){Tp=NULL;return;}//關鍵字已經存在
		else {
			p=mt;
			mt=mt->ptr[i-1];
		}
	}
	//把K應插入的結點指針賦給Tp，下標位置賦給Pos
	Tp=p;Pos=i;
}

//向樹根指針為MT的B樹插入關鍵字
void InsertMBTree(MBNode*& MT,KeyType K)
{
    //當B樹為空時的處理情況
	if(MT==NULL){                
		MT=new MBNode;
		MT->keynum=1;  
		MT->parent=NULL;
		MT->key[1]=K;  
		MT->key[2]=MAXKEY;
		MT->ptr[0]=MT->ptr[1]=NULL;
		return;
	}
	MBNode *tp;int pos;
	//從B樹上查找插入位置
	FindInsert(MT,K,tp,pos);
	//關鍵字已存在，無需插入
	if(tp==NULL){
		cout<<"關鍵字"<<K<<"在B_樹上已經存在，不需插入！"<<endl;
		return ;
	}
    //向非空的B樹中插入
	MBNode*ap=NULL;                 //ap的初值為空
	while(1){
		int i,n;
		n=tp->keynum;
		//從最后插入位置的所有關鍵字均后移一個位置
		for(i=n;i>=pos;i--){
			tp->key[i+1]=tp->key[i];
			tp->ptr[i+1]=tp->ptr[i];
		}
		//把一個插入關鍵字放入tp結點的pos下標位置
		tp->key[pos]=K;  
		tp->ptr[pos]=ap;
		//使p結點的關鍵字的個數增1
		tp->keynum++;
		//若插入后結點中關鍵字個數超過所允許的最大值，則完成插入
		if(n+1<=m-1){
			tp->key[n+2]=MAXKEY; 
			return;
		}
		//計算出m/2的向上取整值
		int j;
		j=int(ceil(double(m)/2));
		//建立新分裂的結點，該結點含有m-j個關鍵字
		ap=new MBNode;
		ap->keynum=m-j;  ap->parent=tp->parent;
		//復制關鍵字和記錄位置
		for(i=1;i<=ap->keynum;i++){
			ap->key[i]=tp->key[j+i];
		}
		//復制指針
		for(i=0;i<=ap->keynum;i++){
			ap->ptr[i]=tp->ptr[j+i];
			if(ap->ptr[i]!=NULL)  ap->ptr[i]->parent=ap;
		}
		ap->key[m-j+1]=MAXKEY;        //最大值放入所有關鍵字后
		tp->keynum=j-1;                //修改tp結點中的關鍵字個數
		K=tp->key[j];   //建立新的待向雙親結點插入關鍵字
		tp->key[j]=MAXKEY;                 //在tp結點的所有關鍵字最后放入最大關鍵字
		//若條件成立，則需建立新的樹根結點，所以退出循環(huán)
		if(tp->parent==NULL) break;
		//求出新的關鍵字在雙親結點的插入位置
		tp=tp->parent;
		i=1;
		while(K>tp->key[i]) i++;
		pos=i;
	}
	//建立新的樹根結點
	MT=new MBNode;
	MT->keynum=1;  
	MT->parent=NULL;
	MT->key[1]=K;  MT->key[2]=MAXKEY;
	MT->ptr[0]=tp; MT->ptr[1]=ap;
	tp->parent=ap->parent=MT;
}


//從mt樹上查找待刪除的關鍵字所在的結點，若為非葉子結點則調換到葉子結點上
//由Tp指針指向該結點
void FindDelete(MBNode* mt,KeyType K,MBNode *& Tp)
{
	int i;
	//從樹根結點起查找待刪除關鍵字K所在的節(jié)點
	while(mt!=NULL){
		i=1;
		while(K>mt->key[i])  i++;
		if(K==mt->key[i])  break;
		mt=mt->ptr[i-1];
	}
	//若mt樹中不存在關鍵字K則Tp返回空值
	if(mt==NULL){Tp=NULL;return;}
	//若關鍵字K所在的結點為葉子，則刪除它后由Tp帶回結點地址
	if(mt->ptr[i]==NULL){
		int n=mt->keynum;
		for(int j=i+1;j<=n;j++){
			mt->key[j-1]=mt->key[j];
		}
		mt->keynum--;
		mt->key[n]=MAXKEY;
		Tp=mt;
		return;
	}
	//在非葉子結點上查找成功，則繼續(xù)查找該結點的中序前驅結點和
	//中序前驅關鍵字，作對調和刪除后，有Tp帶回葉子結點的地址
	Tp=mt;                //用Tp暫存K所在非葉子結點的地址
	MBNode* q=mt;
	mt=mt->ptr[i-1];      //用q作為mt的前驅結點指針
	while(mt!=NULL){
		q=mt;
		mt=mt->ptr[mt->keynum];
	}
	Tp->key[i]=q->key[q->keynum];    //把中序前驅關鍵字賦給被刪除關鍵字的位置
	q->key[q->keynum]=MAXKEY;  //把最大關鍵字放入q結點的最后位置
	q->keynum--;     //q結點中關鍵字個數減1
	Tp=q;   //由Tp帶回被刪除關鍵字的葉子結點
	return;
}

//從B_樹中刪除關鍵字K，刪除成功返回真，否則返回假
bool DeleteMBTree(MBNode*&MT,KeyType K)
{
	//若樹為空，則返回假表示刪除失敗
	if(MT==NULL) return false;
	//調用FindDelete函數，由tp帶回被刪除一個關鍵字的葉子結點的地址
	MBNode* tp;
	FindDelete(MT,K,tp);
	//若MT樹中沒有可刪除的關鍵字則返回假表示刪除失敗
	if(tp==NULL) return false;
	//進行刪除后的循環(huán)處理
	while(1){
		//把tp結點中的關鍵字個數賦給n
		int n=tp->keynum;
		//若刪除后的關鍵字個數不小于最低限，則返回真表示刪除成功
		if(n>=ceil(double(m)/2)-1) return true;
		//當tp結點為整個B_樹的根結點時，若結點中無關鍵字，則應刪除
		//根結點，使整個B_樹減少一層，否則直接返回
		if(tp->parent==NULL){
			if(n==0){
				MT=MT->ptr[0];
				if(MT!=NULL) 
					MT->parent=NULL;
				delete tp;
				return true;
			}
			else return true;
		}
		//用up指向tp的雙親結點，lp和rp擬指向tp的左右兄弟節(jié)點
		MBNode *lp,*rp,*up=tp->parent;
		int i=0,j;
		//查找tp指針在雙親節(jié)點中的下標位置
		while(up->ptr[i]!=tp) i++;
		//從左兄弟結點中調劑關鍵字
		if(i>0&&up->ptr[i-1]->keynum>ceil(double(m)/2)-1){
			//lp指向tp的左兄弟結點
			lp=up->ptr[i-1];
			//修改tp結點
			for(j=n;j>=1;j--)
				tp->key[j+1]=tp->key[j];
			for(j=n;j>=0;j--)
				tp->ptr[j+1]=tp->ptr[j];
			tp->key[n+2]=MAXKEY;
			tp->key[1]=up->key[i];
			tp->ptr[0]=lp->ptr[lp->keynum];
			if(tp->ptr[0]!=NULL) tp->ptr[0]->parent=tp;
			tp->keynum++;
			//修改up結點
			up->key[i]=lp->key[lp->keynum];
			//修改lp結點
			lp->key[lp->keynum]=MAXKEY;
			lp->keynum--;
			//刪除成功返回真
			return true;
		}
		//從右兄弟結點中調劑關鍵字
		if(i<up->keynum&&up->ptr[i+1]->keynum>ceil(double(m)/2)-1){
			//rp指向tp的右兄弟結點
			rp=up->ptr[i+1];
			//修改tp結點
			tp->keynum++;
			tp->key[n+1]=up->key[i+1];
			tp->ptr[n+1]=rp->ptr[0];
			if(tp->ptr[n+1]!=NULL) tp->ptr[n+1]->parent=tp;
			tp->key[n+2]=MAXKEY;
			//修改up結點
			up->key[i+1]=rp->key[1];
			//修改rp結點
			for(j=2;j<=rp->keynum;j++){
				rp->key[j-1]=rp->key[j];
			}
			for(j=1;j<=rp->keynum;j++)
				rp->ptr[j-1]=rp->ptr[j];
			rp->key[rp->keynum]=MAXKEY;
			rp->keynum--;
			//刪除成功返回真
			return true;
		}
		//tp結點同左兄弟結點lp合并
		if(i>0){
			//lp指向tp結點的左兄弟
			lp=up->ptr[i-1];
			//把lp結點中關鍵字個數賦給n1
			int n1=lp->keynum;
			//修改lp結點
			lp->key[n1+1]=up->key[i];
			for(j=1;j<=n;j++){
				lp->key[n1+1+j]=tp->key[j];
			}
			for(j=0;j<=n;j++){
				lp->ptr[n1+1+j]=tp->ptr[j];
				if(lp->ptr[n1+1+j]!=NULL)
					lp->ptr[n1+1+j]->parent=lp;
			}
			lp->key[n1+n+2]=MAXKEY;
			lp->keynum=n1+n+1;
			//刪除tp結點
			delete tp;
			//修改up結點
			for(j=i+1;j<=up->keynum;j++){
				up->key[j-1]=up->key[j];
				up->ptr[j-1]=up->ptr[j];
			}
			up->key[up->keynum]=MAXKEY;
			up->keynum--;
			//雙親結點成為被刪除關鍵字的節(jié)點，把它賦給tp
			tp=up;
		}
		//tp結點同右兄弟結點rp合并，此時i必然為0，tp無左兄弟
		else{
			//rp指向tp結點的右兄弟
			rp=up->ptr[1];
			//把rp結點中關鍵字個數賦n2
			int n2=rp->keynum;
			//把rp結點中的每個關鍵字后移n+1位置
			for(j=n2;j>=1;j--){
				rp->key[n+1+j]=rp->key[j];
			}
			for(j=n2;j>=0;j--)
				rp->ptr[n+1+j]=rp->ptr[j];
			//把雙親結點中的一個記錄的索引項下移
			rp->key[n+1]=up->key[1];
			//把tp結點的每個關鍵字寫入到rp結點中空出的位置上
			for(j=1;j<=n;j++){
				rp->key[j]=tp->key[j];
			}
			for(j=0;j<=n;j++){
				rp->ptr[j]=tp->ptr[j];
				if(rp->ptr[j]!=NULL) rp->ptr[j]->parent=rp;
			}
			//把最大關鍵之放入rp結點的所有關鍵字之后
			rp->key[n2+n+2]=MAXKEY;
			//修改rp結點的關鍵字個數
			rp->keynum=n2+n+1;
			//刪除tp節(jié)點
			delete tp;
			//修改up結點
			for(j=2;j<=up->keynum;j++){
				up->key[j-1]=up->key[j];
			}
			for(j=1;j<=up->keynum;j++)
				up->ptr[j-1]=up->ptr[j];
			up->key[up->keynum]=MAXKEY;
			up->keynum--;
			//雙親結點成為被刪除關鍵字的結點，把它賦給tp
			tp=up;
		}	
	}
}

//中序遍歷輸出B_樹中的所有關鍵字
void TravelMBTree(MBNode* MT)
{
	if(MT!=NULL){
		TravelMBTree(MT->ptr[0]);
		for(int i=1;i<=MT->keynum;i++){
			cout<<MT->key[i]<<' ';
			TravelMBTree(MT->ptr[i]);
		}
	}
}

//清除B_樹，使之變成一棵空樹
void ClearMBTree(MBNode *& MT)
{
	if(MT!=NULL)
	{
		//刪除每個子樹
		for(int i=0;i<=MT->keynum;i++)
			ClearMBTree(MT->ptr[i]);
		//回收根結點
		delete MT;
		//置根指針為空
		MT=NULL;
	}
}

//利用層序遍歷輸出B_樹
void DisplayMBTree(MBNode * MT)
{ 
	//定義兩個隊列分別用來存放相鄰兩行的結點關鍵字，QueueNumber來記錄隊列的項數值
	//定義CurrentNode存放當前結點
	if(MT==NULL) return;
	int i,QueueNumber1=0,QueueNumber2=0;
	MBNode *Queue1[20],*Queue2[20],*CurrentNode1,*CurrentNode2;
	
	//將根結點加入Queue1
	Queue1[QueueNumber1]=MT;
	QueueNumber1++;
	//循環(huán)輸出樹
	while(QueueNumber1>0||QueueNumber2>0){
		while(QueueNumber1>0)
		{
			//將Queue1隊首結點出隊，保存至CurrentNode1結點
			CurrentNode1=Queue1[0];
			QueueNumber1--;
			//Queue1中其他結點依次前移
			i=0;
			while(i<QueueNumber1)
			{
				Queue1[i]=Queue1[i+1];
				i++;
			}
			//輸出CurrentNode1結點中關鍵字的數值
			i=0;
			while(i<CurrentNode1->keynum)
			{
				cout<<"|";
				cout<<CurrentNode1->key[i+1];
				i++;
			}
			cout<<"|   ";
			//將CurrentNode1結點的子結點加入Queue2中
			if(CurrentNode1!=NULL&&CurrentNode1->ptr[0]!=NULL)
			{
				i=0;
				while(i<=CurrentNode1->keynum)
				{
					Queue2[QueueNumber2]=CurrentNode1->ptr[i];
					QueueNumber2++;
					i++;
				}
			}
		}
		cout<<endl;         //在同一層的結點都輸出后換行
		//用同樣的方法將下一行的結點中關鍵字輸出，并將這一行結點的子結點存入Queue1中
		while(QueueNumber2>0)
		{
			//將Queue2隊首結點出隊，保存至CurrentNode2結點
			CurrentNode2=Queue2[0];
			QueueNumber2--;
			//Queue2中其他結點依次前移
			i=0;
			while(i<QueueNumber2)
			{
				Queue2[i]=Queue2[i+1];
				i++;
			}
			//輸出CurrentNode2結點中關鍵字的數值
			i=0;
			while(i<CurrentNode2->keynum)
			{
				cout<<"|";
				cout<<CurrentNode2->key[i+1];
				i++;
			}
			cout<<"|   ";
			//將CurrentNode2結點的子結點加入Queue1中
			if(CurrentNode2!=NULL&&CurrentNode2->ptr[0]!=NULL)
			{
				i=0;
				while(i<=CurrentNode2->keynum)
				{
					Queue1[QueueNumber1]=CurrentNode2->ptr[i];
					QueueNumber1++;
					i++;
				}
			}
		}
		cout<<endl;       //待該行上所有結點的中的關鍵字均輸出后回車換行
	}
	cout<<endl;
}