二叉排序树的插入与查找实现

/*
二叉排序树的插入与查找实现
*/
#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!\n"<<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!\n";
        else cout<<"NOT FOUND!\n";
    return 0;
}