ArvoreDeBuscaBinaria.java

/*
 *	Utiliza a classe No 
 */
public class ArvoreDeBuscaBinaria {

	public static void main(String [] args){
		No Arvore = new No(45);
		insereArvore(Arvore, 56);
		insereArvore(Arvore, 67);
		insereArvore(Arvore, 24);
		insereArvore(Arvore, 61);
		insereArvore(Arvore, 52);
		
		System.out.print("Pre : ");
		preOrdem(Arvore);
		System.out.print("\nEm  : ");
		emOrdem(Arvore);
		System.out.print("\nPos : ");
		posOrdem(Arvore);
		
		excluiArvore(Arvore, 45);
		excluiArvore(Arvore, 24);
		excluiArvore(Arvore, 56);
		
		System.out.println("\n");

		System.out.print("Pre : ");
		preOrdem(Arvore);
		System.out.print("\nEm  : ");
		emOrdem(Arvore);
		System.out.print("\nPos : ");
		posOrdem(Arvore);

		System.out.println("\n");
		
		int chave = 56;
		if(buscaBinaria(Arvore, chave) != null)
			System.out.println("\nEncontrou a chave " + chave);
		else
			System.out.println("\nNao encontrou a chave " + chave);
		
		System.out.println("Altura da arvore : " + alturaArvore(Arvore) );
	}
	
	public static No buscaBinaria(No no, int chave){
		while(no != null){
			if(no.getChave() == chave)
				return no;
			if(chave > no.getChave())
				no = no.getDir();
			else
				no = no.getEsq();
		}
		return null;
	}
	
	public static No buscaNoPai(No atual, int ch){
		No noPai = null;
		while( atual != null ){
			if( atual.getChave() == ch )
				return noPai;
			noPai = atual;
			if( atual.getChave() < ch )
				atual = atual.getDir();
			else
				atual = atual.getEsq();
		}
		return noPai;
	}

	public static No maiorAesquerda(No atual){
		atual = atual.getEsq();
		while( atual.getDir() != null )
			atual = atual.getDir();
		return atual;
	}
	
	public static boolean excluiArvore(No no, int chave){
		No atual, noPai, substituto;
		substituto = null;
		atual = buscaBinaria(no, chave);
		if( atual == null ) return false; // Não encontrou a chave
		noPai = buscaNoPai(no, chave);
		if( atual.getEsq() == null || atual.getDir() == null ){ // Se tem 0 ou 1 filho
			if( atual.getEsq() == null ){
				substituto = atual.getDir();
			}else{
				substituto = atual.getEsq();
			}
			if( noPai == null ){ // Único que não tem pai é a raiz
				no.setChave(substituto.getChave());
				no.setEsq(substituto.getEsq());
				no.setDir(substituto.getDir());
			}else{
				if(chave < noPai.getChave())
					noPai.setEsq(substituto);
				else
					noPai.setDir(substituto);
			}
		}else{
			substituto = maiorAesquerda(atual);
			atual.setChave(substituto.getChave());
			if( substituto.getEsq() != null )
				atual.setEsq(substituto.getEsq());
			else
				atual.setEsq(null);
		}
		
		return true;
	}
	
	public static void insereArvore(No arvore, int chave){
		No anterior = arvore;
		while(arvore != null){
			anterior = arvore;
			if(arvore.getChave() < chave)
				arvore = arvore.getDir();
			else
				arvore = arvore.getEsq();
		}
		No novo = new No(chave);
		if(anterior.getChave() < chave)
			anterior.setDir(novo);
		else
			anterior.setEsq(novo);
	}
	
	public static void preOrdem(No no){
		if(no != null){
			System.out.print(no.getChave() + ", ");
			preOrdem(no.getEsq());
			preOrdem(no.getDir());
		}
	}	
	
	public static void posOrdem(No no){
		if(no != null){
			posOrdem(no.getEsq());
			posOrdem(no.getDir());
			System.out.print(no.getChave() + ", ");
		}
	}
	
	public static void emOrdem(No no){
		if(no != null){
			emOrdem(no.getEsq());
			System.out.print(no.getChave() + ", ");
			emOrdem(no.getDir());
		}
	}
	
	public static int max(int a, int b){
		if(a > b)
			return a;
		return b;
	}
	
	public static int alturaArvore(No arvore){
		if(arvore == null)
			return 0;
		return 1 + max( alturaArvore(arvore.getEsq()), alturaArvore(arvore.getDir()) );
	}
	
}