bptree.h

our homework big project

		for(m_nodeposition=m_noderoot;m_nodeposition!=end;m_nodeposition=m_nodeposition->p_next)
		{
			for(int j=0;j<m_nodeposition->no;j++)
				no.push_back(m_nodeposition->p_leaf_next[j]);
		}
		for(int x=0;x<=i;x++)
			no.push_back(m_nodeposition->p_leaf_next[x]);
		
	}
	return no;
}


//－－－－－－－－－－－－－－－－寻找<－－－－－－－－－－－－－－－－－


template<class T>
vector<int> Node<T>::Ssearch(T & key)
{
	bool f=false;int i;
	node* end;
	vector<int> no;
	Leaf_dfind(key);
	for(m_nodehead=m_noderoot;m_nodehead!=NUll;m_nodehead=m_nodehead->p_node_next[0])
		;
	for(i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
			{f=true;end=m_nodeposition;break;}
	}
	if(f==ture)
	{
		for(m_nodeposition=m_noderoot;m_nodeposition!=end;m_nodeposition=m_nodeposition->p_next)
		{
			for(int j=0;j<m_nodeposition->no;j++)
				no.push_back(m_nodeposition->p_leaf_next[j]);
		}
		for(int x=0;x<i;x++)
			no.push_back(m_nodeposition->p_leaf_next[x]);
		
	}
	return no;
}

//－－－－－－－－－－－－－－－数据插入函数－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Insert_node(T & key,const int & n)
{
	Leaf_ifind(key);
	bool f=false;	

	if(m_total==0)										//当数据被删完时的情况           
	{
		
		m_noderoot->key[0]=key;
		m_noderoot->p_leaf_next[0]=n;
		m_noderoot->no=1;
		m_total=1;
	}
	else												//还有数据
	{
		for(int i=0;i<m_nodeposition->no;i++)			//插入数据比最大值小，找到在叶节点中的位置
		{
			if(compare(key,m_nodeposition->key[i])==-1)	//找到后，后面的数据后移
			{
				for(int j=m_nodeposition->no;j>i;j--)
				{
					m_nodeposition->key[j]=m_nodeposition->key[j-1];
					m_nodeposition->p_leaf_next[j]=m_nodeposition->p_leaf_next[j-1];
				}
				m_nodeposition->key[i]=key;
				m_nodeposition->p_leaf_next[i]=n;
				f=true;
				break;
			}
		}
		if(f==false)										//数据比最大值大，直接插到最后
		{
			m_nodeposition->key[m_nodeposition->no]=key;
			m_nodeposition->p_leaf_next[m_nodeposition->no]=n;
		}
		if(m_nodeposition->no<N-1)							//节点未满，节点的数据个数＋1后退出
			m_nodeposition->no+=1;
		else												//节点已满，进行节点分裂		
			Resize_leaf();
		m_total++;
	}
	m_opf=true;
}


//－－－－－－－－－－－－－－分裂叶节点－－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Resize_leaf()
{

	bool f=false;
	node* new_node=new node;

	Ini(new_node);

	//叶节点分裂

	
	//分为两个叶节点
	
	for(int i=N/2+1;i<N;i++)
	{
		new_node->key[i-N/2-1]=m_nodeposition->key[i];
		new_node->p_leaf_next[i-N/2-1]=m_nodeposition->p_leaf_next[i];
	}

	//处理横向连接及其他数值

	if(m_nodeposition->p_next!=NULL)					
	{
		if(m_nodeposition->p_next->p_next!=NULL)
		{
			new_node->brother=m_nodeposition->brother;
			m_nodeposition->brother=new_node;
		}
		else
		{
			new_node->brother=m_nodeposition->brother;
			m_nodeposition->brother=new_node;
			m_nodeposition->p_next->brother=new_node;
		}
	}
	else
	{
		m_nodeposition->brother=new_node;
		new_node->brother=m_nodeposition;
	}
	new_node->p_next=m_nodeposition->p_next;
	m_nodeposition->p_next=new_node;
	new_node->flag=1;
	m_nodeposition->no=N/2+1;
	new_node->no=N/2;

	for(i=N/2+1;i<N;i++)						//数据以后复位为NULL
	{
		m_nodeposition->key[i]=NULL;
		m_nodeposition->p_leaf_next[i]=NULL;
	}

	//自己是根结点的情况

	if(Isroot(m_nodeposition)==1)
	{
		node* root=new node;
		Ini(root);
		root->key[0]=m_nodeposition->key[N/2];
		root->key[1]=new_node->key[N/2-1];
		root->p_node_next[0]=m_nodeposition;
		root->p_node_next[1]=new_node;
		root->no=2;
		m_nodeposition->p_fathernode=new_node->p_fathernode=root;
		m_noderoot=root;
	}

	//非根结点的情况

	else
	{
		node* po=m_nodeposition->p_fathernode;
		for(i=0;i<po->no;i++)
		{
			if(compare(new_node->key[N/2-1],po->key[i])==0)
			{
				f=true;
				for(int j=po->no;j>i;j--)
				{
					po->key[j]=po->key[j-1];
					po->p_node_next[j]=po->p_node_next[j-1];
				}
				po->key[i]=m_nodeposition->key[N/2];
				po->p_node_next[i]=m_nodeposition;
				po->p_node_next[i+1]=new_node;
			}
			if(f==true)	break;
		}
		//父节点数据未满
		if(m_nodeposition->p_fathernode->no<N-1)
		{
			m_nodeposition->p_fathernode->no++;
			new_node->p_fathernode=m_nodeposition->p_fathernode;
		}

		//父节点数据已满
		else
		{
			m_nodeposition=m_nodeposition->p_fathernode;
			Resize_nleaf();//分裂非叶节点（涉及递归）
		}
	}
}




//－－－－－－－－－－－－－－分裂非叶节点－－－－－－－－－－－－－－－



template<class T>
void Node<T>::Resize_nleaf()
{
	node* new_node=new node;
	Ini(new_node);//初始化

	//把节点分开
	for(int i=N/2+1;i<N;i++)
	{ 
		new_node->key[i-(N/2)-1]=m_nodeposition->key[i];
		new_node->p_node_next[i-(N/2)-1]=m_nodeposition->p_node_next[i];
	}

	//处理横向连接问题及其他数值

	if(m_nodeposition->p_next!=NULL)
	{
		if(m_nodeposition->p_next->p_next!=NULL)
		{
			new_node->brother=m_nodeposition->brother;
			m_nodeposition->brother=new_node;
		}
		else
		{
			new_node->brother=m_nodeposition->brother;
			m_nodeposition->brother=new_node;
			m_nodeposition->p_next->brother=new_node;
		}
	}
	else
	{
		m_nodeposition->brother=new_node;
		new_node->brother=m_nodeposition;
	}
	new_node->p_next=m_nodeposition->p_next;
	m_nodeposition->p_next=new_node;
	m_nodeposition->no=N/2+1;
	new_node->no=N/2;

	for(i=N/2+1;i<N;i++)						//移动后复位为NULL
	{
		m_nodeposition->key[i]=NULL;
		m_nodeposition->p_node_next[i]=NULL;
	}
	for(int x=0;x<N/2+1;x++)					//把子节点中的节点的父节点改过来						
	{
		m_nodeposition->p_node_next[x]->p_fathernode=m_nodeposition;
	}
	for(x=0;x<N/2;x++)							//－－－－－－－－－－－－－－－－		
	{
		new_node->p_node_next[x]->p_fathernode=new_node;
	}

	//根据自己是不是根结点

	if(Isroot(m_nodeposition)==1)				//是根结点de情况
	{
		node* root=new node;
		Ini(root);
		root->key[0]=m_nodeposition->key[N/2];
		root->key[1]=new_node->key[N/2-1];
		root->p_node_next[0]=m_nodeposition;
		root->p_node_next[1]=new_node;
		root->no=2;
		m_nodeposition->p_fathernode=new_node->p_fathernode=root;
		m_noderoot=root;
	}

	else										//非根结点的情况
	{
		bool f=false;

		//把数据插入父节点

		node* po=m_nodeposition->p_fathernode;
		for(i=0;i<po->no;i++)
		{
			if(compare(new_node->key[N/2-1],po->key[i])==0)
			{
				f=true;
				for(int j=po->no;j>i;j--)
				{
		
					po->key[j]=po->key[j-1];
					po->p_node_next[j]=po->p_node_next[j-1];
				}
				po->key[i]=m_nodeposition->key[N/2];
				po->p_node_next[i]=m_nodeposition;
				po->p_node_next[i+1]=new_node;
			}
			if(f==true)break;
		}

		//根据父节点的数据个数

		if(m_nodeposition->p_fathernode->no<N-1)		//数据未被填满
		{
			m_nodeposition->p_fathernode->no++;
			new_node->p_fathernode=m_nodeposition->p_fathernode; 
		}
		else											//数据已经填满
		{
			m_nodeposition=m_nodeposition->p_fathernode;
			Resize_nleaf();
		}
	}
}


//－－－－－－－－－－－－－－删除叶节点数据－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Del_data(T & ckey)
{
	bool f=false;

	Leaf_dfind(ckey);									//所在的叶节点
	for(int i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
		{f=true;break;}
	}
	T x=m_nodeposition->key[i];
	
	if(f==true)											//数据存在
	{
		del(x);
	}
	else cout<<"the date isn't exist\n";
	m_opf=true;
}


//－－－－－－－－－－－－－－－－删－除－－－－－－－－－－－－－－－－


template<class T>
void Node<T>::del(T & k)
{
	bool f=false;

	for(int i=0;i<m_nodeposition->no;i++)			//找到在节点中的位置
	{
		if(compare(k,m_nodeposition->key[i])==0)break;
	}
	if(compare(m_nodeposition->key[i],m_nodeposition->key[i+1])==0)i++;

	if(Isroot(m_nodeposition)==1)					//根结点情况
	{
		if(Isleaf(m_nodeposition)==1)				//叶节点
		{
			if(m_nodeposition->no>1)				//多个数据
			{
				for(;i<m_nodeposition->no-1;i++)
				{
					m_nodeposition->key[i]=m_nodeposition->key[i+1];
					m_nodeposition->p_leaf_next[i]=m_nodeposition->p_leaf_next[i+1];
				}
				m_nodeposition->key[i]=NULL;
				m_nodeposition->p_leaf_next[i]=NULL;
				m_nodeposition->no--;
				m_total--;
			}
			else									//只有一个数据，直接删除
			{
				m_total=0;
				m_nodeposition->no=0;
				m_nodeposition->key[0]=NULL;
				m_nodeposition->p_leaf_next[0]=NULL;
			}
		}
		else										//非叶节点
		{
			for(;i<m_nodeposition->no-1;i++)
			{
				m_nodeposition->key[i]=m_nodeposition->key[i+1];
				m_nodeposition->p_node_next[i]=m_nodeposition->p_node_next[i+1];
			}
			m_nodeposition->key[i]=NULL;
			m_nodeposition->p_node_next[i]=NULL;
			m_nodeposition->no--;
			if(m_nodeposition->no<2)				//只剩两个数据时
			{
				m_noderoot=m_noderoot->p_node_next[0];
				delete m_noderoot->p_fathernode;
				m_noderoot->p_fathernode=NULL;
			}
		}
	}
	else											//非根结点
	{
		if(Isleaf(m_nodeposition)==1)				//叶节点
		{
			for(;i<m_nodeposition->no-1;i++)
			{
				m_nodeposition->key[i]=m_nodeposition->key[i+1];
				m_nodeposition->p_leaf_next[i]=m_nodeposition->p_leaf_next[i+1];
			}
			m_nodeposition->key[i]=NULL;
			m_nodeposition->p_leaf_next[i]=NULL;
			m_total--;
		}
		else										//非叶节点
		{
			for(;i<m_nodeposition->no-1;i++)
			{
				m_nodeposition->key[i]=m_nodeposition->key[i+1];
				m_nodeposition->p_node_next[i]=m_nodeposition->p_node_next[i+1];
			}
			m_nodeposition->key[i]=NULL;
			m_nodeposition->p_node_next[i]=NULL;
		}
		m_nodeposition->no--;
		node* tp=m_nodeposition->p_fathernode;
		for(;Isroot(tp)==0;)
		{
			for(int j=0;j<tp->no;j++)
			{
				if(compare(k,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(k,tp->key[j])==0)
				tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
		}
	
		if(m_nodeposition->no<N/2)					//需要调整的
		{
			Merge();
		}
	}
}


//－－－－－－－－－－－－－重载删除－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－在合并调整中用－－－－－－－－－－－－－


template<class T>
void Node<T>::del(T & k,const T & t)
{
	bool f=false;

	for(int i=0;i<m_nodeposition->no;i++)						//找到在节点中的位置
	{
		if(compare(k,m_nodeposition->key[i])==0)break;
	}
	if(compare(m_nodeposition->key[i],m_nodeposition->key[i+1])==0)i++;