btree.h

实现m阶B_树 （2）将线性表中的键值插入到B_树中（即建立索引）； （3）当删除和插入数据到线性表时

			p = q;//继续向上作结点条真嘎工作
			if(p == root) break;//当上升到根结点时跳出循环
		}
		else break;//不需要进行调整，跳出循环
	}
	if(!root->n)//当根结点为空时，删除根结点
	{
		p = root->ptr[0];
		delete root;
		root = p;
		root->parent = NULL;
	}
	return record;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type> 
void Btree<Type>::LeftAdjust(Mnode<Type>* p,Mnode<Type>* q,int d,int j)
{
	Mnode<Type>* p1 = q->ptr[1];//p的右兄弟
	if(p1->n>d-1)//右兄弟的空间还够，不用合并，仅作调整
	{
		p->n++;
		p->data[p->n] = q->data[1];//双亲结点相应关键码下移
		q->data[1] = p1->data[1];//右兄弟最小关键码上移到双亲结点
		p->ptr[p->n] = p1->ptr[0];//右兄弟最左指针左移
		p1->ptr[0] = p1->ptr[1];//右兄弟中剩余关键码与指针前移
		compress(p1,1);//从p1的第二个指针开始前移填补
	}
	else merge(p,q,p1,1);//p与p1合并，保留p结点
}
///////////////////////////////////////////////////////////////////////////////////////////////////////		
template <class Type> 
void Btree<Type>::RightAdjust(Mnode<Type>* p,Mnode<Type>* q,int d,int j)
{
	Mnode<Type>* p1 = q->ptr[j-1];//p的左兄弟
	if(p1->n>d-1)//空间还够，不用合并，仅作调整
	{
		for(int i=p->n;i>=1;i--)//结点p中的关键码和指针各后移一个位置，腾出空间来容纳从左兄弟p1移过来的关键码和指针
		{
			p->ptr[i+1] = p->ptr[i];
			p->data[i+1] = p->data[i];
		}
		p->ptr[1] = p->ptr[0];
		p->n++;
		p->data[1] = q->data[j];//双亲结点的相应关键码下移
		q->data[j] = p1->data[p1->n];//左兄弟的最大关键码上移到双亲结点
		p->ptr[0] = p1->ptr[p1->n];//左兄弟的最右指针右移到结点p中的指针ptr[0]
	}
	else merge(p1,q,p,1);//否则需要合并，p与p1合并，保留结点p
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
void Btree<Type>::compress(Mnode<Type>* p,int j)
{//在结点p中由第j个位置开始后面的data[]和ptr[]向前移一个位
	for(int i=j;i<p->n;i++)
	{
		p->data[i] = p->data[i+1];
		p->ptr[i] = p->ptr[i+1];
	}
	p->n--;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
void Btree<Type>::merge(Mnode<Type>* p,Mnode<Type>* q,Mnode<Type>* p1,int j)
{
	p->data[(p->n)+1] = q->data[1];//从双亲结点下移一个关键码
	p->ptr[(p->n)+1] = p1->ptr[0];//从右兄弟结点p1左移一个关键码
	for(j=1;j<=p1->n;j++)//右兄弟结点的信息复制到p中
	{
		p->data[(p->n)+1+j] = p1->data[j];
		p->ptr[(p->n)+j+1] = p1->ptr[j];
	}
	compress(q,1);//双亲结点q中的关键码与指针信息全部左移一位
	p->n = p->n+p1->n+1;//修改p中关键码个数的信息
	delete p1;//删除p1
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
int Btree<Type>::GetRecord(Type& x)
{//查找关键码为k.key的结点，返回该结点在被索引数组中的数组记录号
	Triple<Type> result = Search(x);//在树中寻找x
	if(result.tag)
	{
		cerr<<"NOT SUCH A KEY IN THE LIST!"<<endl;
		return -1;
	}
	else
		return result.r->data[result.i].record;//返回记录号
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type>
istream & operator >> ( istream & in, Btree<Type> & Tree ) 
{//本函数输入被索引数组的各项信息
	cout<<"您需要构造成B_树索引结构的数组中将包含多少个数据?请输入:"<<endl;
	in>>Tree.arraysize;
	Tree.Array = new Element[Tree.arraysize];
	char ch = 'a';
	for(int i=0;i<Tree.arraysize;i++)
	{
		Tree.Array[i].edata=ch++;
		cout<<"输入数组元素"<<i<<"的键值: ";
		in>>Tree.Array[i].key;
		Data item(Tree.Array[i].key,i);
		Tree.Insert(item);
	}
	return in;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type>
void Btree<Type>::print() 
{
    Queue< Mnode<Type>* > q;//用一个链式队列从左到右记录当前输出结点的子女，方便下一步输出
	int k;//k是记录当前输出的B_树这一层有多少个结点
	Mnode<Type>* p;
	if(root != NULL)
	{
		q.EnQueue(root);
		k = 1;
	}
	else 		
	{
		cout<<"tree empty"<<endl;
		return ;
	}
	while(!q.IsEmpty())
	{
		int z = k;//记录这一层有多少个要输出的结点
		k = 0;//k恢复为零，统计下一层有多少个要输出的结点
		for(int j=1;j<=z;j++)//本层有z个要输出的结点，循环z次
		{
			p = q.DeQueue();//从队列中退出一个元素
			cout<<'[';//输出一个结点的前示中括号
			for(int i=1;i<p->n;i++)//顺序输出本结点内的关键码及其记录号，每个关键码和记录号对用()括住，用;分隔
				cout<<'('<<p->data[i].key<<','<<p->data[i].record<<");";
			cout<<'('<<p->data[i].key<<','<<p->data[i].record<<")]";//输出结点的最后一个关键码-记录号对，并输出结点的后示中括号
			for(i=0;i<=p->n;i++)//本结点中下一层要输出的结点进队列
			{
				if(p->ptr[i] != NULL)
				{
					q.EnQueue(p->ptr[i]);
					k++;//统计下一层的结点个数
				}
			}
		}
		cout<<endl;//一层输出完毕，换行
	}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
void Btree<Type>::GetKeyRange(Type& a,Type& b)
{
	Mnode<Type> *p = root,*q;
	int i;
	while(p != NULL)//从树根开始搜索关键码大于a.key的最小关键码所在的结点，最终用q指向这个结点,i记录下大于a.key的最小关键码在q中的位置
	{
		for(i=0;i<p->n && p->data[i+1].key<a.key;i++) ;//在结点p内部搜索
		q = p;
		p = p->ptr[i];
	}

	Stack< stkNode<Type> > st;
	st.Push(stkNode<Type>(q,i));//指针q和i形成栈中结点进栈

	while(!st.IsEmpty())//当栈不空，循环输出
	{
		stkNode<Type> Cnode = st.Pop();
		if(Cnode.Node != NULL)
		{
			if(Cnode.k == -1 && Cnode.Node->ptr[0]!=NULL)//当Cnode.k为-1并且Cnode.Node的第一个指针不空
			                                             //则它的第一个指针所指的结点还有比这个结点内关键码小的关键码没输出 
			{
				stkNode<Type> node1(Cnode.Node->ptr[0],0);//ptr[0]和0配对形成栈中结点进栈
				st.Push(node1);
			}
			else if(Cnode.k == -1 && Cnode.Node->ptr[0] == NULL)//当Cnode.k为-1并且Cnode.Node的第一个指针为空
				                                                //则比这个结点内关键码小的所有关键码都已经输出，直接输出这个结点内的关键码 
			{
				stkNode<Type> node2(Cnode.Node,0);
				st.Push(node2);
			}
			else if(Cnode.k<Cnode.Node->n && Cnode.Node->data[Cnode.k+1].key<b.key)//否则
			{
				cout<<Cnode.Node->data[Cnode.k+1].key<<' ';//输出当前结点中的第k+1个关键码
				if(Cnode.Node->ptr[Cnode.k+1] != NULL)//如果第k+1个指针不空,则准备将下一个指针进栈
				{
					stkNode<Type>* node3;
					if(Cnode.k+1 == Cnode.Node->n)//如果这个第k+1个指针是结点的最后一个指针
					{
						node3 = new stkNode<Type>(Cnode.Node->ptr[Cnode.k+1],-1);//设进栈结点的k为-1标志它是当前结点的最后一个指针
						st.Push(*node3);
					}
					else
					{	
						node3 = new stkNode<Type>(Cnode.Node->ptr[Cnode.k+1],0);//否则设进栈结点的k为0,标志它是非最后指针的普通结点
					    st.Push(*node3);
					}
				}
				else//否则如果第k+1个指针空,则当前结点没有子女结点
				{
					for(int j=Cnode.k+2;j<=Cnode.Node->n && Cnode.Node->data[j].key<b.key;j++)//将这个结点内比b.key小比a.key大的关键码都输出
						cout<<Cnode.Node->data[j].key<<' ';
					if(j>Cnode.Node->n)//如果j>Cnode.Node->n,表示当前结点内的全部关键码都已经输出,其祖先结点还可能有要输出的关键码,所以将其父母结点进栈
					{
						Mnode<Type>* s = Cnode.Node->parent;
						for(int c=0;s->ptr[c]!=Cnode.Node;c++);//寻找当前结点是其父母的第几个子女
						stkNode<Type> node4(s,c);
						st.Push(node4);
					}
					
				}
			}
			else//否则当前结点没有符合要求的关键码,在其父母结点中寻找
			{
				Mnode<Type>* t = Cnode.Node->parent;
				if(t != NULL)//如果有父母结点才执行
				{
					for(int d=0;t->ptr[d] != Cnode.Node;d++) ;//寻找当前结点是其父母的第几个子女
					stkNode<Type> node5(t,d);
					st.Push(node5);
				}
			}
		}
	}
	cout<<endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////