b树.cpp

自己开发的b+树代码,经过本人测试,已经初步通过,有问题请联系我

#define EMPTY  -1
#include <iostream.h>
class FTNode
{
public:
	int lkey;
	int ckey;
	int rkey;
	FTNode* left;
	FTNode* lcenter;
	FTNode*  rcenter;
	FTNode*  right;
public:
bool isleaf(){return left==NULL;}

FTNode(){left=lcenter=rcenter=right=NULL;lkey=ckey=rkey=EMPTY;}
};
class FTTree{  
public:
	FTNode  *root;
    FTNode  number;
public:
	bool find(FTNode* subroot,const int& k)
{
	if(subroot==NULL) return false;
    if(k==subroot->lkey){ return true;}
    if(k==subroot->ckey && subroot->ckey!=EMPTY)
	return true;
	if(k==subroot->rkey)
    return true;
	
    if(k < subroot->lkey)
        return find(subroot->left,k);
    else if(subroot->ckey==EMPTY)
        return find(subroot->lcenter,k);
    else if(k < subroot->ckey)
        return find (subroot->lcenter,k);
    else if(subroot->rkey==EMPTY)
        return find(subroot->rcenter,k);
    else if(k<subroot->rkey)
        return find(subroot->rcenter,k);
    else if (k > subroot->rkey)
        return find(subroot->right,k);
} 
bool insert(FTNode*& subroot,const int & e ,int &retval, FTNode*& retptr);
void printnode(FTNode * node);
bool splitenode(FTNode*& subroot,const int & inval ,FTNode *inptr,int & retval, FTNode*& retptr);
};
void FTTree::printnode(FTNode *node)
{if(node==NULL) return;
if(node->lkey!=EMPTY)
cout<<node->lkey<<"|"<<node->ckey<<"|"<<node->rkey<<"     ";
cout<<"!!!!!!!!!!";
if(node->lkey!=EMPTY )
{
printnode(node->left);
printnode(node->lcenter);cout<<"@@@@@@@@@@";
}
else
return;
if(node->ckey!=EMPTY)
printnode(node->rcenter);
else
return;
cout<<"###########";

if(node->rkey!=EMPTY)
printnode(node->right);
else
return;
cout<<"$$$$$$$$$$$";
cout<<endl;
cout<<endl;
cout<<endl;
}

bool FTTree::splitenode(FTNode*& subroot,const int & inval ,FTNode *inptr,int & retval, FTNode*& retptr)
{  
	retptr =new FTNode;
    if(inval <subroot->lkey)
	{
		 retval=subroot->ckey;subroot->ckey=subroot->lkey;subroot->lkey=inval;
		 
         retptr->lkey=subroot->rkey;
         retptr->left=subroot->rcenter;retptr->lcenter=subroot->right;
		 subroot->rcenter=subroot->lcenter;subroot->lcenter=inptr;
		 
	}
	else if(inval < subroot->ckey)
	{
       retval=subroot->ckey;subroot->ckey=inval;
       subroot->rcenter=inptr;retptr->left=subroot->rcenter;
       retptr->lkey=subroot->rkey;
       retptr->lcenter=subroot->right;
	}


    else if(inval < subroot->rkey)
	{
	   retval=inval;retptr->left=inptr;
	   retptr->lcenter=subroot->right;retptr->lkey=subroot->rkey;
	}
    else if(inval>subroot->rkey)
	{  
		retval=subroot->rkey;retptr->left=subroot->right;
        subroot->rkey=inval;retptr->lkey=subroot->rkey;
        retptr->lcenter=inptr;
	}
    subroot->rkey=EMPTY;
	return true;

}

bool FTTree::insert(FTNode*& subroot,const int & e ,int &retval, FTNode*& retptr)
{
	int  myretv=0;FTNode * myretp=NULL;
	
	if(subroot->isleaf())
	{
		cout<<"***********";
	if(subroot->lkey==EMPTY)
				subroot->lkey=e;
	else if(subroot->ckey==EMPTY)
			{
				 if (e >subroot->lkey)  subroot->ckey=e;
			     else if (e<subroot->lkey) 
				 {
					 subroot->ckey=subroot->lkey;
				     subroot->lkey=e;
				 }
			}
	else if (subroot->rkey==EMPTY)
			{    
				 if(e< subroot->lkey)
				 {
				 subroot->rkey=subroot->ckey;
				 subroot->ckey=subroot->lkey;
				 subroot->lkey=e;
				 }
				 else if (e >subroot->lkey && e< subroot->ckey)
				 {
					 subroot->rkey=subroot->ckey;
				     subroot->ckey=e;

				 }

				 else if (e >subroot->ckey)
				 {
					 subroot->rkey=e;
					 
				 }
			 }
			 else  
				 splitenode(subroot,e,NULL,retval,retptr);
	}
		
 	else 
	{
		if (e < subroot->lkey)
		   insert(subroot->left,e,myretv,myretp);
		else if(subroot->ckey==EMPTY || subroot->ckey >e)
		   insert(subroot->lcenter,e,myretv,myretp);
		else if(subroot->rkey==EMPTY || e < subroot->rkey)
		   insert(subroot->rcenter,e,myretv,myretp);
		else if(e>subroot->rkey)
		   insert(subroot->right,e,myretv,myretp);
	}
	if(myretp!=NULL)
	{
	if(subroot->ckey==EMPTY)
	{
		if(myretv >subroot->lkey)
		{
				subroot->ckey=myretv;subroot->rcenter=myretp;
		}
	   else if(myretv<subroot->lkey)
	   {      
				subroot->ckey=subroot->lkey;
				subroot->lkey=myretv;
				
				subroot->rcenter=subroot->lcenter;
				subroot->lcenter=myretp;
			}
	}
	else if(subroot->rkey==EMPTY)
		{
			if(myretv< subroot->lkey)
			{
				subroot->rkey=subroot->ckey;
				subroot->ckey=subroot->lkey;
				subroot->lkey=myretv;
				subroot->right=subroot->rcenter;
				subroot->rcenter=subroot->lcenter;
				subroot->lcenter=retptr;
			}
			else if(myretv<subroot->ckey)
			{
				subroot->ckey=subroot->ckey;
				subroot->right=subroot->rcenter;
				subroot->ckey=myretv;
				subroot->rcenter=myretp;
			}
			else if(myretv>subroot->ckey)
			{
				subroot->rkey=myretv;
				subroot->right=myretp;
			}
	} 
			else if(subroot->rkey!=EMPTY)
                splitenode (subroot,myretv,myretp,retval,retptr);
		}
	
	  return true;

		 

}

//打试卷上的那一张一面
FTTree *t=new FTTree;
FTNode *e=new FTNode;
FTNode * fnode1=new FTNode;
void main()
{
t->root=e;

int retal=0;
FTNode *node=NULL;
t->insert(t->root,9,retal,node);
t->insert(t->root,5,retal,node);
t->insert(t->root,3,retal,node);
t->printnode(t->root);
t->insert(t->root,4,retal,node);
if(node!=NULL)
{
FTNode * fnode=new FTNode;
fnode->lkey=retal;
fnode->left=t->root;
fnode->lcenter=node;
t->root=fnode;
}
t->printnode(t->root);
t->insert(t->root,6,retal,node);
t->printnode(t->root);
t->insert(t->root,7,retal,node);
t->printnode(t->root);
const int b=2; 
t->insert(t->root,b,retal,node);
t->printnode(t->root);
const int c=1;
t->insert(t->root,c,retal,node);
t->printnode(t->root);  
t->insert(t->root,8,retal,node);
t->printnode(t->root); 
 t->insert(t->root,10,retal,node);
t->printnode(t->root); 
t->insert(t->root,11,retal,node);
t->printnode(t->root); 
FTNode *node1=NULL;
t->insert(t->root,12,retal,node1);
if(node1!=NULL)
{
fnode1->lkey=retal;
fnode1->left=t->root;
fnode1->lcenter=node1;
t->root=fnode1;
}  
t->printnode(t->root); 
t->insert(t->root,13,retal,node);
t->printnode(t->root); 
t->insert(t->root,14,retal,node);
t->printnode(t->root); 
t->insert(t->root,15,retal,node);
t->printnode(t->root); 
t->insert(t->root,16,retal,node);
t->printnode(t->root);
t->insert(t->root,17,retal,node);
t->printnode(t->root);  
t->insert(t->root,18,retal,node);
t->printnode(t->root);
t->insert(t->root,19,retal,node);
t->printnode(t->root);  
t->insert(t->root,20,retal,node);
t->printnode(t->root);
t->insert(t->root,21,retal,node);
t->printnode(t->root); 
t->insert(t->root,22,retal,node);
t->printnode(t->root);  
t->insert(t->root,23,retal,node);
t->printnode(t->root);   
}