Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Binary Tree Java - Arvore Binaria em Java com metodos inserir e remover comentados detalhadamente
/* Arvore Binaria em Java (insere, apaga, busca, caminha)
Criado por: profa. Divani Barbosa Gavinier
Curriculo Lattes: http://lattes.cnpq.br/8503400830635447
divanibarbosa@gmail.com
*/
class No {
long item;
No dir;
No esq;
}
////////////////////////////////////////////////
class Tree {
private No root, atual; // raiz
boolean flag=true;
public Tree() { root=null; } // inicializa arvore
public void inserir(long v) {
No novo = new No(); // cria um novo Nó
novo.item = v; // atribui o valor recebido ao item de dados do Nó
novo.dir = null;
novo.esq = null;
if (root == null) root = novo;
else { // se nao for a raiz
No atual = root;
No parente;
while(true) {
parente = atual;
if (v <= atual.item) { // ir para esquerda
atual = atual.esq;
if (atual == null) {
parente.esq = novo;
return;
}
} // fim da condição ir a esquerda
else { // ir para direita
atual = atual.dir;
if (atual == null) {
parente.dir = novo;
return;
}
} // fim da condição ir a direita
} // fim do laço while
} // fim do else não raiz
}
public No buscar(long chave) {
No atual = root; // começa a procurar desde raiz
while (atual.item != chave) { // enquanto nao encontrou
if(chave < atual.item ) atual = atual.esq; // caminha para esquerda
else atual = atual.dir; // caminha para direita
if (atual == null) return null; // encontrou uma folha -> sai
} // fim laço while
return atual; // terminou o laço while e chegou aqui é pq encontrou item
}
public boolean remover(long v) {
if (root == null) return false; // se arvore vazia
No atual = root;
No pai = root;
boolean filho_esq = true;
// ****** Buscando o valor **********
while (atual.item != v) { // enquanto nao encontrou
pai = atual;
if(v < atual.item ) { // caminha para esquerda
atual = atual.esq;
filho_esq = true; // é filho a esquerda? sim
}
else { // caminha para direita
atual = atual.dir;
filho_esq = false; // é filho a esquerda? NAO
}
if (atual == null) return false; // encontrou uma folha -> sai
} // fim laço while de busca do valor
// **************************************************************
// se chegou aqui quer dizer que encontrou o valor (v)
// "atual": contem a referencia ao No a ser eliminado
// "pai": contem a referencia para o pai do No a ser eliminado
// "filho_esq": é verdadeiro se atual é filho a esquerda do pai
// **************************************************************
// Se nao possui nenhum filho (é uma folha), elimine-o
if (atual.esq == null && atual.dir == null) {
if (atual == root ) root = null; // se raiz
else if (filho_esq) pai.esq = null; // se for filho a esquerda do pai
else pai.dir = null; // se for filho a direita do pai
}
// Se é pai e nao possui um filho a direita, substitui pela subarvore a direita
else if (atual.dir == null) {
if (atual == root) root = atual.esq; // se raiz
else if (filho_esq) pai.esq = atual.esq; // se for filho a esquerda do pai
else pai.dir = atual.esq; // se for filho a direita do pai
}
// Se é pai e nao possui um filho a esquerda, substitui pela subarvore a esquerda
else if (atual.esq == null) {
if (atual == root) root = atual.dir; // se raiz
else if (filho_esq) pai.esq = atual.dir; // se for filho a esquerda do pai
else pai.dir = atual.dir; // se for filho a direita do pai
}
// Se possui mais de um filho, se for um avô ou outro grau maior de parentesco
else {
No sucessor = no_sucessor(atual);
// Usando sucessor que seria o Nó mais a esquerda da subarvore a direita do No que deseja-se remover
if (atual == root) root = sucessor; // se raiz
else if(filho_esq) pai.esq = sucessor; // se for filho a esquerda do pai
else pai.dir = sucessor; // se for filho a direita do pai
sucessor.esq = atual.esq; // acertando o ponteiro a esquerda do sucessor agora que ele assumiu
// a posição correta na arvore
}
return true;
}
// O sucessor é o Nó mais a esquerda da subarvore a direita do No que foi passado como parametro do metodo
public No no_sucessor(No apaga) { // O parametro é a referencia para o No que deseja-se apagar
No paidosucessor = apaga;
No sucessor = apaga;
No atual = apaga.dir; // vai para a subarvore a direita
while (atual != null) { // enquanto nao chegar no Nó mais a esquerda
paidosucessor = sucessor;
sucessor = atual;
atual = atual.esq; // caminha para a esquerda
}
// *********************************************************************************
// quando sair do while "sucessor" será o Nó mais a esquerda da subarvore a direita
// "paidosucessor" será o o pai de sucessor e "apaga" o Nó que deverá ser eliminado
// *********************************************************************************
if (sucessor != apaga.dir) { // se sucessor nao é o filho a direita do Nó que deverá ser eliminado
paidosucessor.esq = sucessor.dir; // pai herda os filhos do sucessor que sempre serão a direita
// lembrando que o sucessor nunca poderá ter filhos a esquerda, pois, ele sempre será o
// Nó mais a esquerda da subarvore a direita do Nó apaga.
// lembrando também que sucessor sempre será o filho a esquerda do pai
sucessor.dir = apaga.dir; // guardando o ponteiro a direita do sucessor para
// quando ele assumir a posição correta na arvore
}
return sucessor;
}
public void caminhar() {
System.out.print("\n\n Exibindo em ordem: ");
inOrder(root);
System.out.print("\n Exibindo em pos-ordem: ");
posOrder(root);
System.out.print("\n Exibindo em pre-ordem: ");
preOrder(root);
System.out.print("\n Altura da arvore: " + altura(root));
System.out.print("\n Quantidade de folhas: " + folhas(root));
System.out.print("\n Quantidade de Nós: " + contarNos(root));
if (root != null ) {
long v = min().item;
System.out.print("\n Valor minimo: " + v);
v = max().item;
System.out.print("\n Valor maximo: " + v);
}
}
public void inOrder(No atual) {
if (atual != null) {
inOrder(atual.esq);
System.out.print(atual.item + " ");
inOrder(atual.dir);
}
}
public int altura(No atual) {
if(atual == null || (atual.esq == null && atual.dir == null))
return 0;
else {
if (altura(atual.esq) > altura(atual.dir))
return ( 1 + altura(atual.esq) );
else
return ( 1 + altura(atual.dir) );
}
}
public int folhas(No atual) {
if(atual == null) return 0;
if(atual.esq == null && atual.dir == null) return 1;
return folhas(atual.esq) + folhas(atual.dir);
}
public int contarNos(No atual) {
if(atual == null) return 0;
else return ( 1 + contarNos(atual.esq) + contarNos(atual.dir));
}
public void posOrder(No atual) {
if (atual != null) {
posOrder(atual.esq);
posOrder(atual.dir);
System.out.print(atual.item + " ");
}
}
public void preOrder(No atual) {
if (atual != null) {
System.out.print(atual.item + " ");
preOrder(atual.esq);
preOrder(atual.dir);
}
}
public No min() {
No atual = root;
No anterior = null;
while (atual != null) {
anterior = atual;
atual = atual.esq;
}
return anterior;
}
public No max() {
No atual = root;
No anterior = null;
while (atual != null) {
anterior = atual;
atual = atual.dir;
}
return anterior;
}
}
////////////////////////////////////////////////
class TreeBinApp {
public static void main(String[] args) {
Tree arv = new Tree();
System.out.print("\n >>> Inserindo os valores: 50, 25, 75, 48, 71, 63, 10, 67");
arv.inserir(50);
arv.inserir(25);
arv.inserir(75);
arv.inserir(48);
arv.inserir(71);
arv.inserir(63);
arv.inserir(10);
arv.inserir(67);
arv.caminhar();
System.out.print("\n\n >>> Removendo o valor 10");
if( arv.remover(10) ) System.out.print("\n Valor removido");
else System.out.print("\n Valor NAO encontrado");
arv.caminhar();
System.out.println();
System.out.println("\n >>> Procurando o valor 71");
No encontrou = arv.buscar(71);
if( encontrou!=null ) System.out.println(" Valor encontrado");
else System.out.println(" Valor NAO encontrado");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment