谁能写这个二叉搜索树结合AVL树的实现文件啊

jerryzheng

前面一个贴被封了，不好意思！其实我只是问了一句“这里没有能解决的高手吗？”，当然有高手也不一定非要来解答这个问题，我自己并非完全不会写，但写得不好！这种拿到网上来问人的途径也许有人会有异议，如果能请到一个老师我愿意付出任何代价学习我想学习和不懂的知识，但是没找到。不回答的人我没有任何权利说什么，但是真的渴望有人肯赐教！我觉得我能知道怎么写好这个东东，也算是大有收获了！

#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
};