TAD Árvore Binária

Objetivo: Escreva um programa que leia uma seqüência de números e monte uma Árvore Binária.

O programa deve ter as seguintes opções:

• Ler números digitados pelo usuário e montar a Árvore Binária ordenada;
• Remover um determinado elemento da árvore;
  Obs: Para simplificar permita remover somente "folhas".
• Verificar se a árvore está vazia;
• Percorrer a árvore pelos modos: preorder, inorder e posorder;
• Exibir a árvore na tela, de modo que a estrutura binária da árvore possa ser visualizada, ou seja, de maneira que possamos conferir a estrutura da árvore;
• Retornar a altura da árvore.

Classes:

Árvore:

import java.util.ArrayList;

public class Arvore {

// Atributo
private Elemento Raiz;

// Construtor recebe um Elemento Raiz para criar a árvore
public Arvore(Elemento Raiz){
this.Raiz = Raiz;
}

// Método SET
public void setRaiz(Elemento Raiz){
this.Raiz = Raiz;
}

// Método GET
public Elemento getRaiz(){
return this.Raiz;
}

// Método para inserir um novo elemento na árvore
public void InserirElemento(int Valor){

// O caminhamento na arvore vai começar a partir da raiz
Elemento ElementoAux = Raiz;

// Cria um novo elemento com o valor a ser inserido
Elemento NovoElemento = new Elemento(Valor);

// Inicia o caminhamento na árvore
while(ElementoAux != null){

// Verifica se o valor a ser inserido é maior que o valor do elemento atual
if(Valor > ElementoAux.getValor()){
// Verifica se elemento direito é diferente de nulo
if(ElementoAux.getElementoDireito() != null) // Se sim, pega o elemento direito para continuar a busca
ElementoAux = ElementoAux.getElementoDireito();
else{ // Se não, insere o elemento como o elemento direito
ElementoAux.setElementoDireito(NovoElemento);
ElementoAux = null;
}
// Valor a ser inserido menor que o valor do elemento atual
} else {
// Verifica se elemento esquero é diferente de nulo
if(ElementoAux.getElementoEsquerdo() != null) // Se sim, pega o elemento esquerdo para continuar a busca
ElementoAux = ElementoAux.getElementoEsquerdo();
else{ // Se não, insere o elemento como o elemento esquerdo
ElementoAux.setElementoEsquerdo(NovoElemento);
ElementoAux = null;
}
}
}
}

// Método para fazer o caminhamento "PreOrder"
public void PreOrder(Elemento Elemento){
if(Elemento != null){
System.out.printf("%d ", Elemento.getValor());
if(Elemento.Interno()){
PreOrder(Elemento.getElementoEsquerdo());
PreOrder(Elemento.getElementoDireito());
}
}
}

// Método para fazer o caminhamento "PostOrder"
public void PostOrder(Elemento Elemento){
if(Elemento != null){
if(Elemento.Interno()){
PostOrder(Elemento.getElementoEsquerdo());
PostOrder(Elemento.getElementoDireito());
}
System.out.printf("%d ", Elemento.getValor());
}
}

// Método para fazer o caminhamento "InOrder"
public void InOrder(Elemento Elemento){
if(Elemento != null){
if(Elemento.Interno()){
InOrder(Elemento.getElementoEsquerdo());
}
System.out.printf("%d ", Elemento.getValor());
if(Elemento.Interno()){
InOrder(Elemento.getElementoDireito());
}
}
}

// Método para remover um elemento
// Recebe como parâmetro um elemento e o valor a ser removido
public boolean Remover(Elemento Elemento, int Valor){
// Verifica se elemento é diferente de nulo
if(Elemento != null){
// Verifica se o valor do elemento é igual ao valor a ser removido
if(Elemento.getValor() == Valor){
// Verifica se o elemento é um elemento externo
if(!Elemento.Interno()) // Se sim, retorna verdadeiro, pois pode ser removido
return true;
else // Se não, retorna falso, pois não pode ser removido
return false;

// Se valor do elemento atual for diferente do valor a ser removido...
} else {

// Verifica se o elemento atual é um elemento interno
if(Elemento.Interno()){

boolean flag; // Flag para verificar se foi removido o elemento

flag = Remover(Elemento.getElementoEsquerdo(), Valor); // Chama a função remover recursivamente enviando o elemento esquerdo

// Verifica se foi removido o elemento
if(flag){
Elemento.setElementoEsquerdo(null); // Remove a ligação com o elemento
return false;
} else {

flag = Remover(Elemento.getElementoDireito(), Valor); // Chama a função remover recursivamente enviando o elemento direito

// Verifica se foi removido o elemento
if(flag){
Elemento.setElementoDireito(null); // Remove a ligação com o elemento
return false;
} else
return false;
}
}
}
}
return false;
}

// Método chamado para calcular Altura da árvore
public int Altura(){
return CalculaAltura(this.Raiz, 0);
}

// Método para calcular a Altura da árvore
// Recebe como parâmetro um elemento e a altura atual da contagem
private int CalculaAltura(Elemento Elemento, int Altura){
// Verifica se elemento é diferente de nulo
if(Elemento != null){

// Verifica se elemento atual é um elemento interno
if(Elemento.Interno()){
int AlturaAux1, AlturaAux2;
// Chama o método para Calcular altura recursivamente, enviando o elemento esquerdo e a altura atual + 1
AlturaAux1 = CalculaAltura(Elemento.getElementoEsquerdo(), Altura + 1);

// Chama o método para Calcular altura recursivamente, enviando o elemento direito e a altura atual + 1
AlturaAux2 = CalculaAltura(Elemento.getElementoDireito(), Altura + 1);

// Verifica qual dos lados teve a maior altura e retorna
if(AlturaAux1 > AlturaAux2)
return AlturaAux1;
else
return AlturaAux2;

// Se elemento atual é um elemento externo, apenas retorna a altura recebida
} else {
return Altura;
}
}
return 0;
}

// Método Auxiliar do método para imprimir
// Método Cria um Array onde cada posição do array representa um nível da arvore.
private ArrayList<object> BuscaPai(){

// Cria um array de niveis
ArrayList<object> ArrayNiveis = new ArrayList<object>();

// Cria um array auxiliar para fazer o laço
ArrayList<object> ArrayAux = new ArrayList<object>();
ArrayAux.add(this.Raiz); // Inicia o array com o elemento Raiz

ArrayNiveis.add(ArrayAux); // Adiciona no array de niveis o array contendo o elemento raiz

// Percorre o array auxiliar
while(ArrayAux.size() >= 1){

// Cria um array para receber o array do método BuscaFilhos
ArrayList<object> Array = new ArrayList<object>();

// Recebe o array do método BuscaFilhos
Array = BuscaFilhos(ArrayAux);

// Adiciona o array recebido no array de níveis
ArrayNiveis.add(Array);

// Verifica se o conteudo do array recebido tem algum elemento válido, não nulo
boolean Flag = false;
for(int i = 0; i < Array.size(); i++){
if(Array.get(i) != null){
Flag = true; // Existe elemento válido
break;
}
}

// Se existe elemento válido, seta o array auxiliar com o array recebido pelo método BuscaFilhos
if(Flag)
ArrayAux = Array;
else{ // Se não existe elemento válido, remove esse último array do array de níveis
ArrayNiveis.remove(ArrayNiveis.indexOf(Array));
break;
}
}

// Retorna o array de níveis para a impressão
return ArrayNiveis;
}

// Método Auxiliar do Método BuscaPai
// Método cria um array de filhos de acordo com o array passado
private ArrayList<object> BuscaFilhos(ArrayList<object> Array){

// Cria um novo array de filhos
ArrayList<object> ArrayNovo = new ArrayList<object>();

// Percorre o array passado, adicionando no novo array o filho da esquerda e da direita
for(int i = 0; i < Array.size(); i++){
// Recupera o elemento do array
Elemento ElementoAux = (Elemento)Array.get(i);

// Verifica se elemento é diferente de nulo
if(ElementoAux != null){ // Se sim, adiciona o elemento esquerdo e direito no novo array
ArrayNovo.add(ElementoAux.getElementoEsquerdo());
ArrayNovo.add(ElementoAux.getElementoDireito());
} else { // Se não, adiciona dois valores nulos no novo array, indicando que não tem filhos
ArrayNovo.add(null);
ArrayNovo.add(null);
}
}

// Retorna o novo array de filhos para a função BuscaPai
return ArrayNovo;
}

// Método para imprimir a árvore
public void Imprimir(){

// Chama a função BuscaPai que retornará o array de níveis da arvore
ArrayList<object> Array = BuscaPai();

// Verifica o tamanho do array da ultima posição do array de níveis
ArrayList<object> ArraySize = (ArrayList<object>) Array.get(Array.size() - 1);

// Cria uma variavel de tamanho
int Tamanho = ArraySize.size();

// Percorre o array de níveis
for(int i = 0; i < Array.size(); i++){

// Recupera o array da posição atual do array de niveis
ArrayList<object> Array2 = (ArrayList<object>) Array.get(i);

// Divide o tamanho pela metade, que é o número de espaços que serão utilizados para o nivel atual
Tamanho = Tamanho/2;

if(i == Array.size() - 1)
System.out.printf(" ");

for(int j = 0; j < Array2.size(); j++){

int Espacos; // Variavel que conterá quantos "\t" serão necessários para desenhar o nível atual

if(j == 0) // Se for o primeiro índice do FOR, recebe o próprio tamanho
Espacos = Tamanho;
else // Se não, recebe o tamanho * 2
Espacos = Tamanho * 2;

// Percorre o número de espaços tabulando a impressão
for(int k = 1; k <= Espacos; k++)
System.out.printf("\t");

// Verifica se é o último nível que está sendo impresso na tela
if((i == Array.size() - 1) && (j != 0))
System.out.printf("\t "); // Se sim, insere alguns espaços depois da tabulação

// Recupera o elemento para recuperar o valor
Elemento NovoElemento = (Elemento)Array2.get(j);

// Se elemento diferente de nulo...
if(NovoElemento != null)
System.out.printf("%d", NovoElemento.getValor()); // Imprime o valor do elemento
else
System.out.printf("-"); // Imprime um traço
}
System.out.printf("\n"); // Pula de linha a cada nível
}

}

}

Elemento:

public class Elemento {

// Atributos
private int Valor;
private Elemento ElementoDireito;
private Elemento ElementoEsquerdo;

// Contrutor recebe um valor como parâmetro
public Elemento(int Valor){
this.Valor = Valor;
this.ElementoDireito = null;
this.ElementoEsquerdo = null;
}

// Métodos SET
public void setValor(int Valor){
this.Valor = Valor;
}

public void setElementoEsquerdo(Elemento ElementoEsquerdo){
this.ElementoEsquerdo = ElementoEsquerdo;
}

public void setElementoDireito(Elemento ElementoDireito){
this.ElementoDireito = ElementoDireito;
}

// Métodos GET
public int getValor(){
return this.Valor;
}

public Elemento getElementoEsquerdo(){
return this.ElementoEsquerdo;
}

public Elemento getElementoDireito(){
return this.ElementoDireito;
}

// Método para verificar se nodo é interno
public boolean Interno(){
if((ElementoEsquerdo != null) || (ElementoDireito != null))
return true;
return false;
}

}

Main:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

public static void main(String Args[]){

int Opcao;

Scanner input = new Scanner(System.in);

// Cria um novo elemento que será o elemento Raiz
Elemento elemento = new Elemento(25);

// Cria a nova árvore, enviando o elemento Raiz
Arvore arvore = new Arvore(elemento);

// Insere os elementos na árvore
arvore.InserirElemento(15);
arvore.InserirElemento(20);
arvore.InserirElemento(10);
arvore.InserirElemento(13);
arvore.InserirElemento(30);
arvore.InserirElemento(28);
arvore.InserirElemento(35);
arvore.InserirElemento(14);

Opcao = 1;

while((Opcao >= 0) && (Opcao <= 7)){
Menu();
Opcao = input.nextInt();

if((Opcao >= 0) && (Opcao <= 7)){
int Valor;
switch(Opcao){
case 1 : ;
System.out.printf("\nDigite o valor do elemento a ser inserido: ");
Valor = input.nextInt();
arvore.InserirElemento(Valor);
break;
case 2 : System.out.printf("\nDigite o valor do elemento a ser removido: ");
Valor = input.nextInt();
arvore.Remover(arvore.getRaiz(), Valor);
break;
case 3 : System.out.printf("\nAltura da árvore: %d", arvore.Altura());
break;
case 4 : System.out.printf("\nPreOrder: ");
arvore.PreOrder(arvore.getRaiz());
break;
case 5 : System.out.printf("\nPostOrder: ");
arvore.PostOrder(arvore.getRaiz());
break;
case 6 : System.out.printf("\nInOrder: ");
arvore.InOrder(arvore.getRaiz());
break;
case 7 : arvore.Imprimir();
break;
}

}

}

}

private static void Menu(){
System.out.printf("\n");
System.out.printf("\n");
System.out.printf("0 - Sair\n");
System.out.printf("1 - Inserir Elemento\n");
System.out.printf("2 - Remover Elemento\n");
System.out.printf("3 - Verificar Altura\n");
System.out.printf("4 - Caminhamento PreOrder\n");
System.out.printf("5 - Caminhamento PostOrder\n");
System.out.printf("6 - Caminhamento InOrder\n");
System.out.printf("7 - Imprimir Árvore\n");
System.out.printf("Digite Sua Opção: ");
}

}