B-树查找算法

[c]代码库

#define m 5 /*B 树的阶，暂设为5*/
typedef struct NODE
{
	int keynum; /* 结点中关键码的个数，即结点的大小*/
	struct NODE *parent; /*指向双亲结点*/
	KeyTypekey[m+1]; /*关键码向量，0 号单元未用*/
	struct NODE *ptr[m+1]; /*子树指针向量*/
	record *recptr[m+1]; /*记录指针向量*/
} NodeType; /*B 树结点类型*/
typedef struct
{
	NodeType *pt; /*指向找到的结点*/
	int i; /*在结点中的关键码序号，结点序号区间[1…m]*/
	int tag; /* 1:查找成功，0:查找失败*/
} Result; /*B 树的查找结果类型*/
Result SearchBTree ( NodeType *t,KeyType kx )
{ /*在m 阶B 树t 上查找关键码kx，反回(pt,i,tag)。若查找成功，则特征值tag=1，*/
	/*指针pt 所指结点中第i 个关键码等于kx；否则，特征值tag=0,等于kx 的关键码记录*/
	/*应插入在指针pt 所指结点中第i 个和第i+1 个关键码之间*/
	p=t;
	q=NULL;
	found=FALSE;
	i=0; /*初始化，p 指向待查结点，q 指向p 的双亲*/
	while ( p&&!found )
	{
		n=p->keynum;
		i=Search ( p,kx ); /*在p-->key[1…keynum]中查找*/
		if ( i>0&&p->key[i]= =kx ) found=TRUE; /*找到*/
		else {q=p; p=p->ptr[i];}
	}
	if ( found ) return ( p,i,1 ); /*查找成功*/
	else return ( q,i,0 ); /*查找不成功，反回kx 的插入位置信息*/
}