本文共 3221 字，大约阅读时间需要 10 分钟。

BinNode模板类：

#include 
   
    #define BinNodePosi(T) BinNode
    
     *#define stature(p) ((p) ? (p)->height : -1)typedef enum {RB_RED, RB_BLACk} RBColor;template 
     
       struct  BinNode{    T data;    BinNodePosi(T) parent; BinNodePosi(T) lc; BinNodePosi(T) rc;    int height;     int npl;    RBColor color;    BinNode():        parent(NULL), lc(NULL), rc(NULL), height(0), npl(1),color(RB_RED){}    BinNode( T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL,              int h = 0, int l = 1, RBColor c = RB_RED) :        data(e), parent(p), lc(lc), rc(rc), height(h), npl(l), color(c) {}    int size();    BinNodePosi(T) insertAsLC( T const& );    BinNodePosi(T) isnertAsRC( T const& );    BinNodePosi(T) succ();    template 
      
        void travLevel( VST& );    template 
       
         void travPre  ( VST& );    template 
        
          void travIn ( VST& ); template 
         
           void travPost ( VST& ); bool operator< ( BinNode const& bn) { return data < bn.data; } bool operator== ( BinNode const& bn) { return data == bn.data; }};
         
        
       
      
     
    
   

快捷接口：

#define IsRoot(x) (!(x).parent)#define IsLChild(x) (!IsRoot(x) && (&(x) == (x).parent->lc ))#define IsRChild(x) (!IsRoot(x) && (&(x) == (x).parent->rc ))#define HasParent(x) ( !IsRoot(x) )#define HasLChild(x) ( (x).lc )#define HasRChild(x) ( (x).rc )#define HasChild(x) (HasLChild(x) || HasRChild(x))#define HasBothChild(x) (HasLChild(x) && HasRChild(x))#define IsLeaf(x) ( !HasChild(x) )#define sibiling(p) (IsLChild(*p) ? (p)->parent->rc : (p)->parent->lc)#define uncle(x) (IsLChild(*(x)->parent) ? (x)->parent->parent->rc ：(x)->parent->parent->lc)#define FromParentTo(x) (IsRoot(x) ? _root : (IsLChild(x) ? (x).parent->lc : (x).parent->rc))

size():

template 
   
     int BinNode
    
     ::size(){    int s = 1;    if (lc) s += lc->size;    if (rc) s += rc->size;    return s;}
    
   

BinTree模板类：

#include "BinNode.h"#include 
   
    template 
    
      class BinTree {protected:    int _size; BinNodePosi(T) _root;    virtual int updateHeight( BinNodePosi(T) x );    void updateHeightAbove( BinNodePosi(T) x );public:    BinTree() : _size(0), _root(NULL){}    ~BinTree() { if ( 0 < _size) remove(_root); }    int size() const { return _size; }    bool empty() const { return !_root; }    BinNodePosi(T) root() const { return _root; }    BinNodePosi(T) insertAsRoot( T const& e );    BinNodePosi(T) insertAsLC( BinNodePosi(T) x, T const& e );    BinNodePosi(T) insertAsRC( BinNodePosi(T) x, T const& e );    BinNodePosi(T) attachAsLC( BinNodePosi(T) x, BinTree
     
      * &T );    BinNodePosi(T) attachAsRC( BinNodePosi(T) x, BinTree
      
       * &T );    int remove( BinNodePosi(T) x );    BinTree
       
        * secede( BinNodePosi(T) x );    template 
        
          void travLevel( VST& visit) { if(_root) _root->travLevel( visit ); } template 
         
           void travPre( VST& visit) { if(_root) _root->travPre( visit ); } template 
          
            void travPost( VST& visit) { if(_root) _root->travPost( visit ); } template 
           
             void travIn( VST& visit) { if(_root) _root->travIn( visit ); } bool operator< (BinTree
            
              const& t) { return _root && t._root && lt( _root, t._root); } bool operator== (BinTree
             
               const& t) { return _root && t._root && (_root == t._root); } };