btree.cpp

图书管理系统 C**实现的 包括B树 可以参考一下呀 有需要联系我哈

#include "head.h"

void InitBTree(BTree &T)
{
	T=(BTree)malloc(sizeof(BTNode));
	T->keynum=0;
	T->parent=NULL;
	T->ptr[0]=NULL;
}
int Search(BTree p,int k)
{
	int i=0;
	while(i<p->keynum)
	{
		if(p->key[i+1]->k>k)
			return i;
		else if(p->key[i+1]->k==k)
			return i+1;
		else i++;
	}
	return i;
}

Result SearchBTree(BTree T,int k)
{
	BTree p,q;
	Result r;
	int found=FALSE,i=0;
	q=NULL;
	p=T;	
	while(p!=NULL&&!found){
		i=Search(p,k);
		if(i>0 && p->key[i]->k==k) found=TRUE;
		else{
			q=p;
			if(	p->ptr[i])
			p->ptr[i]->parent=p;
			p=p->ptr[i];
		}
	}
	if(found)
	{
		r.pt=p;
		r.i=i;
		r.tag=1;
	}
	else
	{
		if(T==NULL)
			r.pt=T;
		else
		r.pt=q;
		r.i=i;
		r.tag=0;
	}
	return r;
}

void split(BTree &q,int s,BTree &ap)
{
	int i;
	ap=(BTree)malloc(sizeof(BTNode));
	ap->keynum=q->keynum-s;
	for(i=1;i<=ap->keynum;i++)
	{
		ap->key[i]=(KeyType *)malloc(sizeof(KeyType));
		ap->key[i]->k=q->key[i+s]->k;
		ap->key[i]->recptr=q->key[i+s]->recptr;
		ap->ptr[i]=q->ptr[s+i];
	}

	ap->ptr[0]=q->ptr[s];


	ap->parent=q->parent;
	q->keynum=s-1;
}

void Insert(BTree &q,int i,KeyType x,BTree ap)
{
	int j;
	q->keynum++;

	q->key[q->keynum]=(KeyType *)malloc(sizeof(KeyType));
	for(j=q->keynum;j>i+1;j--)
	{
		q->key[j]->k=q->key[j-1]->k;  //？？？如果直接写成q->key[j]=q->key[j-1]就会有错
		q->key[j]->recptr=q->key[j-1]->recptr;
		q->ptr[j]=q->ptr[j-1];
		
	}
	q->key[i+1]->k=x.k;
	q->key[i+1]->recptr=x.recptr ;
	q->ptr[i+1]=ap;
	if(ap!=NULL)
		ap->parent=q;


}

void NewRoot(BTree &T,BTree q,KeyType x,BTree ap)
{
	BTree temp;
	temp=T;
	/*temp=(BTree)malloc(sizeof(BTNode));
	temp->keynum=1;
	temp->parent=NULL;
	 //T->key[1]=x; 不能直接赋值，而要分别对其中的元素赋值～
	temp->key[1]=(KeyType *)malloc(sizeof(KeyType));
	temp->key[1]->k=x.k;
	temp->key[1]->recptr=x.recptr;
	temp->ptr[0]=T;
	T->ptr[1]=ap;
	T=temp;*/
	T=(BTree)malloc(sizeof(BTNode));
	T->keynum=1;
	T->parent=NULL;
	 temp->parent=T;
	 ap->parent=T;
	T->key[1]=(KeyType *)malloc(sizeof(KeyType));
	T->key[1]->k=x.k;
	T->key[1]->recptr=x.recptr;
	T->ptr[0]=temp;
	T->ptr[1]=ap;
	

	
}
Status InsertBTree(BTree &T,KeyType k,BTree q,int i)
{
	int s,j;
	KeyType x;
	BTree ap,parent=T;
	int finished=FALSE;
	x=k;
	ap=NULL;
	if(T!=NULL &&q!=T)
	for(j=0;j<=T->keynum;j++)
		if(q==T->ptr[j])
		{
			q->parent=T;
			break;
		}
	while(q!=NULL &&!finished)
	{
		Insert(q,i,x,ap);
		if(q->keynum<3) finished=TRUE;
		else
		{
			s=M/2+1;
			split(q,s,ap);
			x.k=q->key[s]->k;
			x.recptr=q->key[s]->recptr;
			q=q->parent;
			if(q!=NULL) i=Search(q,x.k);
		}
	}
	if(!finished)
		NewRoot(T,q,x,ap);
	return OK;
}
void FindSmallest(BTree p,BTree &q)
{
	q=p;
	while(q->ptr[0]!=NULL)
		q=q->ptr[0];
}

int Parent(BTree p) //返回p的父结点中指向p的编号
{
	BTree q;
	int i;
	q=p->parent;
	if(q!=NULL)
	for(i=0;i<=q->keynum;i++)
		if(q->ptr[i]==p)
			return i;
		return -1;
}
void RightBrother(BTree p,BTree &right)
{
	int i;
	if(p->parent==NULL)
		right=NULL;
	i=Parent(p);
	if((i+1)<=p->parent->keynum)
	{
		right=p->parent->ptr[i+1];
		if(right)
		right->parent=p->parent;
	}
	else
		right=NULL;
	
}

void LeftBrother(BTree p,BTree &left)
{
	int i;
	if(p->parent==NULL)
		left=NULL;
	i=Parent(p);
	if((i-1)>=0)
	{
		left=p->parent->ptr[i-1];
		left->parent=p->parent;
	}
	else
		left=NULL;

}
	

	
void LeftMove(BTree &p,int loc)
{
	int i;
	for(i=loc;i<p->keynum;i++)
	{
		p->key[i]->k=p->key[i+1]->k;
		p->key[i]->recptr=p->key[i+1]->recptr;
		p->ptr[i]=p->ptr[i+1];
	}
}

Status DeleteBTree(BTree &T,int k)
{
	int i,loc,key,s;
	BTree p,q,right,left,ap;
	KeyType x;
	Result location;
	int finished=FALSE;

	location=SearchBTree(T,k);

	if(!location.tag)
	{
		printf("can't find the node with keyword %d.\n",k);
		return ERROR;
	}
	p=location.pt;      //要删除的结点的位置～～
	loc=location.i;

	if(p->ptr[0]!=NULL)     //删除结点为非终端结点时
	{
		FindSmallest(p->ptr[loc],q); //q记录p->ptr所指子树中的最小关键字
		key=q->key[1]->k;
		DeleteBTree(T,key);
		p->key[loc]->k=key;
	}
	else
	{
	if(p->keynum>=M/2+1)  //关键字数目不小于m/2时
	{
		for(i=loc;i<p->keynum;i++)
		{
			p->key[i]->k=p->key[i+1]->k;
			p->key[i]->recptr=p->key[i+1]->recptr;
		}
		p->keynum--;
		finished=TRUE;
	}
	else

	if(p->keynum==M/2)
	{
		i=Parent(p);
		RightBrother(p,right);

		if(right && right->keynum>M/2)
		{
			p->key[M/2]->k=p->parent->key[i+1]->k;
			p->key[M/2]->recptr=p->parent->key[i+1]->recptr;
			p->parent->key[i+1]->k=right->key[1]->k;
			p->parent->key[i+1]->recptr=right->key[1]->recptr;
			right->key[1]->k=right->key[2]->k;
			right->key[1]->recptr=right->key[2]->recptr;
			right->keynum--;
			finished=TRUE;
		}
		else
		{
			LeftBrother(p,left);
			if(left && left->keynum>M/2)
			{
				p->key[1]->k=p->parent->key[i]->k;
				p->key[1]->recptr=p->key[1]->recptr;
				p->parent->key[i]->k=left->key[left->keynum]->k;
				p->parent->key[i]->recptr=left->key[left->keynum]->recptr;

				left->keynum--;
				finished=TRUE;
			}
			else  //相邻兄弟结点中关键字数目均等于m/2-1
			{
				while(p->parent && !finished)
				{
				if(right)
				{
					i=Parent(right);
					right->keynum++;
					right->key[2]=(KeyType *)malloc(sizeof(KeyType));//don't forget!
					right->key[2]->k=right->key[1]->k;
					right->key[2]->recptr=right->key[1]->recptr;
					right->ptr[2]=right->ptr[1];
					right->ptr[1]=right->ptr[0];
					p->keynum--;
					right->key[1]->k=p->parent->key[i]->k;
					right->key[1]->recptr=p->parent->key[i]->recptr;

					p->parent->keynum--;
					if(p->ptr[0] && p->ptr[0]->keynum!=0)
					right->ptr[0]=p->ptr[0];
					else
						right->ptr[0]=p->ptr[1];
					
					if(p->parent->keynum>=M/2 &&p->parent->keynum<M)
					{
						if(!left)
						{
							p->parent->key[1]->k=p->parent->key[2]->k;
							p->parent->key[1]->recptr=p->parent->key[2]->recptr;
							 
							p->parent->ptr[0]=p->parent->ptr[1];
							p->parent->ptr[1]=p->parent->ptr[2];
						}
						else
						p->parent->ptr[1]=right;
						finished=TRUE;
					}
					
				}
				else if(left )
				{
				    if(left->keynum<2)
					i=Parent(left);
				
					left->keynum++;
					left->key[left->keynum]=(KeyType *)malloc(sizeof(KeyType));
					left->key[left->keynum]->k=p->parent->key[i+1]->k;
					left->key[left->keynum]->recptr=p->parent->key[i+1]->recptr;
					p->parent->keynum--;
					p->parent->ptr[i+1]=NULL;
					if(p->ptr[1])
					left->ptr[left->keynum]=p->ptr[1];
					else
						left->ptr[left->keynum]=p->ptr[0];
				
					if(p->parent->keynum>=M/2 && left->keynum<M)
					{
						LeftMove(p->parent,i);
						//p->parent->key[1]=p->parent->key[2];
						//p->parent->ptr[0]=right->ptr[1];
						//p->parent->ptr[1]=right->ptr[2];
					
						
						finished=TRUE;
					}

						if(left->keynum>=M)
						{
							s=2;
							split(left,s,ap);
							p=p->parent->parent;
							i=Search(p,left->key[s]->k);
							x.k=left->key[s]->k;
							x.recptr=left->key[s]->recptr;
							/*while(p!=NULL &&!finished)
							{
								Insert(p,i,x,ap);
								p->ptr[i]=left;
								if(p->keynum<3) finished=TRUE;
								else
								{
									s=M/2+1;
									split(p,s,ap);
									x.k=p->key[s]->k;
									x.recptr=p->key[s]->recptr;
									p=p->parent;
									if(p!=NULL) i=Search(p,x.k);
								}
							}
							if(!finished)
							{
								NewRoot(T,p,x,ap);
								finished=TRUE;

							}*/
				}
				}
				
				}// if (left)
				else if(left->keynum==2)
				{
					p->key[1]->k=p->parent->key[1]->k;
					p->key[1]->recptr=p->parent->key[1]->recptr;
					p->parent->key[1]->k=left->key [2]->k;
					p->parent->key[1]->recptr=left->key [2]->recptr;
					p->ptr[1]=p->ptr[0];
					p->ptr[0]=left->ptr[2];
					left->ptr[2]->parent=p;
					p->keynum++;
					left->keynum--;
					finished=TRUE;
				}
					


			 
				if(!finished)
				{
					/*if(p->parent->parent &&  p->parent->keynum==0)
					{
					if(right)
					{
						i=Parent(p->parent);

						p->parent->ptr[i]=right;
						finished=TRUE;
					}
					else
					if(left)
					{
						i=Parent(p->parent);
						p->parent->ptr[i]=left;
					}
					}
					else */
						if(!p->parent->parent &&  p->parent->keynum==0)
					{
						if(right)
						T=right;
						else
						if(left)
						T=left;
						T->parent=NULL;
						finished=TRUE;
					}
	
					else
					{
				
					p=p->parent;
					if(p)
					{
					RightBrother(p,right);
					LeftBrother(p,left);
					}
					}
					
				}
					
				} //while 

			}
		}
	}
		
	}
	return OK;
}
void PrintBTree(BTree T)
{
	int i;
	if(T==NULL) return;//{printf("NULL\n");return;}
	if(T->parent!=NULL)
		if(T->parent->parent==NULL)
			printf("	");
		else if(T->parent->parent->parent==NULL)
			printf("		");
		else if(T->parent->parent->parent->parent==NULL)
			printf("			");

	for(i=1;i<=T->keynum;i++)
		printf("%d ",T->key[i]->k);
	printf("\n");
	
	for(i=0;i<=T->keynum;i++)
	{
		//printf("*%d*",i);
		PrintBTree(T->ptr[i]);
	}
}