#include? < iostream >
using ? namespace ?std;

template? < class ?T >
struct ?BSTreeNode
{
????T?info;
????BSTreeNode? * ls;
????BSTreeNode? * rs;
} ;

template? < class ?T >
class ?BSTree
{
public :
????BSTree();
???? bool ?insert(T?key);
???? bool ?find(T?key);
???? void ?travel();
???? int ?size();
private :
???? bool ?insert_inner(BSTreeNode < T > ? *& root,?BSTreeNode < T > ? * p);
???? bool ?find_inner(BSTreeNode < T > ? * root,?T?key);
???? void ?travel_inner(BSTreeNode < T > ? * root);
????BSTreeNode < T > ? * root;
???? int ?_size;
} ;

template? < class ?T >
BSTree < T > ::BSTree()
{
????root? = ?NULL;
????_size? = ? 0 ;
}

template? < class ?T >
bool ?BSTree < T > ::insert(T?key)
{
????BSTreeNode < T > ? * p? = ? new ?BSTreeNode < T > ;
????p -> info? = ?key;
????p -> ls? = ?NULL;
????p -> rs? = ?NULL;
???? if ?(insert_inner(root,?p))
???????? return ? true ;
???? else
???????? return ? false ;
}

template? < class ?T >
bool ?BSTree < T > ::insert_inner(BSTreeNode < T > ? *& root,?BSTreeNode < T > ? * p)
{
???? if ?(root? == ?NULL)
???? {
????????root? = ?p;
????????_size ++ ;
???????? return ? true ;
????}

???? if ?(root -> info? == ?p -> info)
???????? return ? false ;

???? if ?(p -> info? < ?root -> info)
????????insert_inner(root -> ls,?p);
???? else
????????insert_inner(root -> rs,?p);
}

template? < class ?T >
bool ?BSTree < T > ::find(T?key)
{
???? if ?(find_inner(root,?key))
???????? return ? true ;
???? else
???????? return ? false ;
}

template? < class ?T >
bool ?BSTree < T > ::find_inner(BSTreeNode < T > ? * root,?T?key)
{
???? if ?(root? == ?NULL)
???????? return ? false ;

???? if ?(root -> info? == ?key)
???????? return ? true ;

???? if ?(key? < ?root -> info)
????????find_inner(root -> ls,?key);
???? else
????????find_inner(root -> rs,?key);
}

template? < class ?T >
int ?BSTree < T > ::size()
{
???? return ?_size;
}

template? < class ?T >
void ?BSTree < T > ::travel()
{
????travel_inner(root);
}

template? < class ?T >
void ?BSTree < T > ::travel_inner(BSTreeNode < T > ? * root)
{
???? if ?(root? == ?NULL)? return ?;
????travel_inner(root -> ls);
????cout? << ?root -> info? << ?endl;
????travel_inner(root -> rs);
}


int ?main()
{
????BSTree < int > ?bst;
???? int ?a[]? = ? { 3 ,? 2 ,? 5 ,? 1 ,? 4 } ;
???? for ?( int ?i = 0 ;?i < sizeof (a) / sizeof ( int );?i ++ )
????????bst.insert(a[i]);
????bst.travel();
???? return ? 0 ;
}