0001 using Rank = unsigned int;
0002 
0003 #if defined( DSA_REDBLACK ) //在红黑树中
0004 #define stature( p ) ( ( p ) ? ( p )->height : 0 ) //外部节点（黑）高度为0，以上递推
0005 #else //其余BST中
0006 #define stature( p ) ( (int)( ( p ) ? ( p )->height : -1 ) ) //外部节点高度为-1，以上递推
0007 #endif
0008 
0009 typedef enum { RB_RED, RB_BLACK} RBColor; //节点颜色
0010 
0011 template <typename T> struct BinNode;
0012 template <typename T> using BinNodePosi = BinNode<T>*; //节点位置
0013 
0014 template <typename T> struct BinNode { //二叉树节点模板类
0015 // 成员（为简化描述起见统一开放，读者可根据需要进一步封装）
0016    T data; //数值
0017    BinNodePosi<T> parent, lc, rc; //父节点及左、右孩子
0018    Rank height; //高度（通用）
0019    Rank npl; //Null Path Length（左式堆，也可直接用height代替）
0020    RBColor color; //颜色（红黑树）
0021 // 构造方法
0022    BinNode() : parent( NULL ), lc( NULL ), rc( NULL ), height( 0 ), npl( 1 ), color( RB_RED ) {}
0023    BinNode( T e, BinNodePosi<T> p = NULL, BinNodePosi<T> lc = NULL,
0024             BinNodePosi<T> rc = NULL, int h = 0, int l = 1, RBColor c = RB_RED )
0025       : data( e ), parent( p ), lc( lc ), rc( rc ), height( h ), npl( l ), color( c )
0026       { if (lc) lc->parent = this; if (rc) rc->parent = this; }
0027 // 操作接口
0028    Rank size(); //统计当前节点后代总数，亦即以其为根的子树的规模
0029    Rank updateHeight(); //更新当前节点高度
0030    void updateHeightAbove(); //更新当前节点及其祖先的高度
0031    BinNodePosi<T> insertLc( T const& ); //插入左孩子
0032    BinNodePosi<T> insertRc( T const& ); //插入右孩子
0033    void attachLc( BinNodePosi<T> ); //接入左子树
0034    void attachRc( BinNodePosi<T> ); //接入右子树
0035    BinNodePosi<T> succ(); //取当前节点的直接后继
0036    template <typename VST> void travLevel( VST& ); //子树层次遍历
0037    template <typename VST> void travPre( VST& ); //子树先序遍历
0038    template <typename VST> void travIn( VST& ); //子树中序遍历
0039    template <typename VST> void travPost( VST& ); //子树后序遍历
0040 // 比较器、判等器（各列其一，其余自行补充）
0041    bool operator< ( BinNode const& bn ) { return data < bn.data; } //小于
0042    bool operator== ( BinNode const& bn ) { return data == bn.data; } //等于
0043 };