btree.h

其他人不需帐号就可自由下载此源码 其他人不需帐号就可自由下载此源码

#ifndef __BTREE_H__
#define __BTREE_H__

#include <windows.h>

/*

定义关键字类型

*/
#if !defined(BSTREE_KEY) 

	typedef unsigned long  BSTREE_KEY;

#endif



/*

B-树的实现(BSTREE)

*/

#ifdef __cplusplus
extern "C" {
#endif


#define DEF_BSTREE_STEPS 3   //M阶B-树

#pragma warning( disable : 4996)

	
	typedef struct BSTREE_RECORD {

		void   *ptr;//指向内容指针

	} BSTREE_RECORD;

	typedef struct BSTREE_NODE {
		
		BSTREE_NODE    *parent;                      //指向双亲节点
		BSTREE_KEY      key[DEF_BSTREE_STEPS + 1];   //关键字向量(0号单元没有用)
		BSTREE_NODE    *ptr[DEF_BSTREE_STEPS + 1];   //子树向量
		BSTREE_RECORD  *rec[DEF_BSTREE_STEPS + 1];   //记录指针向量(0号单元没有使用)
		int             keynum;                      //节点中关键字个数

	} BSTREE_NODE;
	

	typedef struct BSTREE_RESULT { 
		
		BSTREE_NODE *ptr; //指向找到的节点
		int         i;    //1..m在节点中关键字序号
		int         tag;  //1:查找成功;0查找失败

	} BSTREE_RESULT;
	


	/*

	在M阶t树上查找关键字k,返回结果BSTREE_RESULT(ptr, i, tag),查找成功
	tag = 1,ptr指向找到节点i个关键字等于k;否则特征值tag=0,等于k的值应
	当插入在指针ptr所指结点中第i和第i+1个关键字之间

	*/
	BSTREE_RESULT bs_search_tree(BSTREE_NODE *t, BSTREE_KEY k);

	
	/*

	在m阶B-树T上结点*q的key[i]与key[i+1]之间插入关键字K的指针r。若引起
	结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B-树。

	*/
	int  bs_insert_tree(BSTREE_NODE *&t, BSTREE_KEY k, BSTREE_RECORD *r, BSTREE_NODE *q, int i);

	
	
	/*

	从B-树root中删除关键k,若在一个节点中删除指定关键字，不再有其他关键字，则删除该节点

	*/
	int  bs_delete_tree(BSTREE_NODE * &root, BSTREE_KEY k) ;

#ifdef __cplusplus
}
#endif

#endif