0001 #include "BinTree/BinTree.h" //引入BinTree 0002 0003 template <typename T> class BST : public BinTree<T> { //由BinTree派生BST模板类 0004 protected: 0005 BinNodePosi(T) _hot; //“命中”节点的父亲 0006 BinNodePosi(T) connect34 ( //按照“3 + 4”结构,联接3个节点及四棵子树 0007 BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), 0008 BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T) ); 0009 BinNodePosi(T) rotateAt ( BinNodePosi(T) x ); //对x及其父亲、祖父做统一旋转调整 0010 public: //基本接口:以virtual修饰,强制要求所有派生类(BST变种)根据各自的规则对其重写 0011 virtual BinNodePosi(T) & search ( const T& e ); //查找 0012 virtual BinNodePosi(T) insert ( const T& e ); //插入 0013 virtual bool remove ( const T& e ); //删除 0014 };