ツリーの挿入と検索の実装

1915 ワード

/*
 
*/
#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; }