#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