btree.h

数据结构课程设计 数据结构B+树 B+ tree Library

#include "LinkList.h"
#define m 4 
enum {FALSE,TRUE};
struct Book
{
int number;//编号
char name[10];//书名
};
struct BTNode
   {
     int keynum;   //结点中关键字的个数
     BTNode *parent; //双亲指针
     char  key[m+1];//关键字向量
     BTNode  *childs[m+1];//树指针向量 
	 LHList<Book *> *books[m+1];//图书链表
	 BTNode()
	 {
	 	 for(int i=0;i<m+1;i++)
		 {
			key[i]='z';
			keynum=0;
			childs[i]=NULL;
			books[i]=NULL;
		 }
	 }
    };  //B+树结点和B+树类型

int Search(BTNode *p, char key)
{
  for(int i=0;i<p->keynum;i++)
  {
	  if(p->key[i]>=key)
		 return i;
  }
	 return p->keynum;
}

BTNode *Search(BTNode *root ,char key,int &position,int &find)//查找
{
   BTNode *p=root;
   int i=0,j=0;
   while(p)
   {
           i=Search(p, key);  //找到key的位置
		   if(p->childs[i]!=NULL)
		   p=p->childs[i];
		   else
		   {
			     for(j=0;j<p->keynum;j++)				 
				 {
					 if(p->key[j]==key)
					 {
					   position=j;
			           find=TRUE;//找到
					 }
				 }
				 return p;
		   }
   } 
	return  p;  //成功，返回位置 
}

void insertBTNode(BTNode *root,char key,int &position)
{
	 int i=Search(root, key);  //找到key的位置
	 for(int j=root->keynum;j>i;j--)
	 {
		 root->key[j]=root->key[j-1];
         root->books[j]=root->books[j-1]; 
	 }
	 root->key[i]=key;
	 root->keynum++;
	 position=i;
}
void divide(BTNode *left,BTNode *right,BTNode *root)
{
 for(int i=0;i<(m+1)/2;i++)  ///分裂当前节点
   {
    left->key[i]=root->key[i];
	left->childs[i]=root->childs[i];
    if(left->childs[i]!=NULL)
	left->childs[i]->parent=left;
	root->childs[i]=NULL;
	root->key[i]='z';
	left->books[i]=root->books[i];
	root->books[i]=NULL;
    left->keynum++;

    right->key[i]=root->key[i+(m+1)/2];
	right->childs[i]=root->childs[i+(m+1)/2];
	 if(right->childs[i]!=NULL)
    right->childs[i]->parent=right;
	root->childs[i+(m+1)/2]=NULL;
	root->key[i+(m+1)/2]='z';
	right->books[i]=root->books[i+(m+1)/2];
    root->books[i+(m+1)/2]=NULL;
    right->keynum++;
   }
   if((m+1)%2!=0)
   {
	   right->key[(m+1)/2]=root->key[m];
	   right->childs[(m+1)/2]=root->childs[m];
	    if(right->childs[i]!=NULL)
	   right->childs[(m+1)/2]->parent=right;
	   root->childs[m]=NULL;
	   right->books[(m+1)/2]=root->books[m];
	   root->books[m]=NULL;
	   root->key[m]='z';
       right->keynum++;
   }    
}
void setBalance(BTNode *root)//调平衡B树
{
   BTNode *left=new BTNode();
   BTNode *right=new BTNode();
   divide(left,right,root);//分裂节点
   if(root->parent!=NULL)//非根节点时
   {
	   BTNode *parent=root->parent;
      for(int i=0;i<parent->keynum;i++)//找到该节点在父节点的位置
		  if(parent->childs[i]==root)
		    break;
	  for(int j=parent->keynum;j>i;j--)//该节点后的节点向后移动一位
	  {
	    parent->key[j]=parent->key[j-1];
		parent->childs[j]=parent->childs[j-1];
	  }
	  parent->key[i]=left->key[left->keynum-1];
	  parent->childs[i]=left;
      parent->key[i+1]=right->key[right->keynum-1];
      parent->childs[i+1]=right;
      parent->keynum++;
	  left->parent=parent;
	  right->parent=parent;
	  delete root;
	  if(parent->keynum>m)//如果没有平衡继续调平衡
       setBalance(parent);//继续
   }
   else
   { 
       root->keynum=2;
       root->key[0]=left->key[left->keynum-1];
	   root->key[1]=right->key[right->keynum-1];
	   root->childs[0]=left;
	   root->childs[1]=right;
	   left->parent=root;
	   right->parent=root;
   }
}