bst.h

关于BST的基本功能和基本操作~适合初初学者使用~

#include <iostream>
using namespace std;

class node
{
         friend class bstree;
         private:
                 int data;
                 node *lefttree;
				 node *righttree;
         public:
                 node(int a){data=a;lefttree=righttree=NULL;}
                 ~node(){};
};

class bstree
{
    protected:
        node *root;
    public:
        bstree();
        ~bstree();
        void free(node *p);
//        void control();
        node * get_root();
        void find(int res,node *p);
        void insert(int in,node *p,int &flag);
        void delete_bs(int del);
        node * max(node *p);
        void max_F(node *p);
        node * min(node *p);
        void min_F(node *p);
        void mid_show();
        void mid_show1(node *p);
        void creat_trees(node *p,int aa);
		void judge(node *r,int &flag);
		node * ret_left(node *h){node *p=h->lefttree;return p;}
		node * ret_righ(node *h){node *p=h->righttree;return p;}

};

/*void bstree :: control()
{
    
}
*/

node * bstree :: get_root(){return root;}

bstree :: bstree()
{
    
    cout <<"Do you want to creat the root?(Y/N)";
    char ch;
    cin >>ch;
    if (ch=='Y'||ch=='y')
    {
        cout <<"please input the data of the root"<<endl;
        int a;
        cin >>a;
        root =new node(a);
        root->data=a;
        cout <<"root KO"<<endl;
    }
    else
    exit(-1);
    return;    
}

bstree :: ~bstree()
{
     if (root->righttree!=NULL)
     free(root->lefttree);
     if (root->lefttree!=NULL)
     free(root->righttree);
     cout <<"Success~"<<endl;
}

void bstree :: free(node *p)
{
    if (p->lefttree != NULL)
		free (p->lefttree);
	else if (p->righttree!= NULL)
		free (p->righttree);
	else 
		delete p;
		return ;
}

void bstree :: find(int res,node *p)
{
    if(res==p->data)
    {
        cout <<"This data existed"<<endl;
        return;
    }
    if(p->righttree==NULL&&p->lefttree==NULL) {cout <<"No data"<<endl;return;}
    if(res>p->data) 
    {
        if(p->righttree==NULL)
        {
            cout<<"No data"<<endl;
            return;
        }
        find(res,p->righttree);
    }
    else 
    {
        if(p->lefttree==NULL)
        {
            cout<<"No data"<<endl;
            return;
        } 
        find(res,p->lefttree);
    }
    return;
}

void bstree :: insert(int in,node *p,int &flag)
{
    if(in==p->data) {cout <<"This data has been existed"<<endl;flag=1;}
    if(in>p->data&&flag==0) 
    {
        if(p->righttree==NULL)
        {
            p->righttree =new node(in);
            flag=1;
            cout <<"INSERT KO"<<endl;
            return;
        }
        else
        insert(in,p->righttree,flag);
    }
    if(in<p->data&&flag==0) 
    {
        if(p->lefttree==NULL)
        {
            p->lefttree =new node(in);
            flag=1;
            cout <<"INSERT KO"<<endl;
            return;
        }
        else
        insert(in,p->lefttree,flag);
    }
    return;
}

void bstree :: delete_bs(int del)
{
    node *q;
    node *p=root;
    for (;p->data!=del||p!=NULL;)
    {
        q=p;
        if(del>p->data) p=p->righttree;
        else p=p->lefttree;
    }
    if(p==NULL) {cout <<"No data"<<endl;return;}
    else 
    {
        if(p->lefttree==NULL&&p->righttree==NULL) 
        {
            delete p;
            return;
        }
        if(p->lefttree!=NULL&&p->righttree==NULL)
        {
            if(q->lefttree==p) q->lefttree=p->lefttree;
            else q->righttree=p->lefttree;
            delete p;
            return;
        }
        if(p->lefttree==NULL&&p->righttree!=NULL)
        {
            if(q->lefttree==p) q->lefttree=p->righttree;
            else q->righttree=p->righttree;
            delete p;
            return;
        }
        else
        {
            node *temp=max(p->lefttree);
            p->data=temp->data;
            delete temp;
            return;
        }
    }
    cout <<"delete KO"<<endl;
    return;
}


node * bstree :: max(node *p)
{
    for(;p->righttree!=NULL;p=p->righttree){}
    return p;
}

void bstree :: max_F(node *p)
{
    for(;p->righttree!=NULL;p=p->righttree)
    cout <<"lefttree's maxdata is: "<<p->data<<endl;
    return;
}

node * bstree :: min(node *p)
{
    for(;p->lefttree!=NULL;p=p->lefttree){}
    return p;
}

void bstree :: min_F(node *p)
{
    for(;p->lefttree!=NULL;p=p->lefttree)
    cout <<"righttree's maxdata is: "<<p->data<<endl;
    return;
}

void bstree :: mid_show()
{
    node *p=root;
    if (p->lefttree!=NULL)
        mid_show1(p->lefttree);
    cout <<p->data<<" ";
    if (p->righttree!=NULL)
        mid_show1(p->righttree);
    cout <<endl;
    return;
}

void bstree :: mid_show1(node *p)
{
    
    if (p->lefttree!=NULL)
        mid_show1(p->lefttree);
    cout <<p->data<<" ";
    if (p->righttree!=NULL)
        mid_show1(p->righttree);
    return;
}

void bstree :: creat_trees(node *p,int aa)
{
    p=new node(aa);
    cout <<"Do you want to creat the leftchild? Enter 'Y' to continue else please enter 'N',thank you."<<endl;
    char cha;
    cin >>cha;
    if(cha=='Y'||cha=='y')
    {
        cout <<"Please enter your data ,thank you ~:";
        int dat1;
        cin >>dat1;
        creat_trees(p->lefttree,dat1);
    }
    if(cha=='n'||cha=='N') {cout <<"This node don't be created."<<endl;}
    if(cha!='n'&&cha!='N'&&cha!='Y'&&cha!='y')
    {
        cout <<"System Wrong!This node will not be created~"<<endl;
    }
    cout <<"Do you want to creat the rightchild? Enter 'Y' to continue else please enter 'N',thank you. "<<endl;
    cout <<"Otherwise this char will be created to be the data of the node."<<endl;
    char cha2;
    cin >>cha2;
    if(cha2=='Y'||cha2=='y')
    {
        cout <<"Please enter your data ,thank you ~:";
        int dat2;
        cin >>dat2;
        creat_trees(p->righttree,dat2);
    }
    if(cha=='n'||cha=='N') cout <<"This node don't be created."<<endl;
    if(cha!='n'&&cha!='N'&&cha!='Y'&&cha!='y')
    cout <<"System Wrong!This node will not be created~"<<endl;
    cout <<"Complete!~"<<endl;
    return;
}

void bstree :: judge(node *r,int &flag)
{
	if(r->lefttree==NULL&&r->righttree==NULL) return;
	if(r->lefttree->data>r->data)
	{
		cout <<"It's not bst tree"<<endl;
		flag=1;
		return ;
	}
	if(r->righttree->data<r->data)
	{
		cout <<"It's not bst tree"<<endl;
		flag=1;
		return ;
	}
	else
	{
		if(r->lefttree!=NULL){judge(r->lefttree,flag);}
		if(r->righttree!=NULL){judge(r->righttree,flag);}
	}
	return ;
}