2011年软考程序员考试复习笔试知识点整理(20)2

 　//Throws UnderflowException as warranted

　　template

　　classAvlTree

　　{

　　public:

　　AvlTree( ) : root( NULL ) { }

　　AvlTree( const AvlTree & rhs ) : root(NULL )

　　{

　　*this = rhs;

　　}

　　~AvlTree( )

　　{

　　makeEmpty( );

　　}

　　/**

　　* Find the smallest item in the tree.

　　* Throw UnderflowException if empty.

　　*/

　　const Comparable & findMin( ) const

　　{

　　if( isEmpty( ) )

　　throw UnderflowException( );

　　return findMin( root )->element;

　　}

　　/**

　　* Find the largest item in the tree.

　　* Throw UnderflowException if empty.

　　*/

　　const Comparable & findMax( ) const

　　{

　　if( isEmpty( ) )

　　throw UnderflowException( );

　　return findMax( root )->element;

　　}

　　/**

　　* Returns true if x is found in the tree.

　　*/

　　bool contains( const Comparable & x )const

　　{

　　return contains( x, root );

　　}

　　/**

　　* Test if the tree is logically empty.

　　* Return true if empty, false otherwise.

　　*/

　　bool isEmpty( ) const

　　{

　　return root == NULL;

　　}

　　/**

　　* Print the tree contents in sorted order.

　　*/

　　void printTree( ) const

　　{

　　if( isEmpty( ) )

　　cout