B树C++代码:查找程序

前言：
因为最近需要写个数据结构完成作业，选了个B树。首先需要写个头文件将数据结构中的B树内容知识装在这个头文件上，主程序才能用这个数据结构。然后就看了书，写了一点点这个代码。后续还有插入、删除等等的操作。

B树C 代码之查找程序：

// An highlighted block
#include <stdlib.h>
using namespace std;
#define m 3 
#define ElemType char;

//定义一个B树的一个节点，节点里包含这些东西 
typedef struct BNode{
	BNode *parent;         //父指针 
	int keynum;            //有多少个数据 
	ElemType data[m 1];       // 真正的数据域，但data【0】始终不用 
	BNode *ptr[m 1];    // 连接他们孩子的指针 
}*Btree;

//定义一个查找结果的结构体 
typedef struct result{
	BNode* p;      //代表该树的哪个结点 
	int i ;         //代表该结点的第几个部分（数据或指针块） 
	int tag;        //代表查找的结果，tag=1也就是该树有你要查找的数据 
};


//定义一个函数“search” ，该函数返回的是p结点（也就是树中的某个结点）的第i个数据块，或叫指针。留后面使用 
int search(Btree p,ElemType key ){
	int i = 0;                                    // 先定义出来的i，共后面for 使用 
	if (key<p->data[1]){return 0 ;}                       // 关键字对比第一个数据，小了就返回i=0  
	if (key>=p->data[p->keynum]){return p->keynum;}       //关键字对比该结点的最后一个数据，大了就返回keynum 
	for (i=0;i<p->keynum;i  ){                            // 若上面连个if 都没有，就说明要查找的数据在中间。通过挪动i ，在i 和 i 1 中对比，直到找到key 在 i i 1区间的 
		if (key>p ->data[i]&&key<=p->data[i 1]){
			return i;
		}
	}
}        //这个函数返回的是i的型，因为ptr【i】可以指向下一个结点，继续检测你要查找的数据 

// 真正的查找函数 Search，返回的是刚才定义过的result结构体 
result Search(Btree T ,ElemType key){
	Btree p=T,q =NULL;                               //首先定义p 和q 中间指针变量 
	bool found = false;                              //定义一个查找的bool 
	int i = 0;                                        //初始i 
	result r;                                        //生成结构体 r 
	while (p&&!found)                                //循环查找 
	{
		i= search(p,key);                               //调用search ，返回i （第i个结点） 
		if (i>0&&key == p->data[i]){found =true;}        // 对比 
		else{
			q=p;p=p->ptr[i];                             //没在p结点找到，找子结点 
		}
		if(found){r.p=p;r.i=i;r.tag=1;}       //查找成功 
		else{r.p=q;r.i=i;r.tag=0;}         //查找没成功（但是，这是插入位置） 
	}
	return r;	
}

;

这篇好文章是转载于：学新通技术网