//Implemantacao da estrutura nao linear do tipo ARVORE BINARIA.

/* Definicao da classe Nodo - representa o nodo da arvore binaria */
template <class T>
class Nodo
{
	public:
		T info;
		Nodo<T> *esq;
		Nodo<T> *dir;
		Nodo();
		Nodo(const T & e);
		Nodo(const T & e,Nodo<T> *esq1,Nodo<T> *dir1);
};

template<class T>
Nodo<T>::Nodo()
{
	esq=dir=NULL;
}
template<class T>
Nodo<T>::Nodo(const T & e)
{
	info = e;
	esq=dir=NULL;
}
template<class T>
Nodo<T>::Nodo(const T & e,Nodo<T> *esq1,Nodo<T> *dir1)
{
	info=e;
	esq=esq1;
	dir=dir1;
}

		//----------------------------------------------
		//	métodos acrescentados Est. Info. 2000/2001
		//----------------------------------------------

		enum direccao {esquerda, direita };

		//----------------------------------------------
		//	(fim) métodos acrescentados 
		//----------------------------------------------



/* Fim da classe Nodo */
/* **************************************************** */
/* Definicao da classe arvBinaria - representa a arvore binaria */
template <class T>
class arvBinaria
{
	protected:
		Nodo<T> *raiz;
		void destroiArv(Nodo<T> * raiz);
		void preOrdem(Nodo<T> *raiz) const;
		void postOrdem(Nodo<T> *raiz) const;
		void ordemSimetrica(Nodo<T> *raiz) const;
		Nodo<T> *eliminar(const T & x,Nodo<T> *rz,int &enc);
		Nodo<T> *pesquisar(const T & x,Nodo<T> *rz) const;

		//----------------------------------------------
		//	métodos acrescentados Est. Info. 2000/2001
		//----------------------------------------------
		
		int numNos(Nodo<T>* p) const;
		int numNosFolha(Nodo<T>* p) const;
		int numNosInternos(Nodo<T>* p) const;
		int numNosNivel(int nNivel, Nodo<T>* p, int nNivelActual) const;
		Nodo<T>* copia(const Nodo<T>* p);

		//----------------------------------------------
		//	3º mini-teste Est. Info. 2000/2001
		//----------------------------------------------


		static bool _dif(const Nodo<T>* a1, const Nodo<T>* a2);
		static bool _iguais(const Nodo<T>* a1, const Nodo<T>* a2);
		static void _uniao(const Nodo<T>* a2, arvBinaria<T>& c);
		static void _interseccao(const Nodo<T>* a1, const arvBinaria<T>& a2, arvBinaria<T>& c);


		//----------------------------------------------
		//	(fim) métodos acrescentados 
		//----------------------------------------------

public:
		arvBinaria();
		~arvBinaria();
		
		bool vazia() const;
		void preOrdem() const
		{ preOrdem(this->raiz); return; }
		void postOrdem() const
		{ postOrdem(this->raiz); return; }
		void ordemSimetrica() const
		{ ordemSimetrica(this->raiz); return; }
		void fazerArv(const T & elem,arvBinaria<T> & a1,arvBinaria<T> & a2);
		bool pesquisar(const T & x) const;
		arvBinaria<T> & eliminar(const T & x);	
		

		//----------------------------------------------
		//	métodos acrescentados Est. Info. 2000/2001
		//----------------------------------------------
		
		void criaRaiz(const T& valor);
		void criaNo(const T& valor, direccao dir, const T& pai);
		int numNos() const	
			{ return numNos(raiz); }
		int numNosFolha() const
			{ return numNosFolha(raiz); }
		int numNosInternos() const
			{ return numNosInternos(raiz); }
		int numNosNivel(int nNivel) const
			{ return numNosNivel(nNivel, raiz, 0); }
		arvBinaria(const arvBinaria& o);
		arvBinaria& operator=(const arvBinaria& o);

		//----------------------------------------------
		//	3º mini-teste Est. Info. 2000/2001
		//----------------------------------------------

		arvBinaria<T> subArvore(const T& x) const;

		bool operator==(const arvBinaria<T>& a2);
		bool operator!=(const arvBinaria<T>& a2);
		arvBinaria<T> operator*(const arvBinaria<T>& a2);
		arvBinaria<T> operator+(const arvBinaria<T>& a2);

		//----------------------------------------------
		//	(fim) métodos acrescentados 
		//----------------------------------------------
};


		//----------------------------------------------
		//	3º mini-teste Est. Info. 2000/2001
		//----------------------------------------------
/*
template <class T>
bool operator==(const arvBinaria<T>& a1, const arvBinaria<T>& a2);

template <class T>
bool operator!=(const arvBinaria<T>& a1, const arvBinaria<T>& a2);

template <class T>
arvBinaria<T> operator*(const arvBinaria<T>& a1, const arvBinaria<T>& a2);

template <class T>
arvBinaria<T> operator+(const arvBinaria<T>& a1, const arvBinaria<T>& a2);
*/
		//----------------------------------------------
		//	(fim) métodos acrescentados 
		//----------------------------------------------


template <class T>
arvBinaria<T>::arvBinaria()
{
	raiz = NULL;
}
template <class T>
arvBinaria<T>::~arvBinaria()
{
	//cout <<"Estou no destrutor"<<endl;
	destroiArv(raiz);
}
template <class T>
void arvBinaria<T>::destroiArv(Nodo<T> * raiz)
{
	if (raiz !=NULL)
	{
		destroiArv(raiz->esq);
		destroiArv(raiz->dir);
		delete raiz;
	}
}
template <class T>
bool arvBinaria<T>::vazia() const
{
	return (raiz==NULL);
}
template <class T>
void arvBinaria<T>::preOrdem(Nodo<T> *raiz) const
{
	if (raiz!=NULL)
	{
		cout<< raiz->info << endl; 
		preOrdem(raiz->esq);
		preOrdem(raiz->dir);
	}
	return;
}

template <class T>
void arvBinaria<T>::postOrdem(Nodo<T> *raiz) const
{
	if (raiz!=NULL)
	{ 
		postOrdem(raiz->esq);
		postOrdem(raiz->dir);
		cout<< raiz->info << endl;
	}
	return;
}

template <class T>
void arvBinaria<T>::ordemSimetrica(Nodo<T> *raiz) const
{
	if (raiz!=NULL)
	{
		ordemSimetrica(raiz->esq);
		cout<< raiz->info << endl; 
		ordemSimetrica(raiz->dir);
	}
	return;
}
template<class T>
void arvBinaria<T>::fazerArv(const T & elem,arvBinaria<T> & a1,arvBinaria<T> & a2)
{
	raiz = new Nodo<T>(elem,a1.raiz,a2.raiz);
	
	a1.raiz=a2.raiz=NULL;
}

template<class T>
bool arvBinaria<T>:: pesquisar(const T & x) const
{
	Nodo<T> *temp;
	temp=pesquisar(x,this->raiz);
	if(temp!=NULL) 
	{
		//cout <<temp->info;
		return true;
	}
	else 
		return false;
}

template<class T>
Nodo<T> * arvBinaria<T>::pesquisar(const T & x,Nodo<T> *rz) const
{
	Nodo<T> * n;
	if(rz)
	{
		if(rz->info==x)
			return rz;
		n=pesquisar(x,rz->esq);
		if(n==NULL)
			return pesquisar(x,rz->dir);
		return n;
	}
	else return NULL;

}

template<class T>
arvBinaria<T>& arvBinaria<T>::eliminar(const T & x)
{
	int enc=0;
	raiz=eliminar(x,raiz,enc);
	return *this;
}

template<class T>
Nodo<T>* arvBinaria<T>::eliminar(const T & x,Nodo<T> *rz,int &enc)
{
	if(rz==NULL)
		return rz;
	if(rz->info==x)
	{
		destroiArv(rz);
		enc=1;
		return NULL;
	}
	
	rz->esq=eliminar(x,rz->esq,enc);
	if (enc==0)
		rz->dir=eliminar(x,rz->dir,enc);
	return rz;
}


		//----------------------------------------------
		//	métodos acrescentados Est. Info. 2000/2001
		//----------------------------------------------

template<class T>		
void arvBinaria<T>::criaRaiz(const T& valor)
{
	raiz = new Nodo<T>(valor, raiz, NULL);
}

template<class T>
void arvBinaria<T>::criaNo(const T& valor, direccao dir, const T& pai)
{
	Nodo<T>* p = pesquisar(pai, raiz);
	if (p != NULL)
	{
		Nodo<T>* n = new Nodo<T>(valor);
		if (dir == esquerda)
		{
			n->esq = p->esq;
			p->esq = n;
		}
		else
		{
			n->dir = p->dir;
			p->dir = n;
		}
	}
}

template<class T>
arvBinaria<T>::arvBinaria(const arvBinaria& o)
{
	raiz = copia(o.raiz);
}

template<class T>
arvBinaria<T>& arvBinaria<T>::operator=(const arvBinaria<T>& o)
{
	destroiArv(raiz);
	raiz = copia(o.raiz);
	return *this;
}

template<class T>
int arvBinaria<T>::numNos(Nodo<T>* p) const
{
	if (p == NULL)
		return 0;

	return 1 + numNos(p->esq) + numNos(p->dir);
}

template<class T>
int arvBinaria<T>::numNosFolha(Nodo<T>* p) const
{
	if (p == NULL)
		return 0;

	if (p->esq == NULL && p->dir == NULL)
		return 1;

	return numNosFolha(p->esq) + numNosFolha(p->dir);
}

template<class T>
int arvBinaria<T>::numNosInternos(Nodo<T>* p) const
{
	if (p == NULL)
		return 0;

	if (p->esq == NULL && p->dir == NULL)
		return 0;

	return 1 + numNosInternos(p->esq) + numNosInternos(p->dir);
}

template<class T>
int arvBinaria<T>::numNosNivel(int nNivel, Nodo<T>* p, int nNivelActual) const
{
	if (p == NULL)
		return 0;

	if (nNivelActual == nNivel)
		return 1;

	return numNosNivel(nNivel, p->esq, nNivelActual+1) + numNosNivel(nNivel, p->dir, nNivelActual+1);
}

template<class T>
Nodo<T>* arvBinaria<T>::copia(const Nodo<T>* p)
{
	if (p == NULL)
		return NULL;

	Nodo<T>* n = new Nodo<T>(p->info);
	n->esq = copia(p->esq);
	n->dir = copia(p->dir);

	return n;
}

		//----------------------------------------------
		//	3º mini-teste Est. Info. 2000/2001
		//----------------------------------------------

template <class T>
arvBinaria<T> arvBinaria<T>::subArvore(const T& x) const
{
	arvBinaria<T> c;
	Nodo<T>* p = pesquisar(x, raiz);
	if (p != NULL)
		c.copia(p);
	return c;
}

template <class T>
bool arvBinaria<T>::_iguais(const Nodo<T>* a1, const Nodo<T>* a2)
{
	if (a1 == NULL && a2 == NULL)
		return true;

	if (a1 == NULL || a2 == NULL)
		return false;

	if (a1->info != a2->info)
		return false;

	if (!_iguais(a1->esq, a2->esq))
		return false;

	return _iguais(a1->dir, a2->dir);
}


template <class T>
bool arvBinaria<T>::operator==(const arvBinaria<T>& a2)
{
	return arvBinaria<T>::_iguais(this->raiz, a2.raiz);
}

template <class T>
bool arvBinaria<T>::_dif(const Nodo<T>* a1, const Nodo<T>* a2)
{
	if (a1 == NULL && a2 == NULL)
		return false;

	if (a1 == NULL || a2 == NULL)
		return true;

	if (a1->info != a2->info)
		return true;

	if (_dif(a1->esq, a2->esq))
		return true;

	return _dif(a1->dir, a2->dir);
}

template <class T>
bool arvBinaria<T>::operator!=(const arvBinaria<T>& a2)
{
	return arvBinaria<T>::_dif(this->raiz, a2.raiz);
}

template <class T>
void arvBinaria<T>::_interseccao(const Nodo<T>* a1, const arvBinaria<T>& a2, arvBinaria<T>& c)
{
	if (a1 == NULL)
		return;

	if (a2.pesquisar(a1->info))
		c.criaRaiz(a1->info);

	_interseccao(a1->esq, a2, c);
	_interseccao(a1->dir, a2, c);
}

template <class T>
arvBinaria<T> arvBinaria<T>::operator*(const arvBinaria<T>& a2)
{
	arvBinaria<T> c;
	arvBinaria<T>::_interseccao(this->raiz, a2, c);
	return c;
}

template <class T>
void arvBinaria<T>::_uniao(const Nodo<T>* a2, arvBinaria<T>& c)
{
	if (a2 == NULL)
		return;

	if (!c.pesquisar(a2->info))
		c.criaRaiz(a2->info);

	_uniao(a2->esq, c);
	_uniao(a2->dir, c);
}

template <class T>
arvBinaria<T> arvBinaria<T>::operator+(const arvBinaria<T>& a2)
{
	arvBinaria<T> c(*this);
	_uniao(a2.raiz, c);
	return c;
}

		//----------------------------------------------
		//	(fim) métodos acrescentados 
		//----------------------------------------------