论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2004-06-24 10:46 |只看该作者 |倒序浏览

#define KEY_STRING_TYPE  0
#define KEY_DATA_TYPE 1

typedef char*  LPBST_ITEM;
typedef char*  LPBST_KEYVALUE;

//callback function called when travelling tree
//input: pitem = the item pointer
//input: lpParam =  the user_defined data
typedef BOOL (*TraverseCallBack)(LPBST_ITEM pitem,char* lpParam,int paramsize);

//callback function to get the item's key value pointer
//input: pitem = the item pointer
//return: pionter to key value of the item ,it's value is used by compare function's keybuf2 parameter
typedef LPBST_KEYVALUE (*GetKeyValueCallBack)(LPBST_ITEM pitem);

//order mode
enum TraverseOrder { Ascending=0,Descending,ParentFirst,ParentLast };

/********************* C L A S S  D E F I N A T I O N ******************/
class CBSTree
{
private:
struct BSNODE//binary tree node
{
   LPBST_ITEM  pitem;//the item data pointer
   short  Factor;//balance factor
   BSNODE *LCH;//left child
   BSNODE *RCH;//right child
};
private:
void    DeleteTree();
void    DeleteTree(BSNODE *pNode); // delete a tree

int    InsertNode(BSNODE *n,LPBST_KEYVALUE pkeyvalue);//insert a node
int    InsertNoBalance(BSNODE* pNode);
// void    Remove(BSNODE *pNode,LPBST_KEYVALUE pkeyvalue); // remove a node from tree
LPBST_ITEM    Remove(BSNODE *pNode,LPBST_KEYVALUE pkeyvalue); // remove a node from tree
void*    Search( BSNODE* pNode,LPBST_KEYVALUE pkeyvalue);//search a node from a tree
void* CheckPoint(BSNODE *pNode);//check the tree's node balance is  validity

//travel a tree
void    DoTraverse_Ascending(BSNODE* pNode,char* lpParam,int paramsize);//general a  ascending array from a binary tree
void    DoTraverse_Descending(BSNODE* pNode,char* lpParam,int paramsize);//general a  Descending array from a binary tree
void    DoTraverse_ParentFirst(BSNODE* pNode,char* lpParam,int paramsize);//general a  ParentFirst array from a binary tree
void    DoTraverse_ParentLast(BSNODE* pNode,char* lpParam,int paramsize);//general a  ParentLast array from a binary tree

//for reindex
void    InsertFromOrderedArray(int low, int hi);//general a balance tree from a ordered array
void    OrderedArray(BSNODE* pNode);//put all tree's node into a array
int    cal_balance(BSNODE *pNode);
int    Cal_Balance();//calculate all node balance factor of root tree

int    compare(LPBST_KEYVALUE keybuf1,LPBST_KEYVALUE keybuf2);
int    height(BSNODE *pNode);
public:

//input: getkvfunc = callback function to get the item's key value pointer
//input: keyvaluetype = the item key value 's data type
//                   0: is string;  1 is signed char|short|int|long
// this value only used  for deciding compare mode between two key value
CBSTree(GetKeyValueCallBack getkvfunc,BYTE keyvaluetype,HWND hwnd = NULL);

~CBSTree();

//travel root tree
//input: to =  is the order type
//input: func = callback function called when reach a node
void Traverse(TraverseOrder order, TraverseCallBack func,char* lpParam = NULL,int paramsize = 0);//general a  ordered array from a binary tree

// rebuild avl tree but not release the node ,it is thread safety
//return: if return 1 then successful
//    if return 0 then failed
//       if return -1 then fatal failed ,the index has destroyed.
int OptimizeIndex();//ReBuildIndex(); //rebalance root tree from  sorted array element

//check the balance factor validity of  all the node on the root tree
//return : the first node's item pointer which balance factor is invalid.
LPBST_ITEM Verify(); //balance tree from  sorted array element

/* Inserts |item| into |tree| ,it is thread safety
input: pitem =  the item pointer
input: pkeyvalue = the item's key value pointer
return: If a duplicate item key value is found in the tree,return 0 without insert it.
   if insert successfully return 1
   else return < 0
*/
int Insert(LPBST_ITEM pitem,LPBST_KEYVALUE pkeyvalue);//insert a node

//remove node from root tree  by key value,it is thread safety
//input: pkeyvalue =  is the item's key value pointer
// void Remove(LPBST_KEYVALUE pkeyvalue); // remove a node by key value
LPBST_ITEM Remove(LPBST_KEYVALUE pkeyvalue); // remove a node by key value

//find the item pointer by a key value
//input: pkeyvalue = is the searched key value pointer
//return: if found then return the item pointer
//    else return NULL
LPBST_ITEM    Find( LPBST_KEYVALUE pkeyvalue);//search a node from a tree
int    GetHeight();//get the height of root tree
private:
GetKeyValueCallBack getkeyvalueFunc;//callback function to get the item's key value pointer
BYTE    keytype; //  the key data type 0: is string;  1 is (signed or unsigned) char|short|int|long
BSNODE  *Root;  //the tree root
BSNODE** mBalArray; // Array of pointers to all nodes of tree
// These two thingies are temp. stuff used in balancing.
int    mBalArrayCount; //the element count of the array
void*    mParam;//the tree pointer for balance by a ordered array
TraverseCallBack mFunc;//the function for balance by a ordered array
CRITICAL_SECTION CriticalSection; //for resolve conflic when changing node of tree

public:
int    mCount;//the tree node count
HWND    hWnd;//handle windows message
};