0001 template <typename T> struct BinNode;
0002 template <typename T> using BNP = BinNode<T>*; //节点位置|Binary Node Position
0003 
0004 template <typename T> struct BinNode {
0005    T data;  BNP<T> parent, lc, rc; //数据、父节点及左、右孩子
0006    int height; //常规二叉树的高度、红黑树的黑高度、左式堆的npl
0007    bool color; //红黑树节点的颜色（0红、1黑）
0008 //构造方法
0009    BinNode(T e, BNP<T> _p = nullptr, BNP<T> lc = nullptr,
0010             BNP<T> rc = nullptr, int h = 0, bool c = RBT_RED)
0011       : data(e), parent(_p), lc(lc), rc(rc), height(h), color(c)
0012       { if (lc) lc->parent = this;  if (rc) rc->parent = this; }
0013 //操作接口
0014    Rank size(); //后代总数
0015    int updateHeight(); //更新高度
0016    void updateHeightAbove(); //更新当前节点及历代祖先的高度
0017    BNP<T> insertLc(const T&); //插入左孩子
0018    BNP<T> insertRc(const T&); //插入右孩子
0019    void attachLc(BNP<T>); //接入左子树
0020    void attachRc(BNP<T>); //接入右子树
0021    BNP<T> succ(); //直接后继：取决于具体的遍历规则，默认为中序
0022    template <typename V> void traverse(V&); //遍历
0023 //比较器、判等器：仅示例各一，其余可自行补充
0024    bool operator<(const BinNode& bn) { return data <  bn.data; }
0025    bool operator==(const BinNode& bn) { return data == bn.data; } //相等者，未必相同
0026 }; //BinNode