ArvoreBuscaBinaria.java

/**
 * Representa uma árvore formada por nós com, no máximo, dois filhos.
 * Possui apenas a referência para a raiz, de onde partem todos as 
 * buscas.
 * 
 * As árvores de busca binária têm uma propriedade em todos os nós:
 * os valores menores ficam na sub-árvore à esquerda e os valores 
 * maiores ficam na sub-árvore à direita.  
 *
 */
public class ArvoreBuscaBinaria {

	/**
	 * Raiz da árvore
	 */
	private No raiz;

	/**
	 * Adiciona um valor na árvore de busca binária mantendo
	 * as propriedades da busca nos nós.
	 */
	public void add(int valor) {
		
		if (raiz == null) {
			raiz = new No();
			raiz.setValor(valor);
			return;
		}
		
		No atual = raiz;
		
		addRecursivo(valor, atual);

	}

	/**
	 * Tenta adicionar um valor como filho do nós atual.
	 * Se o espaço já estiver ocupado, caminha recursivamente
	 * nos nós filhos.
	 * 
	 * @param valor Valor a ser adicionado na árvore.
	 * @param atual Nó que está sendo analisado
	 */
	protected void addRecursivo(int valor, No atual) {
		if (valor == atual.getValor()) {
			throw new RuntimeException("Já tem " + valor);
		}
		
		if (valor < atual.getValor()) {
			addEsquerda(valor, atual);
			
		} else {
			addDireita(valor, atual);
		}
	}

	protected void addEsquerda(int valor, No atual) {
		No esquerda = atual.getEsquerda();
		if (esquerda == null) {
			No novo = new No();
			novo.setValor(valor);
			novo.setPai(atual);
			atual.setEsquerda(novo);
		} else {
			addRecursivo(valor, esquerda);
		}
	}

	protected void addDireita(int valor, No atual) {
		No direita = atual.getDireita();
		
		if (direita == null) {
			No novo = new No();
			novo.setValor(valor);
			novo.setPai(atual);
			atual.setDireita(novo);
		} else {
			addRecursivo(valor, direita);
		}
	}

	/**
	 * Verifica se um valor está presente na árvore atual.
	 * @param valor Valor a ser procurado
	 * @return -1 se o valor não existir ou a quantidade de níveis buscados para
	 * encontrar o valor
	 */
	public int contains(int valor) {
		return containsRecursivo(valor, raiz, 0);
	}

	/**
	 * Caminha recursivamente na árvore, em busca de um valor
	 * @param valor Valor a ser procurado
	 * @param atual Nó que está sendo analisado agora
	 * @param nivel Nível do pai do nó atual
	 * @return -1 se o valor não existir ou a quantidade de níveis buscados para
	 * encontrar o valor
	 */
	private int containsRecursivo(int valor, No atual, int nivel) {
		if (atual == null) {
			return -1;
		}
		
		if (atual.getValor() == valor) {
			return nivel + 1;
		}
		
		if (valor < atual.getValor()) {
			return containsRecursivo(valor, atual.getEsquerda(), ++nivel);
		} else {
			return containsRecursivo(valor, atual.getDireita(), ++nivel);
		}
	}

	public void imprimir() {
		imprimirPosOrdem(raiz);
	}

	private void imprimirPosOrdem(No atual) {
		if (atual == null) {
			return;
		}
		
		imprimirPosOrdem(atual.getEsquerda());	 	//ESQ
		
		imprimirPosOrdem(atual.getDireita());		//DIR

		System.out.print(atual.getValor() + " "); 	//ATUA
	}
	
	private void imprimirInOrdem(No atual) {
		if (atual == null) {
			return;
		}
		
		imprimirInOrdem(atual.getEsquerda());	 	//ESQ
		
		System.out.print(atual.getValor() + " "); 	//ATUA
		
		imprimirInOrdem(atual.getDireita());			//DIR
	}

	private void imprimirPreOrdem(No atual) {
		if (atual == null) {
			return;
		}
		
		System.out.print(atual.getValor() + " "); 	//ATUA
		
		imprimirPreOrdem(atual.getEsquerda());	 	//ESQ
		
		imprimirPreOrdem(atual.getDireita());		//DIR
	}

	public int tamanho() {
		return tamanhoPreOrdem(raiz);
	}

	private int tamanhoInOrdem(No atual) {
		if (atual == null) {
			return 0;
		}
		
		return 	
				tamanhoInOrdem(atual.getEsquerda())	 	//ESQ
				+ 1 										//ATUA
				+ tamanhoInOrdem(atual.getDireita());	//DIR
	}
	
	private int tamanhoPreOrdem(No atual) {
		if (atual == null) {
			return 0;
		}
		
		return 	
				1 										//ATUA
				+ tamanhoPreOrdem(atual.getEsquerda())	//ESQ
				+ tamanhoPreOrdem(atual.getDireita());	//DIR
	}
}

/**
 * Representa um nó de uma árvore de busca binária.
 * Possui referências para os dois filhos possíveis (esquerda e direita), 
 * para o nó pai e o valor armazenado.
 *
 */
class No {

	private int valor;
	private No direita, esquerda, pai;

	public int getValor() {
		return valor;
	}

	public void setValor(int valor) {
		this.valor = valor;
	}

	public No getDireita() {
		return direita;
	}

	public void setDireita(No direita) {
		this.direita = direita;
	}

	public No getEsquerda() {
		return esquerda;
	}

	public void setEsquerda(No esquerda) {
		this.esquerda = esquerda;
	}

	public No getPai() {
		return pai;
	}

	public void setPai(No pai) {
		this.pai = pai;
	}

}

ArvoreBuscaBinariaTest.java

import static org.junit.Assert.*;

import org.junit.Test;

public class ArvoreBuscaBinariaTest {

	@Test
	public void test() {
		ArvoreBuscaBinaria arvore = new ArvoreBuscaBinaria(); 
		arvore.add(21);
		arvore.add(15);
		arvore.add(14);
		arvore.add(70);
		arvore.add(16);
		arvore.add(82);
		arvore.add(65);
		arvore.add(61);
		arvore.add(68);
		arvore.add(18);
		arvore.add(17);
		
		assertEquals(3, arvore.contains(16));
		assertEquals(2, arvore.contains(70));
		assertEquals(1, arvore.contains(21));
		assertEquals(4, arvore.contains(68));
		assertEquals(5, arvore.contains(17));
		
		assertEquals(-1, arvore.contains(100));
		assertEquals(-1, arvore.contains(0));
		assertEquals(-1, arvore.contains(63));
		
		assertEquals(11, arvore.tamanho());
		
		arvore.imprimir();
	}

}