b_tree.cpp

B-树的创建、插入、删除等一系列操作！

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define NULL 0
#define M 3						    //定义B_树的阶数
#define MAXKEY 32767				//定义B_树的最大关键字

typedef int KeyType;				//定义关键字类型	

typedef struct B_Node				//定义B_树结点类型
{
	int keynum;						//关键字数目
	B_Node *parent;					//指向父亲结点的指针			
	KeyType key[M+1];				//关键字数组，下标0未用	
	B_Node *ptr[M+1];				//指向孩子的指针数组
}B_Node;

void B_Init(B_Node *&Root)			//初始化B_树
{
	Root=NULL;
}

int B_Empty(B_Node *Root)			//判断B_树空否,若空则返回1,不空返回0
{
	if(Root==NULL)
		return 1;
	else 
		return 0;
}

void B_PreOrderTraverse(B_Node *Root)		//先序遍历B_树
{
	int i;
	B_Node *p=Root;
	if(p!=NULL)
	{
		printf("(");
		for(i=1;i<p->keynum;i++)			//输出该结点关键字
			printf("%d,",p->key[i]);
		printf("%d) ",p->key[i]);
		for(i=0;i<=p->keynum;i++)
			B_PreOrderTraverse(p->ptr[i]);	//从左至右先序递归遍历其子树
	}
	printf(".");							//提示为叶子结点
}

void B_Search(B_Node *Root,KeyType k,B_Node *&pt,int &pos,int &tag)
//从B_树Root上查找关键字为k的插入位置,pt返回插入结点的位置,pos返回
//插入下标,tag返回查找成功与否,成功则为1,否则为0
{
	int i;
	B_Node *p=Root;				//p指向B_树的根结点
	while(p!=NULL)
	{
		i=1;
		while(k>p->key[i])		//查找p指向的结点中关键字不小于k的第1个关键字的下标i
			i++;			
		if(k==p->key[i])		//若找到则返回该结点的指针pt和位置i及标志tag
		{
			tag=1;
			pt=p;
			pos=i;
			return;
		}
		else					//未找到则保存pt,pos后继续寻找,直到p为空
		{
			pt=p;
			pos=i;
			p=p->ptr[i-1];
		}
	}
	tag=0;
}

int B_Insert(B_Node *&Root,KeyType k)	//在Root指向的B_树中插入关键字k
{
	if(Root==NULL)						//若B_树为空树则创建根结点
	{
		Root=(B_Node *)malloc(sizeof(B_Node)); 
		Root->keynum=1;
		Root->parent=NULL;
		Root->key[1]=k;					//插入关键字k
		Root->key[2]=MAXKEY;
		Root->ptr[0]=Root->ptr[1]=NULL;
		return 1;						//插入成功,退出
	}
	B_Node *pt;						//pt指向插入结点
	int pos,tag;					//pos记录关键字所在结点的位置下标
	B_Search(Root,k,pt,pos,tag);	//查找插入点
	if(tag==1)						//若存在该关键字则不需插入
	{
		printf("\n关键字%d在B_树上已存在，不需插入!\n",k);
		return 0;
	}
	B_Node *pa=NULL;
	while(1)				//结束条件为插入关键字k后,所有结点关键字数目均不大于
	{						//M-1或需分裂一个新的根结点
		int i,j,n;
		n=pt->keynum;		//被插入结点关键字数目
		for(i=n;i>=pos;i--)	//从插入位置到最后的所有数据域均后移一个位置
		{
			pt->key[i+1]=pt->key[i];
			pt->ptr[i+1]=pt->ptr[i];
		}
		pt->key[pos]=k;		//插入关键字
		pt->ptr[pos]=pa;	//连上pa,pa为新分裂结点的指针
		pt->keynum++;
		if(pt->keynum<=M-1)	//若该结点关键字数目不大于M-1则插入结束
		{
			pt->key[pt->keynum+1]=MAXKEY;
			return 1;
		}
		//否则需分裂结点
		j=int(ceil(double(M)/2));				//对m/2向上取整
		pa=(B_Node *)malloc(sizeof(B_Node));	//pa为新分裂结点的指针
		pa->keynum=M-j;	
		pa->parent=pt->parent;
		for(i=1;i<=pa->keynum;i++)				//为新分裂结点赋关键字
			pa->key[i]=pt->key[i+j];
		for(i=0;i<=pa->keynum;i++)				//为新分裂结点赋孩子指针
		{
			pa->ptr[i]=pt->ptr[i+j];
			if(pa->ptr[i]!=NULL)				//若孩子指针指向其他子树
				pa->ptr[i]->parent=pa;			//则该子树的双亲指向新分裂的结点pa		
		}
		pa->key[M-j+1]=MAXKEY;			//pa的第一个无用关键字置最大值
		pt->keynum=j-1;					//需分裂结点pt的关键字数目置j
		k=pt->key[j];					//向上分裂的关键字置k
		pt->key[i]=MAXKEY; 				//需分裂结点pt的第一个无用关键字置最大值
		if(pt->parent==NULL) break;		//若需分裂的结点为根结点则跳出循环
		pt=pt->parent;					//若不是根结点则pt上移至其双亲
		i=1;							//在其双亲中再次寻找插入位置pos,继续循环	
		while(k>pt->key[i])
			i++;
		pos=i;
	}
	Root=(B_Node *)malloc(sizeof(B_Node));	//创建一个新的根结点,连上pt,pa
	Root->keynum=1;
	Root->parent=NULL;
	Root->key[1]=k;
	Root->key[2]=MAXKEY;
	Root->ptr[0]=pt;
	Root->ptr[1]=pa;
	pt->parent=Root;
	pa->parent=Root;
	return 1;								//插入结束
}

int B_Delete(B_Node *&Root, KeyType k)
//在Root指向的B_树中删除关键字k,并返回根指针Root
{
	if(Root==NULL)				//若该树为空,则退出
		return 0;
	int i,j,f;					//i为被删除关键字所在位置
	B_Node *pm,*pb,*q;			//pm指向删除结点
	B_Search(Root,k,pm,i,f);	//寻找删除点,并返回指针pm,位置i,标志f
	if(f==0)					//若未找到,则退出
		return 0;
	if(pm->ptr[i]==NULL)		//若pm指向叶子结点则直接删除该关键字
	{
		int n=pm->keynum;
		for(int j=i+1;j<=n;j++)
			pm->key[j-1]=pm->key[j];	//因为是叶子结点故不需移动孩子指针
		pm->keynum--;
		pm->key[n]=MAXKEY;
	}
	//若pm指向非叶子结点则查找其中序前驱结点及中序前驱关键字
	//,调整关键字,使被删关键字落在叶子结点上,以便于逐层调整结点
	if(pm->ptr[i]!=NULL)	
	{
		pb=pm;				//pb存储待删关键字所在结点
		q=pm;				//q作为pm前驱
		pm=pm->ptr[i-1];	//pm指向关键字k的左子树
		while(pm!=NULL)		//q指向该子树的最大结点
		{
			q=pm;
			pm=pm->ptr[pm->keynum];
		}
		pb->key[i]=q->key[q->keynum];   //被删关键字k的中序前驱关键字赋值给k
		q->key[q->keynum]=MAXKEY;		//删除中序前驱关键字
		q->keynum--;
		pm=q;							//pm指向该中序前驱关键字所在叶子结点
	}
	//调整删除后的结点,使其满足B_树的条件
	while(1)							//结束条件为所有结点满足B_树的要求
	{
		int n=pm->keynum;				//n记录被删结点的关键字数目
		if(n>=ceil((double(M)/2)-1))	//若被删结点关键字数目大于M/2向上取整则删除结束
			return 1;
		if(pm->parent==NULL)		
		{
			if(n>0&&n<ceil(double(M)/2)-1)	//若被删结点为根结点,且关键字个数不为0
				return 1;					//删除结束
			if(n==0)					//若被删结点没有关键字
			{
				Root=Root->ptr[0];		//Root指向其左子树根结点
				if(Root!=NULL)
					Root->parent=NULL;	//若根指针不空则其指向的结点成为根结点
				return 1;				//删除结束
			}
		}
		B_Node *pl,*pr,*pp=pm->parent;	//pp指向被删结点的双亲
		i=0;
		while(pp->ptr[i]!=pm)			//寻找指针pm在双亲结点孩子指针域中的下标位置i
			i++;
		if(i>0&&pp->ptr[i-1]->keynum>ceil(double(M)/2)-1)
		//被删关键字所在结点中的关键字数目=[M/2]-1,而与该结点相邻的左兄弟结点中
		//的关键字数目>[M/2]-1
		//则需向左兄弟中调整关键字
		{
			pl=pp->ptr[i-1];			//pl指向被删结点的左兄弟
			for(j=n;j>=1;j--)			//被删结点空出第一个关键字及指针域
			{
				pm->key[j+1]=pm->key[j];
				pm->ptr[j+1]=pm->ptr[j];
			}
			pm->ptr[1]=pm->ptr[0];
			pm->key[n+2]=MAXKEY;
			pm->key[1]=pp->key[i];		//被删结点双亲对应关键字下移至被删结点的第一个关键字
			pm->ptr[0]=pl->ptr[pl->keynum];	//左兄弟对应子指针右移至被删结点的第一个孩子指针
			if(pm->ptr[0]!=NULL)			//若该指针指向其他子树,则修改其子树的双亲域
				pm->ptr[0]->parent=pm;
			pm->keynum++;					//修改被删结点数据
			pp->key[i]=pl->key[pl->keynum];	//左兄弟最大关键字上移至其双亲的第一个关键字
			pl->key[pl->keynum]=MAXKEY;		//修改左兄弟数据
			pl->keynum--;
			return 1;						//删除结束
		}
		if(i<pp->keynum&&pp->ptr[i+1]->keynum>ceil(double(M)/2)-1)
		//被删关键字所在结点中的关键字数目=[M/2]-1,而与该点相邻的右兄弟结点中
		//的关键字数目>[M/2]-1
		//则需向右兄弟中调整关键字
		{
			pr=pp->ptr[i+1];			//pr指向被删结点的右兄弟
			pm->keynum++;
			pm->key[n+1]=pp->key[i+1];	//被删结点双亲对应关键字下移至被删结点的最大有效关键字
			pm->ptr[n+1]=pr->ptr[0];	//右兄弟对第一个指针左移至被删结点的最后一个有效指针
			if(pm->ptr[n+1]!=NULL)		//若该指针指向其他子树,则修改其子树的双亲域
				pm->ptr[n+1]->parent=pm;
			pm->key[n+2]=MAXKEY;		
			pp->key[i+1]=pr->key[1];	//右兄弟最小关键字上移至其双亲的对应关键字
			pr->ptr[0]=pr->ptr[1];		//右兄弟剩余数据均左移一个位置
			for(j=2;j<=pr->keynum;j++)
			{
				pr->key[j-1]=pr->key[j];
				pr->ptr[j-1]=pr->ptr[j];
			}
			pr->key[pr->keynum]=MAXKEY;
			pr->keynum--;
			return 1;					//删除结束
		}
		if(i>0)
		//被删关键字所在结点和其相邻的左兄弟结点中的关键字数目均=[M/2]-1
		//则需向左兄弟中合并关键字
		{
			pl=pp->ptr[i-1];				//pl指向被删结点的左兄弟
			int n1=pl->keynum;				//n1记录左兄弟的关键字数目
			pl->key[n1+1]=pp->key[i];		//双亲结点对应关键字合并至左兄弟最大关键字处
			for(j=1;j<=n;j++)				//pm指向结点中剩余关键字合并至左兄弟中
				pl->key[n1+1+j]=pm->key[j];
			for(j=0;j<=n;j++)				//pm指向结点中剩余的孩子指针合并至左兄弟中
			{
				pl->ptr[n1+1+j]=pm->ptr[j];
				if(pl->ptr[n1+1+j]!=NULL)
					pl->ptr[n1+1+j]->parent=pl;//若该指针指向其他子树,则修改其子树的双亲域
			}
			pl->key[n1+n+2]=MAXKEY;			//修改左孩子记录数据
			pl->keynum=n1+n+1;
			for(j=i+1;j<=pp->keynum;j++)	//双亲剩余数据均左移一个位置
			{
				pp->key[j-1]=pp->key[j];
				pp->ptr[j-1]=pp->ptr[j];
			}
			pp->key[pp->keynum]=MAXKEY;
			pp->keynum--;
			pm=pp;							//双亲结点成为被删结点
		}									//因双亲被合并一个关键字,故需重新调整该树
		else
		//被删关键字所在结点和其相邻的右兄弟结点中的关键字数目均=[M/2]-1,i必为0
		//则需向右兄弟中合并关键字
		{
			pr=pp->ptr[1];					//pr指向被删结点的右兄弟
			int n2=pr->keynum;				//n2记录右兄弟的关键字数目
			for(j=n2;j>=1;j--)				//右兄弟数据均后移n2=n+1个位置
			{
				pr->key[n2+j]=pr->key[j];
				pr->ptr[n2+j]=pr->ptr[j];
			}
			pr->ptr[n2]=pr->ptr[0];
			pr->key[n+1]=pp->key[1];		//双亲第一个关键字合并至右兄弟中
			for(j=1;j<=n;j++)				//被删结点中剩余关键字合并至右兄弟中
				pr->key[j]=pm->key[j];
			for(j=0;j<=n;j++)				//被删结点中剩余孩子指针合并至右兄弟中
			{
				pr->ptr[j]=pm->ptr[j];
				if(pr->ptr[j]!=NULL)
					pr->ptr[j]->parent=pr;	//若该指针指向其他子树,则修改其子树的双亲域
			}
			pr->key[2*n+3]=MAXKEY;
			pr->keynum=2*n+2;
			pp->ptr[0]=pp->ptr[1];			//双亲剩余数据均左移一个位置
			for(j=2;j<=pp->keynum;j++)
			{
				pp->key[j-1]=pp->key[j];
				pp->ptr[j-1]=pp->ptr[j];
			}
			pp->key[pp->keynum]=MAXKEY;
			pp->keynum--;
			pm=pp;							//双亲结点成为被删结点
		}									//因双亲被合并一个关键字,故需重新调整该树
	}										//while end
}

void main()
{
	int flag,flag2,num,num2,n,local,i,k,del;
	B_Node *ps,*pr;							//ps指向根结点
	KeyType key;
	B_Init(ps);
	while(1)
	{
		printf("\n*****************************************************************\n");
		printf("		1.先序遍历B_树中所有结点\n");
		printf("		2.在B_树中查找关键字\n");
		printf("		3.在B_树中插入关键字\n");
		printf("		4.在B_树中删除关键字\n");
		printf("		5.初始化B_树\n");
		printf("		6.退出程序\n");
		printf("*****************************************************************\n");
loop:	printf("\n请输入您的选择(1-6):");
		scanf("%d",&n);
		if(n<1||n>6)
		{
			printf("输入超出范围,请重新输入:");
			goto loop;
		}
		switch(n)
		{
		case 1:
			printf("\n");
			flag=B_Empty(ps);
			if(flag==1)
				printf("该B_树为空树\n");
			if(flag==0)
			{
				printf("先序序列:");
				B_PreOrderTraverse(ps);
				printf("\n");
			}
			break;
		case 2:
			flag=B_Empty(ps);
			if(flag==1)
				printf("\n该B_树为空树\n");
			if(flag==0)
			{
				printf("\n请输入要查找的关键字:");
				scanf("%d",&key);
				B_Search(ps,key,pr,local,flag);
				if(flag==1)
				{
					printf("\n该关键字%d对应的结点为(",key);
					for(i=1;i<pr->keynum;i++)
						printf("%d,",pr->key[i]);
					printf("%d),",pr->key[i]);
					printf("在该结点中的位置为%d\n",local);
				}
				else
					printf("\n未找到该关键字%d!\n",key);
			}
			break;
		case 3:
			printf("\n请输入要插入关键字的个数:");
			scanf("%d",&num);
			for(i=1;i<=num;i++)
			{
				printf("\n请输入第%d个关键字:",i);
				scanf("%d",&key);
				k=B_Insert(ps,key);
				if(k==1)
				{
					printf("先序序列:");
					B_PreOrderTraverse(ps);
				}
			}
			break;
		case 4:
			flag=B_Empty(ps);
			if(flag==1)
				printf("\n该B_树已为空树\n");
			if(flag==0)
			{
				printf("\n请输入要删除的关键字个数:");
				scanf("%d",&num2);
				for(i=1;i<=num2;i++)
				{
					printf("\n请输入第%d个要删除的关键字:",i);
					scanf("%d",&del);
					k=B_Delete(ps,del);
					if(k==0)
						printf("\n未找到该关键字!\n");
					flag2=B_Empty(ps);
					if(flag2==1)
					{
						printf("\n该B_树已为空树");
						break;
					}
					printf("先序序列:");
					B_PreOrderTraverse(ps);
				}
			}
			break;
		case 5:
			B_Init(ps);
			printf("\n初始化完成!\n");
			break;
		case 6:
			return;
		}
	}
}