atree.h

来自「CxxTester是一个用于C＋＋代码的通用测试框。它支持测试库系统、有一套方法」· C头文件 代码 · 共 102 行

//----------------------------------------------------------------------//
//                             COPYRIGHT (C) 2002                       //
//                                                                      //
// ATree.h                                                              //
//                                                                      //
// include file for avl-tree implementation                             //
//----------------------------------------------------------------------//

#ifndef ATree_h
#define ATree_h 1

#define MAX_ELEMS       100    //     number of items allocated at once //
#define MEMORY_FAULT    1      //                         avl-errorcode //
#define BALANCE_FAULT   2      //                         avl-errorcode //



//----------------------------------------------------------------------//
// pre declaration of classes                                           //
//----------------------------------------------------------------------//

class AVL_ITEM;
class LOCAL_DAT;
class AVL_TREE;



//----------------------------------------------------------------------//
//  avl node structure                                                  //
//----------------------------------------------------------------------//

class AVL_ITEM
{
    public:

    LOCAL_DAT       *d_item; // pointer from avl node to user data item //
    AVL_ITEM        *left;   //   left son pointer or next smaller item // 
    AVL_ITEM        *right;  //  right son pointer or next greater item //
    AVL_ITEM        *pre;    //                       pointer to parent //
    signed char     balance; //          balance factor of the avl node //
    unsigned        l_son:1; //        son or next smaller. 1 means son //
    unsigned        r_son:1; //        son or next greater. 1 means son //
};



//----------------------------------------------------------------------//
//  basic class for user data                                           //
//----------------------------------------------------------------------//

class LOCAL_DAT
{
    public:

    AVL_ITEM *avl;                         //       pointer to avl node //
    LOCAL_DAT *avl_nextupper();            //             list function //
    LOCAL_DAT *avl_nextlower();            //             list function //
};



//----------------------------------------------------------------------//
// avl tree class                                                       //
//----------------------------------------------------------------------//

class AVL_TREE
{
    private:

    AVL_ITEM *root;                        //      root of the avl-tree //
    AVL_ITEM *start;                       // actual available mem item //
    AVL_ITEM *end;                         //   last available mem item //
    AVL_ITEM *list;                        //  list of allocated blocks //
    AVL_ITEM *avl_new();                   //       avl node allocating //
    void avl_free(AVL_ITEM*   );           //     avl node deallocating //
    void avl_bal(AVL_ITEM*    );           //        avl tree balancing //
    AVL_ITEM *avl_rr(AVL_ITEM*);           //     single rotation right //
    AVL_ITEM *avl_ll(AVL_ITEM*);           //      single rotation left //
    AVL_ITEM *avl_rl(AVL_ITEM*);           //       rotation right-left //
    AVL_ITEM *avl_lr(AVL_ITEM*);           //       rotation left-right //
    void avl_init(LOCAL_DAT*,AVL_ITEM**);  //     avl node initialising //


    public:

    virtual ~AVL_TREE();                   //       avl_tree destructor //
    AVL_TREE();                            //      avl_tree constructor //
    LOCAL_DAT* avl_lowest() const;         //    search for lowest data //
    LOCAL_DAT* avl_highest() const;        //   search for highest data //
    void avl_clear();                      //           delete avl tree //
    void avl_push(LOCAL_DAT*);             //        avl node insertion //
    void avl_pull(LOCAL_DAT*);             //      deletion of avl node //
    LOCAL_DAT* avl_join(LOCAL_DAT*);       //        avl node insertion //
    LOCAL_DAT *avl_search(LOCAL_DAT& ) const; //   data search function // 
    LOCAL_DAT *avl_loweq (LOCAL_DAT& ) const; // region search function //
    LOCAL_DAT *avl_uppeq (LOCAL_DAT& ) const; // region search function // 
    virtual int compare(LOCAL_DAT*, LOCAL_DAT*) const = 0;// p. virtual //
    void avl_handle(void(*)(LOCAL_DAT*,void*),void*);  //  travers func //   
};

#endif