btree.h

our homework big project

template<class T>
void Node<T>::Merge()
{	
	node* brother=m_nodeposition->brother;
	int i;

	
	if(brother->no<=N/2+1)											//两节点可以合并的说
	{
		if(m_nodeposition->p_next!=NULL)							//不是最右边的节点
		{
			node* t=m_nodeposition;

			//合并

			for(i=m_nodeposition->no;i<m_nodeposition->no+brother->no;i++)
			{
				m_nodeposition->key[i]=brother->key[i-m_nodeposition->no];
				if(Isleaf(m_nodeposition)==1)						//叶节点的赋值
					m_nodeposition->p_leaf_next[i]=brother->p_leaf_next[i-m_nodeposition->no];
				else												//非叶节点的赋值
				{
					m_nodeposition->p_node_next[i]=brother->p_node_next[i-m_nodeposition->no];
					brother->p_node_next[i-m_nodeposition->no]->p_fathernode=m_nodeposition;
				}
			}

			//处理合并后节点的其他数值

			m_nodeposition->no+=brother->no;

			if(brother->p_next!=NULL)
			{
				if(brother->p_next->p_next!=NULL)m_nodeposition->brother=brother->brother;
				else
				{
					m_nodeposition->brother=brother->brother;
					brother->brother->brother=m_nodeposition;
				}
			}
			else
				m_nodeposition->brother=m_nodeposition->p_fathernode->p_node_next[m_nodeposition->p_fathernode->no-3];

			m_nodeposition->p_next=brother->p_next;

			//重置上级节点中的数值

			node* tp=m_nodeposition->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(m_nodeposition->key[m_nodeposition->no-brother->no-1],tp->key[j])==0)
							tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(m_nodeposition->key[m_nodeposition->no-brother->no-1],tp->key[j])==0)
						tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
			}	
			
			m_nodeposition=brother->p_fathernode;
			del(brother->key[brother->no-1],t->key[t->no-1]);		//删除被删节点在父节点中的值
			delete brother;
			brother=NULL;
		}
		else														//最右边的节点
		{
			T ko=m_nodeposition->key[m_nodeposition->no-1];
			node* t=m_nodeposition;

			//合并

			for(i=brother->no;i<brother->no+m_nodeposition->no;i++)
			{
				brother->key[i]=m_nodeposition->key[i-brother->no];
				if(Isleaf(m_nodeposition)==1)
					brother->p_leaf_next[i]=m_nodeposition->p_leaf_next[i-brother->no];
				else
				{
					brother->p_node_next[i]=m_nodeposition->p_node_next[i-brother->no];
					m_nodeposition->p_node_next[i-brother->no]->p_fathernode=brother;
				}
			}
			
			//合并后其他数据处理

			brother->no+=m_nodeposition->no;
			brother->p_next=NULL;
			brother->brother=brother->p_fathernode->p_node_next[brother->p_fathernode->no-3];

			//替换上级节点中的数据

			node* tp=brother->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(brother->key[brother->no-m_nodeposition->no-1],tp->key[j])==0)
							tp->key[j]=brother->key[brother->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(brother->key[brother->no-m_nodeposition->no-1],tp->key[j])==0)
						tp->key[j]=brother->key[brother->no-1];
			}

			m_nodeposition=m_nodeposition->p_fathernode;
			del(ko,brother->key[brother->no-1]);							//删除被删节点在父节点中的值
			delete t;
			t=NULL;
		}
	}
	else																	//两节点不可以合并的说
	{
		if(m_nodeposition->p_next!=NULL)									//不是最右边的节点
		{
			//调整两个节点的数据个数

			int w=m_nodeposition->no;
			m_nodeposition->key[w]=brother->key[0];
			if(Isleaf(m_nodeposition)==1)
				m_nodeposition->p_leaf_next[w]=brother->p_leaf_next[0];
			else
			{
				m_nodeposition->p_node_next[w]=brother->p_node_next[0];
				m_nodeposition->p_node_next[w]->p_fathernode=m_nodeposition;
			}

			m_nodeposition->no++;
			brother->no--;	

			//数据前移

			for( i=0;i<brother->no;i++)
			{
				brother->key[i]=brother->key[i+1];
				if(Isleaf(m_nodeposition)==1)
					brother->p_leaf_next[i]=brother->p_leaf_next[i+1];
				else
					brother->p_node_next[i]=brother->p_node_next[i+1];
			}

			//数据转移后空位付零

			if(Isleaf(m_nodeposition)==1)
				brother->p_leaf_next[i]=NULL;
			else
				brother->p_node_next[i]=NULL;
			brother->key[i]=NULL;
			
			//替换上级节点的值

			node* tp=m_nodeposition->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(m_nodeposition->key[m_nodeposition->no-2],tp->key[j])==0)
							tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(m_nodeposition->key[m_nodeposition->no-2],tp->key[j])==0)
						tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
			}	
			
		}
		else																		//最右边的节点
		{
			//调整数据个数
			
			for(i=m_nodeposition->no;i>0;i--)										//数据后移
			{
				m_nodeposition->key[i]=m_nodeposition->key[i-1];
				if(Isleaf(m_nodeposition)==1)
					m_nodeposition->p_leaf_next[i]=m_nodeposition->p_leaf_next[i-1];
				else
					m_nodeposition->p_node_next[i]=m_nodeposition->p_node_next[i-1];
			}
			if(Isleaf(m_nodeposition)==1)
				m_nodeposition->p_leaf_next[0]=brother->p_leaf_next[brother->no-1];
			else
			{
				m_nodeposition->p_node_next[0]=brother->p_node_next[brother->no-1];
				m_nodeposition->p_node_next[0]->p_fathernode=m_nodeposition;
			}
			m_nodeposition->key[0]=brother->key[brother->no-1];

			brother->no--;
			m_nodeposition->no++;

			//数据转移后空位付零

			if(Isleaf(m_nodeposition)==1)
				brother->p_leaf_next[brother->no]=NULL;
			else
				brother->p_node_next[brother->no]=NULL;
			brother->key[brother->no]=NULL;
			
			//重置上级结点的值

			node* tp=brother->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(m_nodeposition->key[0],tp->key[j])==0)
							tp->key[j]=brother->key[brother->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(m_nodeposition->key[0],tp->key[j])==0)
					tp->key[j]=brother->key[brother->no-1];
			}
		}
	}
}


//－－－－－－－－－－－－－－－－－－－－－－显示用－－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Show()
{
	node* p=m_noderoot;
	if(p!=NULL)
	{
		
		for(;Isleaf(p)==0;)
			p=p->p_node_next[0];
		int j=0;
		m_nodehead=p->p_fathernode;
		for(;;)
		{
			j=0;
			if(p!=NULL)
			{
				while(p->p_next!=NULL)
				{
					for(int i=0;i<p->no;i++)
					{
						cout<<p->key[i];
						cout<<"    ";
						j++;
					}
					p=p->p_next;
					cout<<"\n"<<"\n";
				}
				for(int i=0;i<p->no;i++)
				{
					cout<<p->key[i];
					cout<<"    ";
					j++;
				}
				cout<<"\n"<<"\n";
				cout<<j<<"\n";
				p=m_nodehead;
				cout<<"-------------------------------------"<<"\n";
			}
			if(p!=NULL)
			{
				if(p->p_fathernode!=NULL)
					m_nodehead=p->p_fathernode;
				else
					break;
			}
			if(p==NULL)break;
		}
	
		if(p!=NULL)
		{
			for(int i=0;i<p->no;i++)
			{
				cout<<p->key[i];
				cout<<"    ";
				j++;
			}
		}
		cout<<"\n"<<"\n";
		
	}
	else
		cout<<"no data is exist";
}


template<class T>
void Node<T>::Index(string & filename,int)				//建立索引文件
{
	
	string s="data\\"+filename+".indx";
	ofstream finout(s.c_str(),ios::out|ios::binary);
	

	int total=0;
	size_t place=sizeof(int);
	for(m_nodehead=m_noderoot;m_nodehead->flag==0;m_nodehead=m_nodehead->p_node_next[0])
		;
	inode indxnode;
	node* next=m_nodehead;
	finout.seekp(sizeof(int));
	for(;next!=NULL;)
	{
		indxnode.no=next->no;
		for(int i=0;i<N;i++)
		{
			indxnode.p_leaf_next[i]=next->p_leaf_next[i];
			indxnode.key[i]=next->key[i];
		}
		finout.write((char *)&indxnode,sizeof(indxnode))<<flush;
		next=next->p_next;
		total++;
	}
	finout.seekp(0);
	finout.write((char *)&total,sizeof(int))<<flush;
/*	int x=0;
	finout.seekg(0);
	finout.read((char *)&x,sizeof(x));
	cout<<x<<endl;*/
	finout.close();

}


template<class T>
void Node<T>::Index(string & filename,float a)				//建立索引文件
{
	
	string s="data\\"+filename+".indx";
	ofstream finout(s.c_str(),ios::out|ios::binary);
	

	int total=0;
	size_t place=sizeof(int);
	for(m_nodehead=m_noderoot;m_nodehead->flag==0;m_nodehead=m_nodehead->p_node_next[0])
		;
	fnode indxnode;
	node* next=m_nodehead;
	finout.seekp(sizeof(int));
	for(;next!=NULL;)
	{
		indxnode.no=next->no;
		for(int i=0;i<N;i++)
		{
			indxnode.p_leaf_next[i]=next->p_leaf_next[i];
			indxnode.key[i]=next->key[i];
		}
		finout.write((char *)&indxnode,sizeof(indxnode))<<flush;
		next=next->p_next;
		total++;
	}
	finout.seekp(0);
	finout.write((char *)&total,sizeof(int))<<flush;
/*	int x=0;
	finout.seekg(0);
	finout.read((char *)&x,sizeof(x));
	cout<<x<<endl;*/
	finout.close();

}




template<class T>
void Node<T>::Index(string & filename,char a)				//建立索引文件
{
	int n;
	string s="data\\"+filename+".indx";
	ofstream finout(s.c_str(),ios::out|ios::binary);
	

	int total=0;
	size_t place=sizeof(int);
	for(m_nodehead=m_noderoot;m_nodehead->flag==0;m_nodehead=m_nodehead->p_node_next[0])
		;
	cnode indxnode;
	node* next=m_nodehead;
	finout.seekp(sizeof(int));
	for(;next!=NULL;)
	{
		indxnode.no=next->no;
		for(int i=0;i<indxnode.no;i++)
		{
			indxnode.p_leaf_next[i]=next->p_leaf_next[i];
			indxnode.key[i]=next->key[i];
		}
		finout.write((char *)&indxnode.no,sizeof(int));
		for(int j=0;j<indxnode.no;j++)
		{
			finout.write((char *)&indxnode.p_leaf_next[j],sizeof(int));
		}
		for(j=0;j<indxnode.no;j++)
		{
			n=strlen(indxnode.key[j])+1;
			finout.write((char *)&n,sizeof(int));
			finout.write(indxnode.key[j],n);
		}
		next=next->p_next;
		total++;
	}
	finout.seekp(0);
	finout.write((char *)&total,sizeof(int));
/*	int x=0;
	finout.seekg(0);
	finout.read((char *)&x,sizeof(x));
	cout<<x<<endl;*/
	finout.close();

}

	

template<class T>
void Node<T>::Buildtree(string & filename,int)			//从索引文件中导出建立b＋树
{
	ifstream fin;
	fin.open(("data\\"+filename+".indx").c_str(),ios::in|ios::binary);
	int total;
	int i;
	inode indxnode;
	size_t place=0;
	fin.read((char *)&total,sizeof(int));
	if(total!=0)
	{
					
		for(i=0;i<total;i++)
		{
			fin.read((char *)&indxnode,sizeof(inode));
			for(int j=0;j<indxnode.no;j++)
				Insert_node(indxnode.key[j],indxnode.p_leaf_next[j]);
		}
	}
}


template<class T>
void Node<T>::Buildtree(string & filename,float a)			//从索引文件中导出建立b＋树
{
	ifstream fin;
	fin.open(("data\\"+filename+".indx").c_str(),ios::in|ios::binary);
	int total;
	int i;
	fnode indxnode;
	size_t place=0;
	fin.read((char *)&total,sizeof(int));
	if(total!=0)
	{
					
		for(i=0;i<total;i++)
		{
			fin.read((char *)&indxnode,sizeof(fnode));
			for(int j=0;j<indxnode.no;j++)
				Insert_node(indxnode.key[j],indxnode.p_leaf_next[j]);
		}
	}
}			



template<class T>
void Node<T>::Buildtree(string & filename,char a)			//从索引文件中导出建立b＋树
{
	int n;
	ifstream fin;
	fin.open(("data\\"+filename+".indx").c_str(),ios::in|ios::binary);
	int total;
	int i;
	cnode indxnode;
	
	size_t place=0;
	fin.read((char *)&total,sizeof(int));
	if(total!=0)
	{
					
		for(i=0;i<total;i++)
		{
			fin.read((char *)&indxnode.no,sizeof(int));
			for(int j=0;j<indxnode.no;j++)
			{
				fin.read((char *)&indxnode.p_leaf_next[j],sizeof(int));
			}
			for(j=0;j<indxnode.no;j++)
			{
				indxnode.key[j]=new char;
				
				fin.read((char *)&n,sizeof(int));
				fin.read(indxnode.key[j],n);
			}
			for(j=0;j<indxnode.no;j++)
				Insert_node(indxnode.key[j],indxnode.p_leaf_next[j]);
		}
	}
}		


#endif