find.h

一个B-树实现与编辑

Status Search(BTree &p,int k)         //查找k在p中的位置
{
	int j;
	
	for(j=1;j<=p->keynum&&k>=p->key[j];j++);
	return(j-1);
}   //Search


Result SearchBTree(BTree T,int k)
{
	//在m阶B-树T上查找关键字，返回结果(pt,i,tag).若查找成功，则特征值tag=1
	//指针pt所指结点中第i个关键字等于K;否则返回特征值tag=0,等于k的关键字应插入
	//指针pt指的结点第i和第i+1个关键字之间
	BTree p,q;
	bool found;
	int i;
	Result v;
	p=T;q=NULL;found=FALSE;i=0;
	while(p&&!found)
	{
		i=Search(p,k);    //在p->recptr[1...keynum]中查找,i使p->key[i]<=k<p->key[i+1]
		if(i>0&&p->key[i]==k)found=TRUE;    //找到时，令found=TRUE
		else
		{q=p;p=p->ptr[i];/*没找到时，走向第i棵子树*/
		}
	}//while
		if(found)              //找到时
		{
			v.pt=p;
			v.i=i;
			v.tag=1;
			return(v);
		}
		else                 //没有找到时
		{
			v.pt=q;
			v.i=i;
			v.tag=0;
			return(v);
	}
}    //SearchBTree