bayertree.cpp

数据结构实验课中的所有实验程序

// BayerTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <fstream.h>
#include <stdlib.h>
#include <math.h>
#include "BayerTree.h"

static void PreorderWrite(ofstream& ofs,MBNode * MT);
static void PreorderRead(ifstream& ifs,MBNode *& MT,int&b);

void InitMBTree(MBNode *& MT)
{MT=NULL;}

bool MBTreeEmpty(MBNode*MT)
{return MT==NULL;}

int B_Search (MBNode *MT,KeyType K)
{
	 int i;
     MBNode *p=MT;
  while(p!=NULL)
  {
	   i=1;
	   while(K>p->key[i]) i++;
	   if(K==p->key[i])
		   return p->recptr[i];
	   else
		    p=p->ptr[i-1];
  }
        return -1;}

void FindInsert(MBNode*mt,KeyType K,MBNode *& Tp,int &Pos)
{
	 int i;
	 MBNode *p;
	 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];
		  }
	 }
	 Tp=p;Pos=i;
}


void B_Insert(MBNode * & MT,KeyType K,int num)
{
	if(MT==NULL){MT=new MBNode;
	MT->keynum=1;
	MT->parent =NULL;
	MT->key[1]=K;MT->key[2]=MAXKEY;
	MT->recptr[1]=num;
	MT->ptr[0]=MT->ptr[1]=NULL;
	return;
	}
    MBNode *tp;int pos;
	FindInsert(MT,K,tp,pos);
	if(tp==NULL){cout<<"关键字"<<K<<"在B_树上已经存在，不需插入！"<<endl;
	return;}
	MBNode *ap=NULL;
	while(1){
		   int i,n;
	   n=tp->keynum ;
	   for(i=n;i>=pos;i--){
	        tp->key[i+1]=tp->key[i];
			tp->recptr[i+1]=tp->recptr[i];
			tp->ptr[i+1]=tp->ptr[i];
	}
	tp->key[pos]=K;
	tp->recptr[pos]=num;
	tp->ptr[pos]=ap;
	tp->keynum ++;
	if(n+1<=m-1){tp->key[n+2]=MAXKEY;
	return;}
	int j=int(ceil(double(m)/2));
	ap=new MBNode;
	ap->keynum=m-j;ap->parent =tp->parent ;
	for(i=1;i<=ap->keynum ;i++)
	{ap->key[i]=tp->key[i+j];
	ap->recptr[i]=tp->recptr[i+j];}
	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;
	K=tp->key[j];num=tp->recptr[j];
	tp->key[j]=MAXKEY;
	if(tp->parent==NULL) break;
	tp=tp->parent ;
	i=1;
	while(K>tp->key[i]) i++;
	pos=i;
}//while end
MT=new MBNode;
MT->keynum=1;
MT->parent=NULL;
MT->key[1]=K;MT->key[2]=MAXKEY;
MT->recptr[1]=num;
MT->ptr[0]=tp;MT->ptr[1]=ap;
tp->parent=ap->parent=MT;
}

void FindDelete(MBNode *mt,KeyType K,MBNode *& Tp){
	int i;
	while(mt!=NULL){
	 i=1;
	 while(K>mt->key[i]) i++;
	 if(K==mt->key[i])break;
	 mt=mt->ptr[i-1];
		}
	if(mt==NULL){Tp=NULL;return;}
	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->recptr[j-1]=mt->recptr[j];
	
	}
	mt->keynum --;
	mt->key[n]=MAXKEY;
	Tp=mt;
	return;}

	Tp=mt;
	MBNode *q=mt;
	mt=mt->ptr[i-1];
	while(mt!=NULL){
	  q=mt;
	  mt=mt->ptr[mt->keynum];
	}
     Tp->
}
bool B_Delete(MBNode*&MT,KeyType K);
void B_Travel(MBNode * MT);
int B_Depth(MBNode * MT);
int B_Count(MBNode * MT);
void ClearMBTree(MBNode *& MT);
void WriteFile(char* fname,MBNode * MT);
void ReadFile(char* fname,MBNode *& MT); 
int main(int argc, char* argv[])
{
	return 0;
}