**fig4_16.txt** /* 1*/ #include /* 2*/ template /* 3*/ class Tree_Node /* 4*/ { /* 5*/ protected: /* 6*/ Etype Element; /* 7*/ Tree_Node *Left; /* 8*/ Tree_Node *Right; /* 9*/ Tree_Node( Etype E = 0, Tree_Node *L = NULL, /*10*/ Tree_Node *R = NULL ) : Element( E ), /*11*/ Left( L ), Right( R ) { } /*12*/ friend int Height( Tree_Node * T ); /*13*/ friend class Binary_Search_Tree; /*14*/ }; /*15*/ template /*16*/ class Binary_Search_Tree /*17*/ { /*18*/ protected: /*19*/ void Make_Empty( Tree_Node * & T ); /*20*/ void Insert( const Etype & X, Tree_Node * & T ); /*21*/ void Remove( const Etype & X, Tree_Node * & T ); /*22*/ void Print_Tree( Tree_Node * T ) const; /*23*/ Tree_Node * /*24*/ Copy( const Tree_Node * T ); /*25*/ Tree_Node * /*26*/ Find( const Etype & X, Tree_Node * T ) const; /*27*/ Tree_Node * /*28*/ Find_Min( Tree_Node * T ) const; /*29*/ Tree_Node * /*30*/ Find_Max( Tree_Node * T ) const; /*31*/ Tree_Node *Root; /*32*/ Tree_Node *Last_Find; /*33*/ Binary_Search_Tree( Binary_Search_Tree & Value ); // Disabled. /*34*/ /*35*/ public: /*36*/ // Constructors. /*37*/ Binary_Search_Tree( ) : Root( NULL ), Last_Find( NULL ) { } /*38*/ // Destructor. /*39*/ virtual ~Binary_Search_Tree( ) /*40*/ { Make_Empty( Root ); Root = Last_Find = NULL; } /*41*/ // Operators. /*42*/ const Binary_Search_Tree & /*43*/ operator = ( const Binary_Search_Tree & Value ); /*44*/ const Etype & operator ( ) ( ) const /*45*/ { return Last_Find != NULL ? Last_Find->Element : NULL; } /*46*/ // Member functions. /*47*/ void Make_Empty( ) /*48*/ { Make_Empty( Root ); Root = Last_Find = NULL; } /*49*/ void Print_Tree( ) const /*50*/ { Print_Tree( Root ); } /*51*/ virtual int Find( const Etype & X ) /*52*/ { return int( Last_Find = Find( X, Root ) ); } /*53*/ virtual int Find_Min( ) /*54*/ { return int( Last_Find = Find_Min( Root ) ); } /*55*/ virtual int Find_Max( ) /*56*/ { return int( Last_Find = Find_Max( Root ) ); } /*57*/ virtual void Insert( const Etype & X ) /*58*/ { Insert( X, Root ); } /*59*/ virtual void Remove( const Etype & X ) /*60*/ { Remove( X, Root ); } /*61*/ };