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