0001 #include "BinNode.h" //引入二叉树节点类 0002 template <typename T> class BinTree { //二叉树模板类 0003 protected: 0004 int _size; BinNodePosi(T) _root; //规模、根节点 0005 virtual int 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 int size() const { return _size; } //规模 0011 bool empty() const { return !_root; } //判空 0012 BinNodePosi(T) root() const { return _root; } //树根 0013 BinNodePosi(T) insertAsRoot ( T const& e ); //插入根节点 0014 BinNodePosi(T) insertAsLC ( BinNodePosi(T) x, T const& e ); //e作为x的左孩子(原无)插入 0015 BinNodePosi(T) insertAsRC ( BinNodePosi(T) x, T const& e ); //e作为x的右孩子(原无)插入 0016 BinNodePosi(T) attachAsLC ( BinNodePosi(T) x, BinTree<T>* &T ); //T作为x左子树接入 0017 BinNodePosi(T) attachAsRC ( BinNodePosi(T) x, BinTree<T>* &T ); //T作为x右子树接入 0018 int remove ( BinNodePosi(T) x ); //删除以位置x处节点为根的子树,返回该子树原先的规模 0019 BinTree<T>* secede ( BinNodePosi(T) x ); //将子树x从当前树中摘除,并将其转换为一棵独立子树 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