b_tree.cpp

实现B-树的创建、插入、删除、遍历等功能

#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结点的所有关键字最后放入最大关键字
		//若条件成立，则需建立新的树根结点，所以退出循环
		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所在的节点
	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;
	}
	//在非叶子结点上查找成功，则继续查找该结点的中序前驱结点和
	//中序前驱关键字，作对调和删除后，有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;
	//进行删除后的循环处理
	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的左右兄弟节点
		MBNode *lp,*rp,*up=tp->parent;
		int i=0,j;
		//查找tp指针在双亲节点中的下标位置
		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--;
			//双亲结点成为被删除关键字的节点，把它赋给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节点
			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++;
	//循环输出树
	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;
}