Árvores Binárias em Java

Prévia do material em texto

ESTRUTURA DE 
DADOS EM JAVA 
OBJETIVOS DE APRENDIZAGEM
 > Definir árvore binária, suas propriedades e como percorrê-la.
 > Reconhecer as operações básicas de árvores binárias.
 > Exemplificar a utilização de árvores binárias em Java.
Introdução
Árvores estão entre as estruturas de dados mais importantes da ciência da com-
putação, pois são fáceis de implementar e possuem um grande poder expressivo: 
são ideais para representar relações de hierarquia, subordinação, composição, 
organização e ordenação entre objetos. Além disso, árvores são estruturas de 
dados mais eficientes do que listas, principalmente quando comparamos as 
operações de inserção e consulta aos dados.
Neste capítulo, apresentaremos as árvores binárias. Inicialmente, conhecere-
mos a terminologia básica desse tipo de estrutura de dados e suas propriedades 
principais. Na sequência, estudaremos alguns algoritmos de manipulação desse 
tipo de árvore e entenderemos seu funcionamento. Finalmente, implementare-
mos esse tipo abstrato de dados na linguagem Java, utilizando o paradigma de 
programação orientada a objetos.
Árvores binárias 
em Java
Lucas Rafael Costella Pessutto
Árvores binárias
Árvores são estruturas de dados não lineares, o que signifi ca que cada nodo de 
uma árvore possui apontadores para dois (ou mais) nodos. Diferentemente de 
listas, que são estruturas lineares, não há a noção de antes e depois entre os 
elementos de uma árvore, mas uma relação hierárquica entre seus nodos, que 
se encontram em diferentes níveis nessa hierarquia (GOODRICH; TAMASSIA, 2013). 
Um exemplo clássico de árvore é a organização dos diretórios e arquivos 
em um sistema operacional, como mostrado na Figura 1. A origem do sistema 
de arquivos é o diretório-raiz e, a partir dele, ramificam-se todos os demais 
diretórios; ou seja, a partir da raiz, podemos alcançar qualquer arquivo pre-
sente nesse sistema operacional apenas descendo na hierarquia de diretórios. 
Figura 1. Árvore de arquivos de um sistema operacional.
Fonte: Tanenbaum e Woodhull (2008, p. 455).
Há diversos outros exemplos de árvores em nosso cotidiano, como uma 
árvore genealógica, um organograma de uma empresa e a organização de um 
livro, com seu título no nível hierárquico superior, seus capítulos no segundo 
nível e as seções em um nível abaixo deste, ligadas a seu respectivo capítulo.
Nomenclatura e propriedades
Árvores possuem uma nomenclatura especial, com inspiração biológica. 
Portanto, costumamos nos referir aos nodos como “raiz” e “folhas”. Também 
é comum utilizar as relações parentais para categorizar as posições relativas 
entre dois nodos da árvore: pai/mãe e fi lho, nodos irmãos, avô e neto, etc.
Árvores binárias em Java2
O primeiro nodo de uma árvore é chamado de raiz. Como mencionado 
anteriormente, todo nodo de uma árvore aponta para dois ou mais nodos, 
chamados de nodos filhos, e cada nodo filho tem um único pai (DEITEL; DEITEL, 
2017). Discutiremos, neste capítulo, somente as árvores binárias, que são 
aquelas cujo cada nodo possui no máximo dois filhos, um à esquerda e outro 
à direita. A Figura 2 contém um exemplo de árvore binária. Sua raiz é o nodo 
G e seus filhos são os nodos D (à esquerda) e J (à direita). Como os nodos D 
e J estão no mesmo nível da árvore, dizemos que esses nodos são irmãos. 
Outra forma de se referir a esses nodos é como raízes das subárvores (direita 
e esquerda) de G. Quando um nodo não possui filho, o chamamos de folha. 
Há cinco nodos folha na árvore da Figura 2: A, C, F, I e K.
Figura 2. Exemplo de árvore binária.
A altura de uma árvore consiste na quantidade de níveis em que a árvore 
foi construída. A altura da árvore da Figura 2 é quatro, pois ela contém quatro 
níveis: o primeiro, com a raiz (G), o segundo, com os filhos da raiz (D e J), o 
terceiro, com os nodos B, E, I e K, e, por fim, o quarto nível, com os nodos A, 
C e F. O grau de um nodo é a quantidade de filhos que possui. Por exemplo, 
o nodo G tem grau dois, o nodo E tem grau um e o nodo A tem grau zero. Por 
ser uma árvore binária, não há qualquer nodo com grau maior do que dois 
(FERRARI et al., 2014).
Como árvores são estruturas não lineares, diversos caminhos podem 
ser percorridos a partir da raiz. Feofiloff (2008) define um caminho em uma 
árvore como uma sequência de nodos (a0, a1, ..., an), onde an+1 é filho de an 
e n é o tamanho do caminho. Um possível caminho da árvore da Figura 2 é 
(G, D, E, F). Esse caminho tem tamanho quatro. Um caminho em uma árvore 
Árvores binárias em Java 3
que percorre todos seus nodos uma única vez é chamado de caminhamento. 
Existem três tipos de caminhamentos: prefixado, pós-fixado e em ordem. O 
que difere em cada um desses caminhamentos é a forma como percorrem os 
nodos da árvore (EDELWEISS; GALANTE, 2008). Vejamos, a seguir, como cada 
um desses caminhos funciona. 
 � Caminhamento prefixado: nesse caminhamento, é visitada a raiz da 
árvore, depois a subárvore da esquerda e, em seguida, a subárvore da 
direita. Considerando a árvore da Figura 2, o caminhamento prefixado 
visitaria os nodos na seguinte ordem: G–D–B–A–C–E–F–J–I–K.
 � Caminhamento pós-fixado: a ordem de visita dos nodos no caminha-
mento pós-fixado consiste em visitar inicialmente a subárvore da 
esquerda, depois a subárvore da direita e, por fim, a raiz. Na árvore da 
Figura 2, o caminhamento pós-fixado produziria a seguinte sequência 
de nodos: A–C–B–F–E–D–I–K–J–G.
 � Caminhamento em ordem: o caminhamento em ordem visita, inicial-
mente, a subárvore da esquerda, depois visita a raiz e, finalmente, 
visita a subárvore da direita. No exemplo da Figura 2, o caminhamento 
em ordem naquela árvore seria: A–B–C–D–E–F–G–I–J–K.
Note que a definição de caminhamentos é recursiva. Portanto, quando 
visitamos uma de suas subárvores, esta é tratada como uma árvore 
também. Por exemplo, na árvore da Figura 2, ao visitar a subárvore esquerda da raiz 
G, obtemos uma árvore com raiz em D e, da mesma forma, ao visitar a subárvore 
esquerda do nodo D, obtemos uma nova árvore com raiz em B. Como veremos 
mais adiante neste capítulo, a maioria dos algoritmos que operam sobre árvores 
é escrita de maneira recursiva: acostume-se a enxergar árvores dessa forma.
Operações sobre uma árvore binária
Nesta seção, vamos ver como as operações básicas de uma estrutura de dados, 
a inserção e a remoção de elementos, podem ser implementadas em uma 
árvore binária. Consideraremos que as árvores tratadas são ordenadas, isto é, 
que existe uma relação de ordem para suas subárvores (EDELWEISS; GALANTE, 
2008). Ainda, utilizaremos um tipo de árvore binária chamado de árvore binária 
de busca para definir tais operações. Além de ser bastante utilizado, esse tipo 
de árvore possui uma regra de ordenação simples: todo nodo deve possuir 
Árvores binárias em Java4
uma chave de pesquisa, que permite comparar os nós da árvore. Ao inserir um 
valor na árvore, o nodo é comparado com a raiz e é inserido na subárvore da 
esquerda, se for menor do que a raiz. Caso sua chave possua um valor maior 
do que o da raiz, nodo é inserido na subárvore da direita (FEOFILOFF, 2008).
A árvore mostrada na Figura 2 é considerada um exemplo de árvore binária 
de busca, considerando a ordem lexicográfica para comparar as letras que 
foram inseridas. Veja como os nodos da subárvore da esquerda do nodo G 
somente possuem elementos menores do que G e como o oposto ocorre na 
subárvore da direita. Dado esse critério de ordenação, realizar pesquisas na 
árvore torna-se bastante eficiente. Por exemplo, imagine que queremos en-
contrar o nodo E na árvore da Figura 2. Começando na raiz da árvore, sabemos 
que esse nodo, se estiver na árvore, estará na subárvore da esquerda, pois 
E < G. Prosseguindo a busca nessa subárvore, comparamos E com D. Nesse 
caso, concluímos que E deve estar na subárvore da direita de D, pois E > D, 
que é onde vamos encontrar o nodo contendo o valor E.
Vamos, agora, definir como um nodo de uma árvore binária deve ser cons-
truído. Por ser uma árvore binária, devemosincluir dois apontadores, um para 
a subárvore da esquerda e outro para a subárvore da direita, de modo a criar 
o encadeamento entre os nodos, conforme mostra a Figura 3. Além disso, cada 
nodo conterá uma seção para armazenar dados. Destacamos, aqui, o campo 
chave do nodo, que é obrigatório para árvores binárias de busca. Outros campos 
de dados podem ser adicionados, de acordo com a necessidade.
Figura 3. Nodo de uma árvore binária.
Inserção de nodos em uma árvore binária
Para inserir um novo nodo em uma árvore binária, precisamos, inicialmente, 
testar se a raiz da árvore está vazia. Se estiver, alocamos o novo nodo como 
a raiz da árvore. Caso a raiz exista, comparamos sua chave com o valor da 
chave do novo nodo. Se a chave do novo nodo for menor do que a raiz e ela 
ainda não possuir um fi lho na subárvore da esquerda, encadeamos o novo 
Árvores binárias em Java 5
nodo na subárvore da esquerda. Se o valor da chave do novo nodo for maior 
do que o da raiz e se a raiz ainda não possuir um filho na subárvore da direita, 
então o novo nodo será encadeado nessa subárvore.
Caso exista um filho na subárvore em que será feita a inserção, o filho se 
torna a raiz da árvore e repete-se, recursivamente, o processo de decidir se 
a inserção acontecerá na subárvore da direita ou da esquerda, até encontrar 
um local onde deva ser inserido o novo nodo. Veja, abaixo, um algoritmo 
recursivo que insere um novo nodo na árvore binária:
função insere(Nodo raiz, int valor){
 se (raiz == NULL){
 Nodo novo = Nodo(valor)
 raiz = novo;
 } senao se (raiz.chave > valor){
 se (raiz.filhoEsquerdo == NULL){
 Nodo novo = Nodo(valor)
 raiz.filhoEsquerdo = novo
 } senao {
 insere(raiz.filhoEsquerdo, valor)
 }
 } senao se (raiz.chave < valor){
 se (raiz.filhoDireito == NULL){
 Nodo novo = Nodo(valor)
 raiz.filhoDireito = novo
 } senao {
 insere(raiz.filhoDireito, valor)
 }
 }
}
Árvores binárias em Java6
Para exemplificar, considere uma árvore que está inicialmente vazia. 
Agora, vamos realizar a inserção do nodo com chave 5 nessa árvore. 
Como ela está vazia, esse nodo será a raiz. Na sequência, se formos 
inserir o nodo 3, este será alocado à esquerda do nodo 5, pois é menor. 
Inserindo o valor 2 na árvore, necessita-se comparar 2 com 5. Como 
2 é menor, ele será inserido na subárvore da esquerda, mas, como já 
existe um nodo nessa subárvore, agora comparamos o nodo 2 com o 
nodo 3. Como 2 também é menor, inserimos esse nodo na subárvore da 
esquerda do nodo 3. Seguindo essa regra, podemos inserir o nodo 4 à 
direita do nodo 3, o nodo 8 à direita do nodo 5, o nodo 6 à esquerda 
do nodo 8 e, por fim, o nodo 7 à direita do nodo 6. A árvore resultante 
dessas inserções pode ser vista na Figura 4.
Figura 4. Árvore binária resultante da inserção dos nodos 5–3–2–4–8–6–7, nessa ordem.
Há duas coisas que são interessantes de se observar na inserção de nodos 
em uma árvore binária. A primeira delas é que os novos nodos são sempre 
inseridos nas folhas da árvore. Logo, chamamos o método inserir recursi-
vamente até encontrar um nodo que não tenha filhos para fazer a inserção. 
Também é interessante destacar que a ordem de inserção dos nodos em 
uma árvore influencia sua aparência. Por exemplo, se repetirmos o exemplo 
anterior, mas inserindo os nodos na ordem contrária na árvore, esta teria 
uma aparência diferente. Veja, na Figura 5, como ficaria essa árvore.
Árvores binárias em Java 7
Figura 5. Árvore binária resultante da inserção dos nodos 7–6–8–4–2–3–5, nessa ordem. 
Perceba como a mudança na ordem de inserção modifica a aparência da árvore.
Remoção de nodos em uma árvore binária
A remoção de um nodo da árvore binária é mais complexa do que a inserção, 
pois devemos garantir que, após a remoção, a árvore se manterá ordenada, 
e por isso temos uma quantidade maior de casos que precisam ser conside-
rados. O primeiro passo é buscar, na árvore, o valor que se deseja remover. 
Após, analisamos em qual dos casos a seguir ele se encaixa e realizamos a 
deleção do nodo. O caso mais simples de remoção é quando há um único 
nodo na árvore, bastando somente setar a raiz da árvore com o valor nulo. 
Quando a árvore possui um nodo filho, três situações distintas podem 
ocorrer no momento da remoção, de acordo com o grau do nodo que será 
removido. Vejamos.
 � Remoção de nodo de grau zero: remover um nodo folha (grau zero) é 
simples; basta encontrar seu pai e setar sua referência no nodo pai 
para nulo.
 � Remoção de nodo de grau um: quando o nodo que será removido 
possui uma subárvore, seu filho passa a ocupar seu local na árvore; 
ou seja, encadeamos o nodo avô com seu neto, removendo o nodo 
intermediário.
 � Remoção de nodo de grau dois: quando ambas as subárvores do nodo 
que será removido estão ocupadas, existem dois nodos que podem 
Árvores binárias em Java8
ser escolhidos para substituir o nodo que será removido, (1) o maior 
valor da subárvore da esquerda e (2) o menor valor da subárvore da 
direita. Escolher um desses dois nodos garantirá que a árvore conti-
nue ordenada. Por convenção, neste capítulo, adotaremos a primeira 
opção. Para encontrar o maior valor da subárvore da esquerda, basta 
encontrar o valor que está mais à direita nessa subárvore.
Veja, abaixo, o algoritmo que realiza a exclusão de um nodo em uma ár-
vore. Foram definidas algumas funções auxiliares, como a função pesquisa, 
que pesquisa se um valor está ou não na árvore, retornando seu nodo (ela 
retorna NULL se o nodo não estiver na árvore). Também definimos a função 
busca _ pai, que retorna o pai do nodo que contém determinado valor. Por 
fim, a função max é utilizada para buscar o valor máximo da subárvore da 
esquerda quando ocorre uma remoção de nodo com dois filhos.
função remove(Nodo raiz, int valor){
 Nodo del = pesquisa(raiz, valor)
 se (del == NULL){
 escreva(“O valor procurado não está na árvore.”)
 } senao se (del.filhoEsquerdo == NULL e del.filhoDi-
reito == NULL){
 // Remoção de um nodo folha
 Nodo pai = busca _ pai(valor)
 se (pai.FilhoEsquerdo.chave == valor) 
 pai.filhoEsquerdo = NULL
 senao
 pai.filhoDireito = NULL
 } senao se (del.FilhoEsquerdo != NULL e del.filhoDi-
reito != NULL){
 // Remoção de Nodo de grau 2
 Nodo pai = busca _ pai(valor)
Árvores binárias em Java 9
 Nodo maior = max(del.filhoEsquerdo)
 Nodo pai _ maior = busca _ pai(maior.chave)
 // Transfere os dados do maior para o del
 del.chave = maior.chave
 // Apaga o nodo maior
 se (maior.filhoEsquerdo == NULL e maior.filhoDireito 
== NULL){
 se (pai _ maior.FilhoEsquerdo.chave == maior){
 pai _ maior.FilhoEsquerdo = NULL
 } senao {
 Pai _ maior.FilhoDireito = NULL
 }
 } senao {
 // Maior possui um filho a esquerda
 se (pai _ maior.FilhoEsquerdo.chave == maior){
 pai _ maior.FilhoEsquerdo = maior.
FilhoEsquerdo
 } senao {
 Pai _ maior.FilhoDireito = maior.FilhoEsquerdo
 }
 }
 } senao {
 // Remoção de nodo de grau 1
Árvores binárias em Java10
 Nodo pai = busca _ pai(valor)
 se (pai.FilhoEsquerdo.chave == valor) {
 se (del.filhoEsquerdo != NULL) 
 pai.filhoEsquerdo = del.filhoEsquerdo
 senao
 pai.filhoEsquerdo = del.filhoDireito
 } senao {
 se (del.filhoEsquerdo != NULL) 
 pai.filhoDireito = del.filhoEsquerdo
 senao
 pai.filhoDireito = del.filhoDireito 
 }
 } 
}
Vamos exemplificar cada caso de remoção com um exemplo prático. 
Considere a árvore obtida na Figura 4. Vamos remover os nodos 7, 8 e 3 da 
árvore, nessa ordem. O nodo 7 possui grau zero; logo, para que seja removido 
da árvore, basta apagar a referência de seu pai (nodo 6) para ele, resultando 
na árvore da Figura 6a. A remoção do nodo 8 se encaixa no segundo caso, 
visto que esse nodo possui uma subárvore. Nesse caso, devemos modificar 
a referência de seu pai (nodo 5) para o nodo 6, que é o filhodo nodo 8. Esse 
processo resultará na árvore da Figura 6b. Por fim, removendo o nodo 3, que 
possui dois filhos, demanda a escolha do maior nodo da subárvore da esquerda 
para substituí-lo. Como, nesse exemplo, só existe o nodo 2 na subárvore, ele 
substituirá o nodo 3, produzindo a árvore da Figura 6c.
Árvores binárias em Java 11
Figura 6. Remoção de nodos 7 (a), 8 (b) e 3 (c) de uma árvore binária.
Implementando uma árvore binária em Java
Após estudarmos a terminologia básica e conhecer os principais métodos 
presentes em uma árvore binária, podemos implementar essa estrutura de 
dados na linguagem de programação Java, utilizando orientação a objetos. 
Aqui, vamos criar uma árvore que armazena somente um número inteiro, que 
também será a chave de busca na árvore. Iniciaremos definindo uma classe 
que representa um nodo da árvore, chamada de NodoArvore, conforme 
mostrado na Figura 3.
public class NodoArvore { 
 private NodoArvore filhoEsquerda; 
 private int chave; 
 private NodoArvore filhoDireita; 
 
 public NodoArvore(int valor){ 
Árvores binárias em Java12
 this.setChave(valor); 
 this.setFilhoEsquerda(null); 
 this.setFilhoDireita(null); 
 }
}
Considere que essa classe também contém os getters e setters correspon-
dentes aos três campos presentes na classe. Ao criar um nodo na árvore, é 
necessário informar o valor inteiro que será armazenado naquele nodo. Por 
padrão, os filhos esquerdo e direito daquele nodo são nulos. Vamos definir, 
agora, uma interface que contém os métodos públicos que devem estar 
presentes na estrutura de dados árvore:
public interface Arvore { 
 public NodoArvore pesquisa (int valor);
 public void inserir (int valor); 
 public void remover (int valor); 
 public void imprime _ preFixado(); 
}
Essa interface possui quatro métodos: um método de consulta à árvore, 
chamado de pesquisa, os métodos de inserção e remoção, e, por fim, um mé-
todo que imprime os valores presentes na árvore utilizando o caminhamento 
prefixado. Vamos, agora, definir a classe ArvoreBinaria, que implementa 
a interface Arvore definida anteriormente e contém uma instância de No-
doArvore, que será a raiz da árvore. Esse objeto é inicializado com o valor 
NULL no construtor da classe.
public class ArvoreBinaria implements Arvore { 
 private NodoArvore raiz; 
 
 public ArvoreBinaria(){ 
 this.raiz = null; 
 }
 
 // Os métodos da interface Arvore deverão ser inseri-
dos aqui.
}
Árvores binárias em Java 13
Vejamos, agora, a implementação de cada um dos métodos da interface 
Arvore, bem como de alguns métodos auxiliares que permanecerão com a 
visibilidade privada dentro da classe ArvoreBinaria para que não sejam 
utilizados fora dessa classe.
Método pesquisa na árvore binária
O método de busca recebe, como parâmetro, o valor que se quer encontrar 
na árvore. Ele utiliza um método auxiliar recursivo para percorrer a árvore 
e buscar o valor informado. O método pesquisaRecursivo compara o 
valor buscado com o valor da chave da raiz. Se eles forem iguais, o método 
retorna aquele nodo; caso contrário, é checado se o valor informado como 
parâmetro é maior ou menor do que a chave do nodo atual. Caso seja 
menor, sabemos que o valor buscado só poderá estar na subárvore da 
esquerda e, se for maior, na subárvore da direita. Conforme o resultado do 
método, é feita uma chamada recursiva, tendo como parâmetro a subárvore 
correspondente ao resultado do teste. Veja, abaixo, a implementação dos 
métodos descritos.
public NodoArvore pesquisa(int valor){ 
 NodoArvore nodoResultado = pesquisaRecursivo(raiz, 
valor); 
 return nodoResultado; 
} 
 
private NodoArvore pesquisaRecursivo(NodoArvore raiz, int 
valor) { 
 if(raiz != null) { 
 if(valor == raiz.getChave()){ 
 return raiz; 
 } else if (valor < raiz.getChave()) { 
 return pesquisaRecursivo(raiz.getFilhoEs-
querda(), valor); 
 } else { 
 return pesquisaRecursivo(raiz.getFilhoDi-
reita(), valor); 
 } 
 } 
 return null; 
}
Árvores binárias em Java14
Método de impressão da árvore
A impressão da árvore é feita por meio de um caminhamento prefixado. 
O método imprime _ preFixado faz uma chamada ao método recursivo 
preFixado, informando, como parâmetro, a raiz da árvore. Esse método, 
por sua vez, realiza o caminhamento pela árvore. Se o nodo atual é nulo, 
nada é feito; caso contrário, ele imprime o valor presente na raiz e faz duas 
chamadas recursivas, primeiramente para a subárvore da esquerda e, depois, 
para a subárvore da direita.
public void imprime _ preFixado(){ 
 preFixado(this.raiz); 
} 
 
private void preFixado(NodoArvore raiz){ 
 if( raiz == null ) 
 return; 
 
 System.out.print(raiz.getChave() + " "); 
 preFixado(raiz.getFilhoEsquerda()); 
 preFixado(raiz.getFilhoDireita()); 
}
Inserção de nodos na árvore
Agora vamos analisar o método de inserção em uma árvore binária. O método 
inserir recebe um número inteiro como parâmetro e o insere na árvore. O 
primeiro teste que é feito é se a árvore está vazia. Se for o caso, então esse 
valor passa a ser a nova raiz da árvore. Se já houver uma raiz, é invocado o 
método recursivo insere, que vai procurar o local onde o novo nodo deve 
ser inserido a partir da raiz, de acordo com o critério de ordenação da árvore. 
Se o valor for menor do que a raiz, ele deve ser inserido ao lado esquerdo 
da árvore; caso seja maior, ele será inserido no lado direito. Após decidir em 
qual das subárvores o nodo deverá ser inserido, é necessário verificar se já 
existe algum nodo alocado naquela subárvore. Caso não exista, criamos um 
nodo e o inserimos naquela subárvore. Se existir um nodo, fazemos uma 
chamada recursiva à função insere, considerando o nodo da subárvore 
correspondente como raiz.
Árvores binárias em Java 15
public void inserir (int valor){ 
 if (raiz == null){ 
 raiz = new NodoArvore(valor); 
 } else { 
 insere(raiz, valor); 
 } 
}
private void insere (NodoArvore raiz, int valor){ 
 if (valor < raiz.getChave()){ 
 if (raiz.getFilhoEsquerda() == null){ 
 NodoArvore novoNodo = new NodoArvore(valor); 
 raiz.setFilhoEsquerda(novoNodo); 
 } else { 
 insere(raiz.getFilhoEsquerda(), valor); 
 } 
 } else if (valor > raiz.getChave()){ 
 if (raiz.getFilhoDireita() == null){ 
 NodoArvore novoNodo = new NodoArvore(valor); 
 raiz.setFilhoDireita(novoNodo); 
 } else { 
 insere(raiz.getFilhoDireita(), valor); 
 } 
 } 
}
Remoção de nodo da árvore
Por fim, vejamos como implementar a remoção de nodos de uma árvore. 
Como comentado na seção anterior, o método de remoção tem alguns casos 
especiais que precisam ser tratados. Estudaremos o código de cada um deles 
agora. Iniciaremos com o método remover, que decide qual dos casos deve 
ser tratado. Primeiramente, utilizaremos o método pesquisa para verificar 
se o valor informado como parâmetro da função realmente se encontra na 
árvore. Se ele não estiver na árvore, apenas informamos ao usuário, escre-
vendo uma mensagem na tela. Se o valor for encontrado na árvore, verificamos 
quantos filhos ele possui e chamamos o método adequado: removeFolha, 
removeUmFilho ou removeDoisFilhos.
Árvores binárias em Java16
public void remover (int valor){ 
 NodoArvore nodo = pesquisa(valor); 
 if (nodo == null){ 
 System.out.println("O valor "+ valor +" não está 
na árvore."); 
 } else if (nodo.getFilhoEsquerda() == null && 
 nodo.getFilhoDireita() == null){ 
 removeFolha(nodo); 
 } else if (nodo.getFilhoEsquerda() != null && 
 nodo.getFilhoDireita() != null){ 
 removeDoisFilhos(nodo); 
 } else { 
 removeUmFilho(nodo); 
 } 
}
Vejamos, agora, como se dá a remoção do nodoem cada um dos três casos. 
Antes disso, vamos definir um método auxiliar chamado de buscaPai, que 
encontra o pai do nodo que deve ser removido. Esse método tem funciona-
mento parecido com o método pesquisa; porém, no lugar de verificar se a 
raiz corresponde ao valor atual, ele checa se algum dos filhos possui o valor 
buscado. Esse método retorna null caso o nodo buscado não possua pai e, 
nesse caso, saberemos que se trata do nodo-raiz.
private NodoArvore buscaPai(NodoArvore raiz, int valor) { 
 if (raiz != null){ 
 if (valor < raiz.getChave()){ 
 if (raiz.getFilhoEsquerda() != null && 
 raiz.getFilhoEsquerda().ge-
tChave() == valor){ 
 return raiz; 
 } else { 
 return buscaPai(raiz.getFilhoEsquerda(), 
valor); 
 } 
 } else if (valor > raiz.getChave()){ 
 if (raiz.getFilhoDireita() != null && 
 raiz.getFilhoDireita().getChave() == valor){ 
 return raiz; 
 } else { 
Árvores binárias em Java 17
 return buscaPai(raiz.getFilhoDireita(), valor); 
 } 
 } 
 } 
 return null; 
}
O método que remove um nodo folha é descrito abaixo. Usamos o método 
buscaPai para localizar o pai do nodo que será removido e, em seguida, 
fazemos um teste para decidir se o nodo a ser removido está à esquerda 
ou à direita de seu pai. Por fim, apagamos sua referência, setando o valor 
daquela subárvore para null.
private void removeFolha(NodoArvore nodo){ 
 NodoArvore pai = buscaPai(this.raiz, nodo.getChave()); 
 if (pai == null){ 
 this.raiz = null; 
 } else if (pai.getFilhoEsquerda() != null && 
 pai.getFilhoEsquerda() == nodo){ 
 pai.setFilhoEsquerda(null); 
 } else { 
 pai.setFilhoDireita(null); 
 } 
}
Observe a comparação que fizemos na função removeFolha: pai.
getFilhoEsquerda() == nodo. Nesse tipo de comparação, 
não estamos comparando os valores das chaves dos dois nodos, mas suas 
referências. Isso quer dizer que essa expressão retornará o valor true se pai.
getFilhoEsquerda() e nodo forem o mesmo objeto. Caso sejam objetos 
diferentes, essa comparação retornará o valor false. 
Veja, agora, como fica a implementação do método que remove um nodo 
que possua um filho. Primeiramente, buscamos o pai do nodo que será remo-
vido e, após isso, verificamos se estamos removendo a raiz da árvore. Se for 
verdadeiro, o filho passa a ser a nova raiz; caso contrário, encadeamos o nodo 
avô com seu neto, removendo o nodo informado como parâmetro da árvore.
private void removeUmFilho(NodoArvore nodo){ 
 NodoArvore pai = buscaPai(this.raiz, nodo.getChave()); 
 if (pai == null){ 
Árvores binárias em Java18
 if (nodo.getFilhoEsquerda() != null){ 
 this.raiz = nodo.getFilhoEsquerda(); 
 } else { 
 this.raiz = nodo.getFilhoDireita(); 
 } 
 } else if (nodo.getFilhoEsquerda() != null) { 
 if (pai.getFilhoEsquerda() == nodo){ 
 pai.setFilhoEsquerda(nodo.getFilhoEsquerda()); 
 } else { 
 pai.setFilhoDireita(nodo.getFilhoEsquerda()); 
 } 
 } else if (nodo.getFilhoDireita() != null){ 
 if (pai.getFilhoEsquerda() == nodo){ 
 pai.setFilhoEsquerda(nodo.getFilhoDireita()); 
 } else { 
 pai.setFilhoDireita(nodo.getFilhoDireita()); 
 } 
 } 
}
O método que exclui um nodo que possui dois filhos necessita de 
um método auxiliar max, que retorna o maior valor de uma árvore. Esse 
método será utilizado para encontrar o nodo que deverá substituir o 
nodo que será removido, conforme explicado na seção anterior. Seu 
funcionamento é bastante simples: ele percorre a subárvore da direita 
até encontrar um nodo que não possua um filho. Esse nodo contém o 
maior valor naquela árvore.
private NodoArvore max(NodoArvore raiz){ 
 if (raiz.getFilhoDireita() == null){ 
 return raiz; 
 } else { 
 return max(raiz.getFilhoDireita()); 
 } 
}
Finalmente, vejamos o código correspondente ao método removeDois-
Filhos. A princípio, esse método procura o pai do nodo a ser removido 
e o maior nodo de sua subárvore esquerda, que ocupará seu lugar. Além 
disso, buscamos o pai do maior nodo, para corrigirmos suas referências. 
Na sequência, modificamos o valor da chave do nodo que será removido 
Árvores binárias em Java 19
(e outros dados que também estejam armazenados naquele nodo) para o 
valor da chave (e outros dados) do nodo max e deletamos o maior nodo 
da árvore. Dessa forma, não precisaremos fazer muitas alterações nos 
apontadores dos nós. 
Por fim, procedemos com a remoção do nodo max da árvore. Será neces-
sário fazer um teste para verificar se esse nodo possui algum descendente 
à esquerda (sabemos que, por ser o maior valor da árvore, ele não possui 
qualquer filho à direita). Caso ele não tenha, basta apagar sua referência 
na variável paiMax. Se ele possuir um filho, esse nodo passa a ocupar sua 
posição.
private void removeDoisFilhos(NodoArvore nodo){ 
 NodoArvore pai = buscaPai(this.raiz, nodo.getChave()); 
 NodoArvore max = max(nodo.getFilhoEsquerda()); 
 NodoArvore paiMax = buscaPai(nodo, max.getChave()); 
 nodo.setChave(max.getChave()); 
 if (max.getFilhoEsquerda() == null){ 
 if (paiMax == nodo){ 
 paiMax.setFilhoEsquerda(null); 
 } else { 
 paiMax.setFilhoDireita(null); 
 } 
 } else { 
 paiMax.setFilhoDireita(max.getFilhoEsquerda()); 
 } 
}
Referências
DEITEL, H. M.; DEITEL, P. J. JavaTM: como programar. 10. ed. São Paulo: Pearson, 2017. 
EDELWEISS, N.; GALANTE, R. Estruturas de dados. Porto Alegre: Bookman, 2008. 18 v. 
(Série Livros Didáticos informática UFRGS).
FEOFILOFF, P. Algoritmos em linguagem C. Rio de Janeiro: Elsevier, 2008. 
FERRARI, R. et al. Estruturas de dados com jogos. Rio de Janeiro: Elsevier, 2014. 
GOODRICH, M. T.; TAMASSIA, R. Estrutura de dados e algoritmos com Java. 5. ed. Porto 
Alegre: Bookman, 2013.
TANENBAUM, A. S.; WOODHULL, A. S. Sistemas operacionais: projeto e implementação. 
Porto Alegre: Bookman, 2008. 
Árvores binárias em Java20
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Árvores binárias em Java 21