二叉查找树

#ifndef __BINARYSEARCHTREE_H__
#define  __BINARYSEARCHTREE_H__

//template<typename int>
class BinarySearchTree
{
    private:
        struct BinaryNode
        {
            int element;
            BinaryNode *left;
            BinaryNode *right;
            BinaryNode(const int &theElement,BinaryNode *lt,BinaryNode *rt):element(theElement),left(lt),right(rt)
            {
            }
        };
        BinaryNode *root;

        void insert(const int &x,BinaryNode * &t)const;
        void remove(const int& x,BinaryNode *&t)const;
        BinaryNode *findMin(BinaryNode *t)const;
        BinaryNode *findMax(BinaryNode *t)const;
        bool contains(const int &x,BinaryNode *t)const;
        void makeEmpty(BinaryNode* & t);
        void printTree(BinaryNode *t)const;
    //    BinaryNode *clone(BinaryNode *t)const;
        int deep(BinaryNode *t);


    public:
        BinarySearchTree();
        BinarySearchTree(const BinarySearchTree &rhs);
        ~BinarySearchTree();

        const int &findMin()const;
        const int &findMax()const;
        bool contains(const int &x)const;
        bool isEmpty()const;
        void printTree()const;

        void makeEmpty();
        void insert(const int &x);
        void remove(const int &x);
    //    const BinarySearchTree& operator=(const BinarySearchTree& rhs);
        int deep()
        {
            return deep(root);
        }
};

#endif

#include"BinarySearchTree.h"
#include<iostream>
using std::cout;

BinarySearchTree::BinarySearchTree():root(NULL)
{
}

bool BinarySearchTree::contains(const int& x)const
{
    return contains(x,root);
}

bool BinarySearchTree::contains(const int &x,BinaryNode *t)const
{
    if(t==NULL)
        return false;
    else if(x < t->element)
        return contains(x,t->left);
    else if(x > t->element)
        return contains(x,t->right);
    else
        return true;
}

void BinarySearchTree::insert(const int &x)
{
    insert(x,root);
}

void BinarySearchTree::insert(const int &x,BinaryNode *&t)const
{
    if(t==NULL)
        t=new BinaryNode(x,NULL,NULL);
    else if(x<t->element)
        insert(x,t->left);
    else if(x>t->element)
        insert(x,t->right);
    else
        ;//Duplicate;do nothing。即如果x已经存在二叉树中，则插入操作终止。
}

void BinarySearchTree::remove(const int &x)
{
    remove(x,root);
}

void BinarySearchTree::remove(const int &x,BinaryNode * &t)const
{
    if(t==NULL)
        return ;
    if(x<t->element)
        remove(x,t->left);
    else if(x>t->element)
        remove(x,t->right);
    else if(t->left!=NULL && t->right!=NULL)
    {
        t->element=findMin(t->right)->element;
        remove(t->element,t->right);
    }
    else
    {
        BinaryNode *oldNode=t;
        t=(t->left!=NULL)? t->left : t->right;
        delete oldNode;
    }
}

BinarySearchTree::BinaryNode* BinarySearchTree::findMin(BinaryNode *t)const
{
    if(t==NULL)
        return NULL;
    if(t->left==NULL)
        return t;
    return findMin(t->left);
}

BinarySearchTree::BinaryNode* BinarySearchTree::findMax(BinaryNode *t)const
{
    if(t!=NULL)
        while(t->right!=NULL)
            t=t->right;
    return t;
}

void BinarySearchTree::makeEmpty()
{
    makeEmpty(root);
}
void BinarySearchTree::makeEmpty(BinaryNode* &t)
{
    if(t!=NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t=NULL;
}

BinarySearchTree::~BinarySearchTree()
{
    makeEmpty();
}

void BinarySearchTree::printTree()const
{
    printTree(root);
}
void BinarySearchTree::printTree(BinaryNode *t)const
{
    if(t==NULL)
        return ;
    else
        cout<<t->element<<',';
    //    printf("%d",t->element);
    printTree(t->left);
    printTree(t->right);
}


//BinarySearchTree::operator =(const BinarySearchTree &rhs)
//{

//}
int BinarySearchTree::deep(BinaryNode *t)//求二叉树的深度。
{
    int lm,rm;
    if(t==NULL)
        return -1;
    lm=deep(t->left);
    rm=deep(t->right);
    return 1+(lm>rm? lm:rm);
}

#include"BinarySearchTree.h"
#include<iostream>
using namespace std;

int main()
{
    BinarySearchTree bt;
    bt.insert(6);
    bt.insert(2);
    bt.insert(1);
    bt.insert(4);
    bt.insert(3);
    bt.insert(8);

    cout<<bt.deep()<<endl;
    bt.printTree();
    cout<<endl;
    bt.remove(2);
    bt.printTree();
    cout<<endl;
    cout<<bt.deep()<<endl;
    bt.remove(1);
    bt.remove(3);
    cout<<bt.deep()<<endl;
    return 0;
}