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