Kod:
if( t == NULL )
return ITEM_NOT_FOUND;
else
return t->element;
}
/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the tree.
* Set the new root.
*/
template <class VeriTipi>
**** BinarySearchTree<VeriTipi>::
insert( const VeriTipi & x, BinaryNode<VeriTipi> * & t ) const
{
if( t == NULL ){
t = new BinaryNode<VeriTipi>( x, NULL, NULL );
}
else if( x < t->element ){
insert( x, t->sol );
}
else if( t->element < x ){
insert( x, t->sag );
}
else
cout<<"Bu bilgi agacta sakli" << endl; // Duplicate; do nothing
}
/**
* Internal method to remove from a subtree.
* x is the item to remove.
* t is the node that roots the tree.
* Set the new root.
*/
template <class VeriTipi>
**** BinarySearchTree<VeriTipi>::
remove( const VeriTipi & x, BinaryNode<VeriTipi> * & t ) const
{
if( t == NULL )
return;
// Item not found; do nothing
if( x < t->element )
remove( x, t->sol );
else if( t->element < x )
remove( x, t->sag );
else if( t->sol != NULL && t->sag != NULL ) // Two children
{
t->element = findMax( t->sol )->element;
remove( t->element, t->sol );
}
else
{
BinaryNode<VeriTipi> *oldNode = t;
t = ( t->sol != NULL ) ? t->sol : t->sag;
delete oldNode;
}
}
/**
* Internal method to find the smallest item in a subtree t.
* Return node containing the smallest item.
*/
template <class VeriTipi>
BinaryNode<VeriTipi> *
BinarySearchTree<VeriTipi>::findMin( BinaryNode<VeriTipi> *t ) const
{
if( t == NULL )
return NULL;
if( t->sol == NULL )
return t;
return findMin( t->sol );
}
/**
* Internal method to find the largest item in a subtree t.
* Return node containing the largest item.
*/
template <class VeriTipi>
BinaryNode<VeriTipi> *
BinarySearchTree<VeriTipi>::findMax( BinaryNode<VeriTipi> *t ) const
{
if( t != NULL )
while( t->sag != NULL )
t = t->sag;
return t;
}
/**
* Internal method to find an item in a subtree.
* x is item to search for.
* t is the node that roots the tree.
* Return node containing the matched item.
*/
template <class VeriTipi>
BinaryNode<VeriTipi> *
BinarySearchTree<VeriTipi>::
find( const VeriTipi & x, BinaryNode<VeriTipi> *t ) const
{
if( t == NULL )
return NULL;
else if( x < t->element )
return find( x, t->sol );
else if( t->element < x )
return find( x, t->sag );
else
return t; // Match
}
/****** NONRECURSIVE VERSION*************************
template <class VeriTipi>
BinaryNode<VeriTipi> *
BinarySearchTree<VeriTipi>::
find( const VeriTipi & x, BinaryNode<VeriTipi> *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->sol;
else if( t->element < x )
t = t->sag;
else
return t; // Match
return NULL; // No match
}
*****************************************************/
/**
* Internal method to make subtree empty.
*/
template <class VeriTipi>
**** BinarySearchTree<VeriTipi>::
makeEmpty( BinaryNode<VeriTipi> * & t ) const
{
if( t != NULL )
{
makeEmpty( t->sol );
makeEmpty( t->sag );
delete t;
}
t = NULL;
}
/**
* Internal method to print a subtree rooted at t in sorted order.
*/
template <class VeriTipi>
**** BinarySearchTree<VeriTipi>::printTree( BinaryNode<VeriTipi> *t ) const
{
if( t != NULL )
{
printTree( t->sol );
cout << t->element << endl;
printTree( t->sag );
}
}
/**
* Internal method to clone subtree.
*/
template <class VeriTipi>
BinaryNode<VeriTipi> *
BinarySearchTree<VeriTipi>::clone( BinaryNode<VeriTipi> * t ) const
{
if( t == NULL )
return NULL;
else
return new BinaryNode<VeriTipi>( t->element, clone( t->sol ), clone( t->sag ) );
}
int main( )
{
const int ITEM_NOT_FOUND = -1;
BinarySearchTree<int> t( ITEM_NOT_FOUND );
BinarySearchTree<int> s(ITEM_NOT_FOUND);
s.insert(10);
s.insert(20);
s.insert(5);
s.insert(30);
s.insert(25);
s.printTree();
cout<<"---------------"<<endl;
s.remove(50);
s.remove(20);
s.printTree();
cout<<"---------------"<<endl;
cout<<"Agactaki en buyuk eleman="<<s.findMax()<<endl;
if( s.find( 25 ) != ITEM_NOT_FOUND )
cout << "Agacta 25 elemani var" << endl;
if( s.find( 35 ) == ITEM_NOT_FOUND )
cout << "Agacta 35 yok" << endl;
system("PAUSE");
return 0;
}