package util;

public class Arvore {
	private Celula raiz;
	private int size;
	
	private class Celula implements Element{//a classe implementa a interface element pra não acessar os
		private Object data;                //dados diretamente
		private Celula pai;
		private Celula noEsquerda;
		private Celula noDireita;
		
		public Celula(Comparable data, Celula noEsquerda, Celula noDireita){
			this.data = data;
			this.noDireita = noDireita;
			this.noEsquerda = noEsquerda;
		}
		
		public Celula getPai(){
			return pai;
		}
		
		public void setPai(Celula n){
			this.pai = n;
		}
		
		public Celula getNoEsquerda(){
			return noEsquerda;
		}
		
		public void setNoEsquerda(Celula n){
			this.noEsquerda = n;
		}
		
		public Celula getNoDireita(){
			return noDireita;
		}
		
		public void setNoDireita(Celula n){
			this.noDireita = n;
		}
		
		@Override
		public Object getData() {
			return data;
		}
		
		public void setData(Object o){
			this.data = o;
		}
	}
	
	public void addRaiz(Comparable o){
		if(raiz == null){
			raiz = inserir(o, raiz);
		}
	}
	
	public Element getRaiz(){
		return raiz;
	}
	
	public Celula inserir(Comparable o, Celula n){
		if(n == null){
			n = new Celula(o, null, null);
		}else{
			
			if(o.compareTo(n.getData()) < 0){
				if(n.getNoEsquerda() != null){
					inserir(o, n.getNoEsquerda());
				} 
				else{
					n.setNoEsquerda(new Celula(o, n, null));
				}
			}
			
			else if(o.compareTo(n.getData()) > 0){
				if(n.getNoDireita() != null){
					inserir(o, n.getNoDireita());
				}
				else{
					n.setNoEsquerda(new Celula(o, null, n));
				}
			}
		}
		size++;
		return n;
	}
	
	public void remove(Element e){
		Celula n = (Celula) e;
		
		if(n.getNoEsquerda() != null && n.getNoDireita() != null){
			n.setData(n.getNoEsquerda().getData());
			remove(n.getNoEsquerda());
		}
		
		else if(n.getNoEsquerda() != null || n.getNoDireita() != null){
			Celula c = n.getNoEsquerda() != null ? n.getNoEsquerda() : n.getNoDireita();
			replace(n, c);
		}
		
		else{
			replace(n, null);
		}
		
		size--;
	}
	
	private void replace (Celula n, Celula c){
		if(n == raiz){
			raiz  = c;
		}
		else{
			if(n == n.getPai().getNoEsquerda()){
				n.getPai().setNoEsquerda(c);
			}
			else{
				n.getPai().setNoDireita(n);
			}
		}
	}
	
	public class Iterador implements Iterator{// o iterador é usado com fila, pra isso eu implementei ela 
		private IFila fila = new Fila();	//e instanciei através da interface
		
		public Iterador(){
			fila.inserirFinal(raiz);
		}
		
		@Override
		public boolean temProximo() {
			if(fila.estaVazia() == true){
				return false;
			}
			
			return true;
		}

		@Override
		public Object obterProximo() {//esse metodo ele pega os filhos da direita e da esquerda e coloca na fila
			Celula n = (Celula) fila.remover();
			
			if(n.getNoDireita() != null){
				fila.inserirFinal(n.getNoDireita());
			}
			
			if(n.getNoEsquerda() != null){
				fila.inserirFinal(n.getNoEsquerda());
			}
			
			return n.getData();
		}
		
	}
	
	
}



@@ -1697,32 +1697,736 @@
 return n;%0D%0A%09%7D%0D%0A%09
+public boolean busca(Celula c, String chave)%7B%0D%0A%09%09if (c.getData() == null)%7B // Se n%C3%A3o houver nada na celula.%0D%0A%09%09%09return false; // A arvore ta vazia retorna false.%09%09%09%09%0D%0A%09%09if (((String) c.getData()).compareTo(chave) = 0) %7B // Se o data da celula for igual a chave de busca.%0D%0A%09%09%09return true;%09%09%09// A raiz %C3%A9 igual a chave, retorna true.%0D%0A%09%09%7D%0D%0A%09%09else if(((String) c.getData()).compareTo(chave) %3C 0)%7B // Se o data da celula for maior do que a chave de busca.%0D%0A%09%09%09return busca(c.getNoEsquerda(),chave); // chamada recursiva passando o no da esquerda.%0D%0A%09%09%7D%0D%0A%09%09else%7B //Se o data for menor do que a chave de busca %0D%0A%09%09%09return busca(c.getNoDireita(),chave); // chamada recursiva passando o no da direita.%09%09%0D%0A%09%09%7D%0D%0A%0D%0A%09%7D
 %0D%0A%09public void r

Update Arvore.java