//Implemantacao da estrutura nao linear do tipo ARVORE BINARIA DE PESQUISA.
/* **************************************************** */
/* Definicao da classe arvBpesq - Representacao da arvore binaria pesquisa*/



#include <list>

template <class K, class T>
class arvBpesq : public arvBinaria<T>
{	
	//----------------------------------------------
	//	métodos acrescentados Est. Info. 2000/2001
	//----------------------------------------------

	Nodo<T>* inserir(Nodo<T>* p, const T& x);
	bool pesquisar_r(Nodo<T>* p, const K& chave, T& x);
	int findall(Nodo<T>* p, const K& chave, list<T>& r);
	int findall(Nodo<T>* p, list<T>& r);

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

public:
	bool pesquisar(const K& chave, T& x) const;
	void juntar_no(const K& chave, const T& x);
	void eliminar(const K& chave, T& x);

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

	void inserir(const T& x)
	{
		raiz = inserir(raiz, x);
	}

	bool pesquisar_r(const K& chave, T& x)
	{
		return pesquisar_r(raiz, chave, x);
	}

	int findall(const K& chave, list<T>& r)
	{
		return findall(raiz, chave, r);
	}

	int findall(list<T>& r)
	{
		return findall(raiz, r);
	}

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

template <class K,class T>
bool arvBpesq<K,T>::pesquisar( const K & chave,T & x) const
{
	Nodo<T> *temp =raiz;	bool enc = false;
	while (temp!=NULL && !enc)	
	{
		if(temp->info > chave)
		{
			cout<<"Esquerda"<<endl;
			temp = temp->esq;
		}
		else if(temp->info < chave)
		{
			cout<<"Direita"<<endl;
			temp = temp->dir;
		}
		else 
		{
			enc = true;
			x = temp->info;
			cout<<"ENCONTREI"<<endl;
		}
	}

	return enc;
}

template <class K,class T>
void arvBpesq<K,T>::juntar_no(const K& chave,const T& x)
{
	Nodo<T>* temp = raiz;
	Nodo<T>* ant = NULL;

	while (temp != NULL)
	{
		if (temp->info == chave)
			return;
		else if (temp->info > chave)
		{
			ant = temp;
			temp = temp->esq;
		}
		else 
		{
			ant = temp;
			temp = temp->dir;
		}
	}

	Nodo<T>* novoNo = new Nodo<T>(x);

	if (ant == NULL)
		raiz = novoNo;
	else if (ant->info >chave)
		ant->esq = novoNo;
	else
		ant->dir = novoNo;
}



template <class K,class T>
void arvBpesq<K,T>::eliminar(const K & chave,T & x)
{
	Nodo<T>* temp = raiz;
	Nodo<T>* ant = NULL;

	bool enc = false;
	while(temp!=NULL && !enc)
	{
		if(temp->info==chave)
		{
			enc = true;
			x=temp->info;
		}
		else if(temp->info<chave)
		{
			ant = temp;
			temp = temp->dir;
		}
			else
			{
				ant = temp;
				temp = temp->esq;
			}
	}

	if(enc)
	{
		if(temp->esq == NULL)
		{
			if(ant == NULL)
			{
				temp = temp->dir;
				delete raiz;
				raiz = temp;
			}
			else 
			{
				if(ant->info < chave)
					ant->dir = temp->dir;
				else
					ant->esq = temp->dir;
				delete temp;
			}
		}
		else
		{
			Nodo<T>* q = temp->esq;
			Nodo<T>* p = q->dir;
			if(p == NULL)
			{
				temp->info = q->info;
				temp->esq = q->esq;
				delete q;
			}
			else
			{
				while (p->dir != NULL)
				{
					q = p;
					p = p->dir;
				}
				temp->info = p->info;
				q->dir = p->esq;
				delete p;
			}
		}
	}
	else 
		cout<<"Nao é possivel eliminar"<<endl;
}


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

	
template <class K,class T>	
Nodo<T>* arvBpesq<K,T>::inserir(Nodo<T>* p, const T& x)
{
	if (p == NULL)
		return new Nodo<T>(x);

	if (getChave(x) < getChave(p->info))
		p->esq = inserir(p->esq, x);
	else
		p->dir = inserir(p->dir, x);
	return p;
}
/*
template <class K,class T>	
void arvBpesq<K,T>::inserir(Nodo<T>*& p, const T& x)	// p é uma referencia para um ponteiro
{
	if (p == NULL)
		p = new Nodo<T>(x);

	if (getChave(x) < getChave(p->info))
		inserir(p->esq, x);
	else
		inserir(p->dir, x);
}
*/

template <class K,class T>	
bool arvBpesq<K, T>::pesquisar_r(Nodo<T>* p, const K& chave, T& x)
{
	if (p == NULL)
		return false;

	if (chave == getChave(p->info))
	{
		x = p->info;
		return true;
	}
	else if (chave < getChave(p->info))
		return pesquisar_r(p->esq, chave, x);
	else
		return pesquisar_r(p->dir, chave, x);
}

template <class K,class T>	
int arvBpesq<K, T>::findall(Nodo<T>* p, const K& chave, list<T>& r)
{
	if (p == NULL)
		return r.size();

	if (getChave(p->info) > chave && r.size() > 0)
		return r.size();

	if (chave == getChave(p->info))
	{
		r.push_front(p->info);
		return findall(p->dir, chave, r);
	}
	else if (chave < getChave(p->info))
		return findall(p->esq, chave, r);
	else
		return findall(p->dir, chave, r);

}

template <class K,class T>	
int arvBpesq<K, T>::findall(Nodo<T>* p, list<T>& r)
{
	if (p == NULL)
		return r.size();

	findall(p->esq, r);
	r.push_back(p->info);
	return findall(p->dir, r);
}

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


/* Fim da classe Arvore Binaria */
/* **************************************************** */