0001 #include "BinNode.h" //引入二叉树节点类
0002 template <typename T> class BinTree { //二叉树模板类
0003 protected:
0004    Rank _size; BinNodePosi<T> _root; //规模、根节点
0005    virtual Rank updateHeight( BinNodePosi<T> x ); //更新节点x的高度
0006    void updateHeightAbove( BinNodePosi<T> x ); //更新节点x及其祖先的高度
0007 public:
0008    BinTree() : _size( 0 ), _root( NULL ) {} //构造函数
0009    ~BinTree() { if ( 0 < _size ) remove( _root ); } //析构函数
0010    Rank size() const { return _size; } //规模
0011    bool empty() const { return !_root; } //判空
0012    BinNodePosi<T> root() const { return _root; } //树根
0013    BinNodePosi<T> insert( T const& ); //插入根节点
0014    BinNodePosi<T> insert( T const&, BinNodePosi<T> ); //插入左孩子
0015    BinNodePosi<T> insert( BinNodePosi<T>, T const& ); //插入右孩子
0016    BinNodePosi<T> attach( BinTree<T>*&, BinNodePosi<T> ); //接入左子树
0017    BinNodePosi<T> attach( BinNodePosi<T>, BinTree<T>*& ); //接入右子树
0018    Rank remove ( BinNodePosi<T> ); //子树删除
0019    BinTree<T>* secede ( BinNodePosi<T> ); //子树分离
0020    template <typename VST> //操作器
0021    void travLevel( VST& visit ) { if ( _root ) _root->travLevel( visit ); } //层次遍历
0022    template <typename VST> //操作器
0023    void travPre( VST& visit ) { if ( _root ) _root->travPre( visit ); } //先序遍历
0024    template <typename VST> //操作器
0025    void travIn( VST& visit ) { if ( _root ) _root->travIn( visit ); } //中序遍历
0026    template <typename VST> //操作器
0027    void travPost( VST& visit ) { if ( _root ) _root->travPost( visit ); } //后序遍历
0028    bool operator<( BinTree<T> const& t ) //比较器（其余自行补充）
0029       { return _root && t._root && lt( _root, t._root ); }
0030    bool operator==( BinTree<T> const& t ) //判等器
0031       { return _root && t._root && ( _root == t._root ); }
0032 }; //BinTree