请教~BinarySearchTree
这是我复制数据结构书的代码,想弄头文件,但编译出现很多错误。请高手帮帮template <typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree( );
BinarySearchTree( const BinarySearchTree & rhs );
~BinarySearchTree( );
const Comparable & findMin( ) const;
const Comparable & findMax( ) const;
bool contains( const Comparable & x ) const;
bool isEmpty( ) const;
void printTree( ) const;
void makeEmpty( );
void insert( const Comparable & x );
void remove( const Comparable & x );
const BinarySearchTree & operator=( const BinarySearchTree & rhs );
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt ) { }
};
BinaryNode *root;
void insert( const Comparable & x, BinaryNode * & t ) const;
void remove( const Comparable & x, BinaryNode * & t ) const;
BinaryNode * findMin( BinaryNode *t ) const;
BinaryNode * findMax( BinaryNode *t ) const;
bool contains( const Comparable & x, BinaryNode *t ) const;
void makeEmpty( BinaryNode * & t );
void printTree( BinaryNode *t ) const;
BinaryNode * clone( BinaryNode *t ) const;
};
bool contains( const Comparable & x ) const //公有调用私有 图4-17
{
return contains( x, root );
}
void insert( const Comparable & x )
{
insert( x, root );
}
void remove( const Comparable & x )
{
remove( x, root );
}
bool contains( const Comparable & x, BinaryNode *t ) const //contains操作
{
if( t == NULL )
return false;
else if( x < t->element )
return contains( x, t->left );
else if( t->element < x )
return contains( x, t->right );
else
return true;
BinaryNode * findMin( BinaryNode *t ) const //findmin
{
if( t == NULL )
return NULL;
if( t->left == NULL )
return t;
return findMin( t->left );
}
BinaryNode * findMax( BinaryNode *t ) const //findmax
{
if( t != NULL )
while( t->right != NULL )
t = t->right;
return t;
}
void insert( const Comparable & x, BinaryNode * & t ) //insert 操作
{
if( t == NULL )
t = new BinaryNode( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
; // Duplicate; do nothing
void remove( const Comparable & x, BinaryNode * & t ) //remove 操作
{
if( t == NULL )
return; // Item not found; do nothing
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) // Two children
{
t->element = findMin( t->right )->element;
remove( t->element, t->right );
}
else
{
BinaryNode *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right;
delete oldNode;
}
}