#include<iomanip.h>
#include<malloc.h>
#include<iostream.h>
#include<process.h>
#define tip_element int
class nod
{
	friend class arbin;
	tip_element info;
	nod *ss,*sd;

public:
	nod (tip_element k, nod *s=NULL,nod *d=NULL):info(k),ss(s),sd(d){}
	/*friend ostream &operator<<(ostream &os,nod *n)
	{
		os<<nod->info;
		return os;
	}*/
};

class  arbin
{
private:
	nod *rad;
	int nrn;
	nod *ins(nod*,tip_element);
	void sterge_arb(nod*);
	void preord(nod*);
	void inord(nod *);
	void *copiere(nod *);
	void sterge_nod(nod *&,tip_element);
	tip_element sterg(nod *&);
	bool egal(nod *,nod*);
	int inalt (nod *);
	bool cauta(nod *, tip_element);
	bool frunza(nod *r) {return r->ss=NULL && r->sd==NULL;}
	friend int max(int a,int b){ return a>b?a:b;}
public:
	arbin():rad(NULL),nrn(0){}
	void afis_RSD(){preord(rad);}
	void afis_SRD(){inord(rad);}
	int count(){ return nrn;}
	bool este_vid(){return rad=NULL;}
	int inaltimea(){return inalt(rad);}
	arbin & operator<<(tip_element k) { rad=ins(rad,k);return *this;}
    	arbin &operator= (arbin &a);
     arbin &operator -= (tip_element k)  { sterge_nod (rad,k);return *this;}
	 bool operator == (arbin &a) {return egal(rad,a.rad);}
	 bool operator == (tip_element k) { return cauta(rad,k);}
    friend ostream & operator <<(ostream & os,arbin &a)
	{
		a.afis_RSD();return os;
	}
	~arbin() {sterge_arb(rad);}
};
  
int arbin::inalt(nod *r)
{
	if(r) return 1 + max(inalt(r->ss),inalt(r->sd));
	else return 0;
}

void arbin::preord(nod *r)
{
	if(r)
	{
		cout<<r;
		if(!frunza(r))
		{
			cout<<"(";
			preord(r->ss);
			cout<<",";
			preord(r->sd);
			cout <<")";
		}
	}
	else cout<<".";
}


void arbin::inord(nod *r)
{
	if(r)
	{
		if(frunza(r))
		{ cout<<"(" ;inord(r->ss);cout<<")";}
	     cout<<r;
		 if(!frunza(r)){cout<<"(";inord(r->sd);cout<<")";}
	}
else cout<<".";	
}

nod *arbin::ins(nod *r,tip_element k)
{
	if(r)
	{
		if(k==r->info);
		else if(k>r->info) r->sd=ins(r->sd,k);
		 else r->ss=ins(r->ss,k);
		 return r;
	}
	else return nrn++,new nod(k);
}
arbin & arbin::operator =(arbin &srs)
{
	if(rad) sterge_arb(rad);
	rad=NULL;
	nrn=srs.nrn;
	//rad=copiere(srs.rad);
	return *this;
}

void arbin::sterge_arb(nod *r)
{
	if(r)
	{
		sterge_arb(r->ss);
		sterge_arb(r->sd);
		delete r;
	}
}


nod *arbin::copiere(nod *r)
{

if(r) return new nod((r->info),copiere(r->ss),copiere(r->sd));
	else return NULL;
}

bool arbin::egal(nod *r1,nod *r2)
{
	if(!r1) return r2=NULL;
	   else if(!r2) return false;
	   else return r1->info=r2.info && egal(r1->ss,r2->ss) && egal(r1->sd,r2->sd);
}

bool arbin::cauta(nod *r,tip_element k)
{
	if(!r) return false;
	else if(k==r->info) return true;
	 else if(k>r->info) return cauta(r->sd,k);
	 else return cauta(r->ss,k);
}

//** stergerea unui nod dintr-un arbore

void arbin::sterge_nod(nod *&r,tip_element k)
{
  nod *aux;
if(!r) cout<<"\n Nodul inexistent!!"<<endl; else 
if(k=r->info)
	{
	  aux =r;
	  if(!aux->sd){ r=aux->ss;delete aux;}
	  else if(!aux->ss) {r=aux->sd;delete aux;}
	  else
		   r->info=sterg(r->sd);
	}
else if(k>r->info) sterge_nod(r->sd,k);
  else sterge_nod(r->ss,k);
}

void main()
{
	arbin a,b;

	a<<56<<12<<34<<90<<67<<80<<110;
	a.afis_RSD();
	cout<<"ARborele are" <<a.count()<<"noduri!"<<endl;
 cout<<a<<endl;
	b=a;b.afis_SRD();
	//testare daca doi arbori sunt identici
	if(a==b) cout<<"\nArbbori identici!"<<endl;
	else cout<<"\nArbori diferiti!!"<<endl;
	//determinare ianltimii unuio arbore
	cout<<"\nInaltimea arborelui este de"<<a.inaltimea()<<"niveluri";
}