/*
*/
#include <iostream>
#include <cstdio>
using namespace std;
template <class T> class BSTree;
template <class T>
class BTreeNode
{
private:
BTreeNode<T> *lchild;
BTreeNode<T> *rchild;
T data;
public:
friend class BSTree<T>;
BTreeNode( T d,BTreeNode<T> *l,BTreeNode<T> *r )
{
data=d;
lchild=l;
rchild=r;
}
};
template <class T>
class BSTree
{
private:
BTreeNode<T> *root;
public:
BSTree()
{
root=NULL;
}
void inst( T el );
void inst1( BTreeNode<T> *p,BTreeNode<T> * &q );
BTreeNode<T> *sear( T el );
};
template <class T>
BTreeNode<T> *BSTree<T>::sear( T el ) //
{
BTreeNode<T> *p=root;
while( p!=NULL )
{
if( p->data==el ) return p;
else if( p->data<el ) p=p->lchild;
else p=p->rchild;
}
return p;
}
template <class T>
void BSTree<T>::inst1( BTreeNode<T> *p,BTreeNode<T> * &q ) //
{
if( q==NULL )
{
q=p;
return;
}
if( q->data<p->data ) inst1( p,q->lchild );
else inst1( p,q->rchild );
}
template <class T>
void BSTree<T>::inst( T el ) //
{
BTreeNode<T> *p;
if( sear(el)!=NULL ) cout<<"HAVE FOUND!
"<<endl;
else
{
p=new BTreeNode<T>( el,NULL,NULL );
inst1( p,root );
}
}
int main()
{
int i;
BSTree<int> bt;
for( i=0;i<10;i++ )
bt.inst(i);
bt.inst(5);
for( i=0;i<11;i++ )
if( bt.sear(i)!=NULL) cout<<"FOUND!
";
else cout<<"NOT FOUND!
";
return 0;
}