#include <iostream>
using namespace std;
template<typename Type>
struct BTNode{
Type elem;
BTNode<Type>* lchild, *rchild;
BTNode(){}
BTNode( BTNode<Type>* l, BTNode<Type>* r, Type k ):
lchild(l), rchild(r), elem(k) {}
};
template<typename Type>
class BSTree{
private:
BTNode<Type>* root;
BTNode<Type>* get_min( BTNode<Type>* );
BTNode<Type>* get_max( BTNode<Type>* );
BTNode<Type>* insert ( BTNode<Type>*, Type key );
BTNode<Type>* erase ( BTNode<Type>*, Type key );
void travel ( BTNode<Type>* root );
void clear ( BTNode<Type>* root );
bool search ( BTNode<Type>*, Type key );
public:
BSTree();
~BSTree();
BTNode<Type>* get_min();
BTNode<Type>* get_max();
void insert( Type key );
void travel();
bool is_empty();
void clear();
void erase( Type key );
bool search( Type key );
};
template<typename Type>
bool BSTree<Type>::search( BTNode<Type>* root, Type key ){
if( !root ) return false;
if( root->elem== key ) return true;
if( key< root->elem ) return search( root->lchild, key );
else return search( root->rchild, key );
}
template<typename Type>
bool BSTree<Type>::search( Type key ){
return search( root, key ); }
template<typename Type>
BTNode<Type>* BSTree<Type>::erase( BTNode<Type>* root, Type key ){
if( root->elem== key ){
if( !root->lchild && !root->rchild ){
delete root;
return NULL; }
else if( root->lchild && !root->rchild ){
BTNode<Type>* tmp= root->lchild;
delete root; return tmp; }
else {
BTNode<Type>* tmp= get_min( root->rchild );
root->elem= tmp->elem;
root->rchild= erase( root->rchild, tmp->elem );
return root; }
}
if( key< root->elem ) root->lchild= erase( root->lchild, key );
else root->rchild= erase( root->rchild, key );
return root;
}
template<typename Type>
void BSTree<Type>::erase( Type key ){
if( !search( key ) ) return;
root= erase( root, key );
}
template<typename Type>
void BSTree<Type>::clear( BTNode<Type>* root ){
if( root ){
clear( root->lchild );
clear( root->rchild );
delete root; }
}
template<typename Type>
void BSTree<Type>::clear(){
clear( root ); }
template<typename Type>
bool BSTree<Type>::is_empty(){
return root== NULL; }
template<typename Type>
BSTree<Type>::BSTree(){ root= NULL; }
template<typename Type>
BSTree<Type>::~BSTree(){
clear(); }
template<typename Type>
void BSTree<Type>::travel( BTNode<Type>* root ){
if( root ){
travel( root->lchild );
cout << root->elem << endl;
travel( root->rchild ); }
}
template<typename Type>
void BSTree<Type>::travel(){
BTNode<Type>* r= root;
travel( r ); }
template<typename Type>
BTNode<Type>* BSTree<Type>::insert(BTNode<Type>* root,Type key){
if( root== NULL )
return new BTNode<Type>( NULL, NULL, key );
if( root->lchild== NULL && key< root->elem ){
root->lchild= new BTNode<Type>( NULL, NULL, key );
return root; }
else if( root->rchild== NULL && key> root->elem ){
root->rchild= new BTNode<Type>( NULL, NULL, key );
return root; }
if( root->elem> key ) root->lchild= insert( root->lchild, key );
else root->rchild= insert( root->rchild, key );
return root;
}
template<typename Type>
void BSTree<Type>::insert( Type key ){
root= insert( root, key ); }
template<typename Type>
BTNode<Type>* BSTree<Type>::get_min( BTNode<Type>* root ){
if( root== NULL ) return NULL;
while( root->lchild ) root= root->lchild;
return root;}
template<typename Type>
BTNode<Type>* BSTree<Type>::get_min(){
BTNode<Type>* r= root;
return get_min( r );}
template<typename Type>
BTNode<Type>* BSTree<Type>::get_max( BTNode<Type>* root ){
if( root== NULL ) return NULL;
while( root->rchild ) root= root->rchild;
return root;}
template<typename Type>
BTNode<Type>* BSTree<Type>::get_max(){
BTNode<Type>* r= root;
return get_max( r );}
int main()
{
freopen( "test.txt", "w", stdout );
BSTree<int> test;
for( int i= 0; i< 100000; ++i )
test.insert( rand() );
for( int i= 0; i< 100000; ++i )
test.erase( rand() );
test.travel();
return 0;
}
posted on 2009-04-11 19:29
Darren 阅读(1259)
评论(2) 编辑 收藏 引用