As estruturas de dados são fundamentais para a organização eficiente de informações em sistemas computacionais. Entre elas, as árvores destacam-se pela sua capacidade de representar relações hierárquicas de forma intuitiva. Este artigo explora o conceito de árvores, com foco particular nas árvores binárias, suas propriedades, métodos de armazenamento e operações essenciais.
Estruturas de Árvore
Uma árvore é uma estrutura de dados não linear que organiza dados em uma hierarquia. Consiste em um conjunto de 'n' (n ≥ 0) nós interconectados, assemelhando-se a uma árvore invertida, com a raiz no topo e as folhas na base. As principais características de uma árvore incluem:
- Um nó especial, conhecido como nó raiz, que não possui antecessor.
- Todos os outros nós, exceto a raiz, são divididos em 'M' (M > 0) subconjuntos, cada um formando uma subárvore. Cada nó, exceto a raiz, possui um único nó pai e pode ter zero ou mais nós filhos.
- A definição de árvore é recursiva.
É crucial que as subárvores não possuam intersecções, caso contrário, a estrutura não é considerada uma árvore válida.
Conceitos Essenciais
- Uma árvore com N nós possui N-1 arestas.
- Subárvores não podem se sobreopr.
- Cada nó, exceto a raiz, tem exatamente um pai.
- Profundidade (ou Nível): A distância de um nó até a raiz (contando a raiz como nível 1 ou 0, dependendo da convenção).
- Grau de um Nó: O número de filhos de um nó.
Árvores Binárias
Uma árvore binária é um tipo especial de árvore em que cada nó possui no máximo dois filhos (grau ≤ 2). Estes filhos são estritamente designados como filho esquerdo e filho direito, e sua ordem é significativa.
Tipos Específicos de Árvores Binárias
- Árvore Binária Cheia (Full Binary Tree): Uma árvore binária na qual cada nó, exceto as folhas, tem exatamente dois filhos. Alternativamente, uma árvore binária onde todos os níveis estão completamente preenchidos. Para 'k' níveis, o número total de nós é 2^k - 1.
- Árvore Binária Completa (Complete Binary Tree): Uma árvore binária onde todos os níveis estão preenchidos, exceto possivelmente o último, e todos os nós do último nível estão o mais à esquerda possível. Uma árvore binária cheia é sempre uma árvore binária completa.
Propriedades das Árvores Binárias
- Em uma árvore binária não vazia, o número máximo de nós no nível 'i' (começando de i=1 para a raiz) é 2^(i-1).
- A profundidade máxima de uma árvore binária com 'k' níveis é 2^k - 1 nós (começando de k=1 para a raiz).
- Para qualquer árvore binária, se 'n0' é o número de nós folha e 'n2' é o número de nós com grau 2, então n0 = n2 + 1.
- A altura 'h' de uma árvore binária completa com 'n' nós é aproximadamente log2(n+1) (arredondado para cima).
- Em uma árvore binária completa com 'n' nós, se os nós são numerados de 0 a n-1, de cima para baixo e da esquerda para a direita:
- O pai do nó 'i' (se i > 0) é o nó em (i-1)/2.
- O filho esquerdo do nó 'i' (se 2i+1 < n) é o nó em 2i+1.
- O filho direito do nó 'i' (se 2i+2 < n) é o nó em 2i+2.
Armazenamento de Árvores Binárias
Árvores binárias podem ser armazenadas de duas maneiras principais:
- Armazenamento Sequencial: Geralmente usando um array, onde a posição dos nós é determinada por suas relações (baseado nas propriedades de nós em árvores completas). É eficiente para árvores completas.
- Armazenamento Encadeado (Linked Storage): Usando nós que contêm referências para seus filhos (e opcionalmente, para o pai). A representação mais comum é a "representação por filhos", onde cada nó tem referências para o filho esquerdo e o filho direito.
// Representação de um nó de árvore binária comum
class NoArvore {
public int valor; // O dado armazenado no nó
public NoArvore filhoEsquerdo; // Referência para o filho esquerdo
public NoArvore filhoDireito; // Referência para o filho direito
public NoArvore(int valor) {
this.valor = valor;
}
}
// Representação de um nó com referência ao pai (raramente usada para algos comuns)
class NoArvoreComPai {
public int valor;
public NoArvoreComPai filhoEsquerdo;
public NoArvoreComPai filhoDireito;
public NoArvoreComPai pai; // Referência para o nó pai
public NoArvoreComPai(int valor) {
this.valor = valor;
}
}
Para a maioria dos problemas algorítmicos, a representação apenas com referências aos filhos é suficiente.
Operações Fundamentais em Árvores Binárias
Percursos (Travessias) de Árvores Binárias
O percurso de uma árvore envolve visitar cada nó exatamente uma vez. Existem quatro métodos principais de percurso para árvores binárias:
- Percurso em Pré-ordem (Raiz-Esquerda-Direita): Visita o nó raiz, depois percorre recursivamente a subárvore esquerda, e finalmente percorre recursivamente a subárvore direita.
- Percurso em Ordem (Esquerda-Raiz-Direita): Percorre recursivamente a subárvore esquerda, visita o nó raiz, e depois percorre recursivamente a subárvore direita.
- Precurso em Pós-ordem (Esquerda-Direita-Raiz): Percorre recursivamente a subárvore esquerda, depois percorre recursivamente a subárvore direita, e finalmente visita o nó raiz.
- Percurso em Nível (Breadth-First Traversal): Visita os nós nível por nível, da esquerda para a direita. Geralmente implementado usando uma fila.
Para ilustrar os percursos, considere a seguinte árvore (sem imagens, descrita textualmente):
1
/ \
2 3
/ \ / \
4 5 6 7
- Pré-ordem: 1, 2, 4, 5, 3, 6, 7
- Em Ordem: 4, 2, 5, 1, 6, 3, 7
- Pós-ordem: 4, 5, 2, 6, 7, 3, 1
- Em Nível: 1, 2, 3, 4, 5, 6, 7
Implementação de Operações Básicas
Vamos criar uma classe ArvoreBinaria para encapsular as operações.
import java.util.*;
public class ArvoreBinaria {
// Classe interna para representar um nó da árvore
static class NoArvore {
public int valor;
public NoArvore filhoEsquerdo;
public NoArvore filhoDireito;
public NoArvore(int valor) {
this.valor = valor;
}
}
public NoArvore raiz; // O nó raiz da árvore
// Método para criar uma árvore de exemplo para testes
public NoArvore construirArvoreExemplo() {
NoArvore no1 = new NoArvore(1);
NoArvore no2 = new NoArvore(2);
NoArvore no3 = new NoArvore(3);
NoArvore no4 = new NoArvore(4);
NoArvore no5 = new NoArvore(5);
NoArvore no6 = new NoArvore(6);
NoArvore no7 = new NoArvore(7);
no1.filhoEsquerdo = no2;
no1.filhoDireito = no3;
no2.filhoEsquerdo = no4;
no2.filhoDireito = no5;
no3.filhoEsquerdo = no6;
no3.filhoDireito = no7;
return no1;
}
// Percurso em Pré-ordem (Raiz-Esquerda-Direita)
public void percursoPreOrdem(NoArvore no) {
if (no == null) {
return;
}
System.out.print(no.valor + " "); // Visita a raiz
percursoPreOrdem(no.filhoEsquerdo); // Percorre a subárvore esquerda
percursoPreOrdem(no.filhoDireito); // Percorre a subárvore direita
}
// Percurso em Ordem (Esquerda-Raiz-Direita)
public void percursoEmOrdem(NoArvore no) {
if (no == null) {
return;
}
percursoEmOrdem(no.filhoEsquerdo); // Percorre a subárvore esquerda
System.out.print(no.valor + " "); // Visita a raiz
percursoEmOrdem(no.filhoDireito); // Percorre a subárvore direita
}
// Percurso em Pós-ordem (Esquerda-Direita-Raiz)
public void percursoPosOrdem(NoArvore no) {
if (no == null) {
return;
}
percursoPosOrdem(no.filhoEsquerdo); // Percorre a subárvore esquerda
percursoPosOrdem(no.filhoDireito); // Percorre a subárvore direita
System.out.print(no.valor + " "); // Visita a raiz
}
// Contar o número total de nós
public int contarNos(NoArvore no) {
if (no == null) {
return 0;
}
return 1 + contarNos(no.filhoEsquerdo) + contarNos(no.filhoDireito);
}
// Contar o número de nós folha
public int contarFolhas(NoArvore no) {
if (no == null) {
return 0;
}
if (no.filhoEsquerdo == null && no.filhoDireito == null) {
return 1; // É uma folha
}
return contarFolhas(no.filhoEsquerdo) + contarFolhas(no.filhoDireito);
}
// Obter o número de nós em um determinado nível K
public int contarNosNivelK(NoArvore no, int k) {
if (no == null || k <= 0) {
return 0;
}
if (k == 1) {
return 1; // Encontrou um nó no nível K
}
// Soma os nós no nível K-1 das subárvores esquerda e direita
return contarNosNivelK(no.filhoEsquerdo, k - 1) + contarNosNivelK(no.filhoDireito, k - 1);
}
// Obter a altura da árvore
public int obterAltura(NoArvore no) {
if (no == null) {
return 0;
}
int alturaEsquerda = obterAltura(no.filhoEsquerdo);
int alturaDireita = obterAltura(no.filhoDireito);
return 1 + Math.max(alturaEsquerda, alturaDireita); // 1 para o nó atual
}
// Verificar se um valor existe na árvore
public boolean buscarValor(NoArvore no, int valorBuscado) {
if (no == null) {
return false;
}
if (no.valor == valorBuscado) {
return true;
}
return buscarValor(no.filhoEsquerdo, valorBuscado) || buscarValor(no.filhoDireito, valorBuscado);
}
// Percurso em Nível (BFS)
public void percursoEmNivel(NoArvore no) {
if (no == null) {
return;
}
Queue<noarvore> fila = new LinkedList<>();
fila.offer(no); // Adiciona a raiz à fila
while (!fila.isEmpty()) {
NoArvore atual = fila.poll(); // Remove o nó da frente da fila
System.out.print(atual.valor + " ");
if (atual.filhoEsquerdo != null) {
fila.offer(atual.filhoEsquerdo);
}
if (atual.filhoDireito != null) {
fila.offer(atual.filhoDireito);
}
}
}
// Verificar se é uma Árvore Binária Completa
public boolean ehArvoreCompleta(NoArvore no) {
if (no == null) {
return true; // Uma árvore vazia é considerada completa
}
Queue<noarvore> fila = new LinkedList<>();
fila.offer(no);
boolean encontrouNulo = false; // Flag para indicar se já encontramos um nó nulo
while (!fila.isEmpty()) {
NoArvore atual = fila.poll();
if (atual == null) {
encontrouNulo = true; // A partir daqui, todos os nós restantes na fila devem ser nulos
} else {
if (encontrouNulo) {
// Se já encontramos um nulo e agora encontramos um não nulo, não é completa
return false;
}
// Adiciona os filhos à fila (mesmo que sejam nulos para verificação posterior)
fila.offer(atual.filhoEsquerdo);
fila.offer(atual.filhoDireito);
}
}
return true;
}
}
</noarvore></noarvore>
Para testar as operações:
public class TestarArvore {
public static void main(String[] args) {
ArvoreBinaria arvore = new ArvoreBinaria();
arvore.raiz = arvore.construirArvoreExemplo();
System.out.println("Percurso Pré-ordem:");
arvore.percursoPreOrdem(arvore.raiz);
System.out.println("\nPercurso Em Ordem:");
arvore.percursoEmOrdem(arvore.raiz);
System.out.println("\nPercurso Pós-ordem:");
arvore.percursoPosOrdem(arvore.raiz);
System.out.println("\n\nNúmero total de nós: " + arvore.contarNos(arvore.raiz));
System.out.println("Número de nós folha: " + arvore.contarFolhas(arvore.raiz));
System.out.println("Número de nós no nível 3: " + arvore.contarNosNivelK(arvore.raiz, 3));
System.out.println("Altura da árvore: " + arvore.obterAltura(arvore.raiz));
System.out.println("Valor 5 existe na árvore? " + arvore.buscarValor(arvore.raiz, 5));
System.out.println("Valor 10 existe na árvore? " + arvore.buscarValor(arvore.raiz, 10));
System.out.println("Percurso Em Nível:");
arvore.percursoEmNivel(arvore.raiz);
System.out.println("\nÉ uma árvore completa? " + arvore.ehArvoreCompleta(arvore.raiz));
}
}
Problemas Comuns de Entrevista Envolvendo Árvores Binárias
As árvores binárias são um tópico frequente em entrevistas de programação. Muitos problemas podem ser resolvidos de forma elegante usando recursão ou estruturas de dados auxiliares como pilhas e filas.
1. Verificando a Igualdade entre Duas Árvores
O objetivo é determinar se duas árvores binárias são estruturalmente idênticas e se contêm os mesmos valores em posições correspondentes. Duas árvores são consideradas iguais se:
- Ambas são nulas.
- Ambas não são nulas, seus nós raízes têm o mesmo valor, e suas subárvores esquerdas são iguais, e suas subárvores direitas são iguais.
class SolucaoIgualdade {
// A classe NoArvore deve estar definida ou ser compatível
// static class NoArvore { int valor; NoArvore filhoEsquerdo; NoArvore filhoDireito; ... }
public boolean saoDuasArvoresIdenticas(NoArvore p, NoArvore q) {
if (p == null && q == null) {
return true; // Ambas são nulas, são idênticas
}
if (p == null || q == null) {
return false; // Uma é nula e a outra não, não são idênticas
}
if (p.valor != q.valor) {
return false; // Valores dos nós raízes são diferentes
}
// Verifica recursivamente as subárvores
return saoDuasArvoresIdenticas(p.filhoEsquerdo, q.filhoEsquerdo) &&
saoDuasArvoresIdenticas(p.filhoDireito, q.filhoDireito);
}
}
2. Identificando uma Subárvore
Este problema pede para verificar se uma árvore 'sub' é uma subárvore de outra árvore 'principal'. Uma subárvore é definida como uma árvore idêntica à árvore 'sub', que está enraizada em algum nó da árvore 'principal'.
class SolucaoSubarvore {
// A classe NoArvore e o método saoDuasArvoresIdenticas devem estar disponíveis
// (usar o método do problema anterior)
public boolean contemSubarvore(NoArvore principal, NoArvore sub) {
if (principal == null) {
return false; // Se a árvore principal for nula, não pode conter uma subárvore (exceto se sub também for nula, mas a definição geralmente exclui isso)
}
if (sub == null) {
return true; // Uma árvore nula é sempre considerada uma subárvore
}
// Verifica se a subárvore 'sub' é idêntica à árvore 'principal' a partir do nó atual
if (new SolucaoIgualdade().saoDuasArvoresIdenticas(principal, sub)) {
return true;
}
// Continua a busca nas subárvores esquerda e direita da árvore principal
return contemSubarvore(principal.filhoEsquerdo, sub) || contemSubarvore(principal.filhoDireito, sub);
}
}
3. Inverter uma Árvore Binária
A operação de inversão de uma árvore binária significa trocar os filhos esquerdo e direito de cada nó.
class SolucaoInversao {
public NoArvore inverterArvore(NoArvore raiz) {
if (raiz == null) {
return null; // Uma árvore vazia não pode ser invertida
}
// Troca os filhos do nó atual
NoArvore temp = raiz.filhoEsquerdo;
raiz.filhoEsquerdo = raiz.filhoDireito;
raiz.filhoDireito = temp;
// Inverte recursivamente as subárvores
inverterArvore(raiz.filhoEsquerdo);
inverterArvore(raiz.filhoDireito);
return raiz;
}
}
4. Verificar se uma Árvore é Balanceada
Uma árvore binária balanceada é definida como aquela em que, para cada nó, a diferença de altura entre suas subárvores esquerda e direita não excede 1. Uma abordagem comum é calcular a altura e verificar o balanceamento em uma única passagem recursiva.
class SolucaoBalanceamento {
public boolean ehBalanceada(NoArvore raiz) {
// Se a altura retornada for -1, significa que a subárvore não é balanceada
return calcularAlturaBalanceada(raiz) != -1;
}
// Retorna a altura da árvore se balanceada, -1 caso contrário
private int calcularAlturaBalanceada(NoArvore no) {
if (no == null) {
return 0; // Altura de uma árvore vazia é 0
}
int alturaEsquerda = calcularAlturaBalanceada(no.filhoEsquerdo);
if (alturaEsquerda == -1) {
return -1; // Subárvore esquerda não é balanceada
}
int alturaDireita = calcularAlturaBalanceada(no.filhoDireito);
if (alturaDireita == -1) {
return -1; // Subárvore direita não é balanceada
}
// Verifica a condição de balanceamento para o nó atual
if (Math.abs(alturaEsquerda - alturaDireita) > 1) {
return -1; // O nó atual não é balanceado
}
// Se o nó é balanceado, retorna sua altura
return 1 + Math.max(alturaEsquerda, alturaDireita);
}
}
5. Verificar se uma Árvore é Simétrica
Uma árvore é simétrica se for um espelho de si mesma em torno de sua raiz. Isso significa que a subárvore esquerda deve ser uma imagem espelhada da subárvore direita.
class SolucaoSimetria {
public boolean ehSimetrica(NoArvore raiz) {
if (raiz == null) {
return true; // Uma árvore vazia é simétrica
}
return verificarSimetria(raiz.filhoEsquerdo, raiz.filhoDireito);
}
private boolean verificarSimetria(NoArvore p, NoArvore q) {
if (p == null && q == null) {
return true; // Ambos são nulos, simétricos neste ponto
}
if (p == null || q == null) {
return false; // Um é nulo e o outro não, não simétricos
}
if (p.valor != q.valor) {
return false; // Valores diferentes, não simétricos
}
// Para simetria, o filho esquerdo de 'p' deve ser espelho do filho direito de 'q'
// E o filho direito de 'p' deve ser espelho do filho esquerdo de 'q'
return verificarSimetria(p.filhoEsquerdo, q.filhoDireito) &&
verificarSimetria(p.filhoDireito, q.filhoEsquerdo);
}
}
6. Construção de Árvore a Partir de String de Pré-ordem (com '#')
Dada uma string que representa o percurso em pré-ordem de uma árvore binária, onde '#' denota um nó nulo, reconstruir a árvore e realizar um percurso em ordem.
import java.util.Scanner;
class NoChar { // Usamos char para valores de nó
char dado;
NoChar esquerdo;
NoChar direito;
public NoChar(char dado) {
this.dado = dado;
}
}
class SolucaoConstrucaoPreOrdem {
private int indiceGlobal = 0; // Usado para rastrear a posição atual na string
public NoChar construirArvore(String entrada) {
indiceGlobal = 0; // Resetar para cada nova chamada
return construir(entrada);
}
private NoChar construir(String entrada) {
if (indiceGlobal >= entrada.length()) {
return null;
}
char caractereAtual = entrada.charAt(indiceGlobal);
indiceGlobal++;
if (caractereAtual == '#') {
return null; // Nó nulo
} else {
NoChar novoNo = new NoChar(caractereAtual);
novoNo.esquerdo = construir(entrada); // Construir subárvore esquerda
novoNo.direito = construir(entrada); // Construir subárvore direita
return novoNo;
}
}
public void percursoEmOrdem(NoChar no) {
if (no == null) {
return;
}
percursoEmOrdem(no.esquerdo);
System.out.print(no.dado + " ");
percursoEmOrdem(no.direito);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Digite a string de pré-ordem (use # para nós nulos):");
while (scanner.hasNextLine()) {
String linha = scanner.nextLine();
SolucaoConstrucaoPreOrdem construtor = new SolucaoConstrucaoPreOrdem();
NoChar raiz = construtor.construirArvore(linha);
System.out.print("Percurso Em Ordem da árvore construída: ");
construtor.percursoEmOrdem(raiz);
System.out.println("\n");
System.out.println("Digite a próxima string ou pressione Enter para sair:");
}
scanner.close();
}
}
7. Percurso em Nível Agrupado
Similar ao percurso em nível básico, mas o resultado deve ser uma lista de listas, onde cada lista interna representa os nós de um nível específico.
import java.util.*;
class SolucaoPercursoNivelAgrupado {
public List<list>> percursoNivel(NoArvore raiz) {
List<list>> resultado = new ArrayList<>();
if (raiz == null) {
return resultado;
}
Queue<noarvore> fila = new LinkedList<>();
fila.offer(raiz);
while (!fila.isEmpty()) {
int tamanhoNivel = fila.size(); // Número de nós no nível atual
List<integer> nivelAtualValores = new ArrayList<>();
// Processa todos os nós do nível atual
for (int i = 0; i < tamanhoNivel; i++) {
NoArvore noAtual = fila.poll();
nivelAtualValores.add(noAtual.valor);
// Adiciona os filhos para o próximo nível
if (noAtual.filhoEsquerdo != null) {
fila.offer(noAtual.filhoEsquerdo);
}
if (noAtual.filhoDireito != null) {
fila.offer(noAtual.filhoDireito);
}
}
resultado.add(nivelAtualValores); // Adiciona a lista de valores do nível atual ao resultado final
}
return resultado;
}
}
</integer></noarvore></list></list>
8. Ancestral Comum Mais Próximo (LCA)
Dado uma árvore binária e dois nós 'p' e 'q' presentes na árvore, encontrar o ancestral comum mais próximo. O ancestral comum mais próximo é o nó de maior profundidade que possui 'p' e 'q' como descendentes (onde um nó pode ser descendente de si mesmo).
class SolucaoLCA {
public NoArvore encontrarLCA(NoArvore raiz, NoArvore p, NoArvore q) {
if (raiz == null || raiz == p || raiz == q) {
return raiz; // Se a raiz for nula ou um dos nós p/q, ela é o LCA (ou o ponto de parada)
}
// Busca o LCA nas subárvores esquerda e direita
NoArvore lcaEsquerdo = encontrarLCA(raiz.filhoEsquerdo, p, q);
NoArvore lcaDireito = encontrarLCA(raiz.filhoDireito, p, q);
// Se ambos os resultados não são nulos, significa que p e q foram encontrados
// em subárvores diferentes, então a raiz atual é o LCA.
if (lcaEsquerdo != null && lcaDireito != null) {
return raiz;
}
// Se apenas a subárvore esquerda encontrou um LCA (ou p/q), ele é o resultado.
if (lcaEsquerdo != null) {
return lcaEsquerdo;
}
// Caso contrário, o LCA (ou p/q) está na subárvore direita.
return lcaDireito;
}
}
9. Recosntruir Árvore a Partir de Pré-ordem e Em Ordem
Dadas duas sequências de percurso (pré-ordem e em ordem) de uma árvore binária, reconstruir a árvore original.
Princípio: O primeiro elemento da sequência de pré-ordem é sempre a raiz. Na sequência em ordem, os elementos à esquerda da raiz pertencem à subárvore esquerda, e os elementos à direita pertencem à subárvore direita.
class SolucaoReconstrucaoPreEm {
private int indicePreOrdem = 0; // Índice para a sequência de pré-ordem
public NoArvore construir(int[] preOrdem, int[] emOrdem) {
indicePreOrdem = 0;
// Mapeia valores para seus índices na sequência em ordem para busca rápida
Map<integer integer=""> mapaEmOrdem = new HashMap<>();
for (int i = 0; i < emOrdem.length; i++) {
mapaEmOrdem.put(emOrdem[i], i);
}
return construirRecursivo(preOrdem, 0, emOrdem.length - 1, mapaEmOrdem);
}
private NoArvore construirRecursivo(int[] preOrdem, int inicioEmOrdem, int fimEmOrdem, Map<integer integer=""> mapaEmOrdem) {
if (inicioEmOrdem > fimEmOrdem || indicePreOrdem >= preOrdem.length) {
return null; // Condição de parada: subárvore vazia
}
int valorRaiz = preOrdem[indicePreOrdem++];
NoArvore raizAtual = new NoArvore(valorRaiz);
// Encontra a posição da raiz na sequência em ordem
int indiceRaizEmOrdem = mapaEmOrdem.get(valorRaiz);
// Constrói a subárvore esquerda
raizAtual.filhoEsquerdo = construirRecursivo(preOrdem, inicioEmOrdem, indiceRaizEmOrdem - 1, mapaEmOrdem);
// Constrói a subárvore direita
raizAtual.filhoDireito = construirRecursivo(preOrdem, indiceRaizEmOrdem + 1, fimEmOrdem, mapaEmOrdem);
return raizAtual;
}
}
</integer></integer>
10. Reconstruir Árvore a Partir de Em Ordem e Pós-ordem
Semelhante ao problema anterior.
Princípio: O último elemento da sequência de pós-ordem é sempre a raiz. Na sequência em ordem, os elementos à esquerda da raiz pertencem à subárvore esquerda, e os elementos à direita pertencem à subárvore direita.
class SolucaoReconstrucaoEmPos {
private int indicePosOrdem; // Índice para a sequência de pós-ordem
public NoArvore construir(int[] emOrdem, int[] posOrdem) {
indicePosOrdem = posOrdem.length - 1; // Começa do final da pós-ordem
Map<integer integer=""> mapaEmOrdem = new HashMap<>();
for (int i = 0; i < emOrdem.length; i++) {
mapaEmOrdem.put(emOrdem[i], i);
}
return construirRecursivo(posOrdem, 0, emOrdem.length - 1, mapaEmOrdem);
}
private NoArvore construirRecursivo(int[] posOrdem, int inicioEmOrdem, int fimEmOrdem, Map<integer integer=""> mapaEmOrdem) {
if (inicioEmOrdem > fimEmOrdem || indicePosOrdem < 0) {
return null; // Condição de parada
}
int valorRaiz = posOrdem[indicePosOrdem--]; // Pega o último elemento e move o índice para trás
NoArvore raizAtual = new NoArvore(valorRaiz);
int indiceRaizEmOrdem = mapaEmOrdem.get(valorRaiz);
// Importante: para pós-ordem, construímos a subárvore direita primeiro!
raizAtual.filhoDireito = construirRecursivo(posOrdem, indiceRaizEmOrdem + 1, fimEmOrdem, mapaEmOrdem);
raizAtual.filhoEsquerdo = construirRecursivo(posOrdem, inicioEmOrdem, indiceRaizEmOrdem - 1, mapaEmOrdem);
return raizAtual;
}
}
</integer></integer>
11. Converter Árvore Binária em String
Dada a raiz de uma árvore binária, construir uma string usando percurso em pré-ordem. Regras especiais para parênteses:
- Parênteses em torno do filho esquerdo nunca podem ser omitidos se houver um filho direito não nulo.
- Parênteses em torno do filho direito podem ser omitidos se ele for nulo.
class SolucaoArvoreParaString {
public String converterParaString(NoArvore raiz) {
StringBuilder resultado = new StringBuilder();
gerarStringRecursivo(raiz, resultado);
return resultado.toString();
}
private void gerarStringRecursivo(NoArvore no, StringBuilder sb) {
if (no == null) {
return;
}
sb.append(no.valor); // Adiciona o valor do nó atual
// Processa o filho esquerdo
if (no.filhoEsquerdo != null) {
sb.append("(");
gerarStringRecursivo(no.filhoEsquerdo, sb);
sb.append(")");
} else if (no.filhoDireito != null) {
// Se o filho esquerdo é nulo, mas o direito não é, devemos adicionar "()" para o esquerdo
sb.append("()");
}
// Processa o filho direito (apenas se não for nulo)
if (no.filhoDireito != null) {
sb.append("(");
gerarStringRecursivo(no.filhoDireito, sb);
sb.append(")");
}
}
}
12. Percurso em Pré-ordem (Iterativo/Não Recursivo)
Implementar o percurso em pré-ordem usando uma pilha para simular a recursão.
import java.util.*;
class SolucaoPreOrdemIterativa {
public List<integer> percurso(NoArvore raiz) {
List<integer> resultado = new ArrayList<>();
if (raiz == null) {
return resultado;
}
Stack<noarvore> pilha = new Stack<>();
pilha.push(raiz); // Começa com a raiz na pilha
while (!pilha.isEmpty()) {
NoArvore noAtual = pilha.pop(); // Visita o nó (Raiz)
resultado.add(noAtual.valor);
// Adiciona o filho direito primeiro, para que o esquerdo seja desempilhado primeiro (LIFO)
if (noAtual.filhoDireito != null) {
pilha.push(noAtual.filhoDireito);
}
if (noAtual.filhoEsquerdo != null) {
pilha.push(noAtual.filhoEsquerdo);
}
}
return resultado;
}
}
</noarvore></integer></integer>
13. Percurso em Ordem (Iterativo/Não Recursivo)
Implementar o percurso em ordem usando uma pilha.
import java.util.*;
class SolucaoEmOrdemIterativa {
public List<integer> percurso(NoArvore raiz) {
List<integer> resultado = new ArrayList<>();
Stack<noarvore> pilha = new Stack<>();
NoArvore noAtual = raiz;
while (noAtual != null || !pilha.isEmpty()) {
// Primeiro, navega até o nó mais à esquerda, empilhando todos os nós no caminho
while (noAtual != null) {
pilha.push(noAtual);
noAtual = noAtual.filhoEsquerdo;
}
// Pop o nó mais à esquerda, visita-o (Raiz)
noAtual = pilha.pop();
resultado.add(noAtual.valor);
// Agora, move para a subárvore direita
noAtual = noAtual.filhoDireito;
}
return resultado;
}
}
</noarvore></integer></integer>
14. Percurso em Pós-ordem (Iterativo/Não Recursivo)
Este é o mais complexo dos percursos iterativos, pois um nó só pode ser visitado após ambos os seus filhos serem visitados. Uma abordagem é usar duas pilhas ou uma pilha com um controle de último visitado.
import java.util.*;
class SolucaoPosOrdemIterativa {
public List<integer> percurso(NoArvore raiz) {
List<integer> resultado = new ArrayList<>();
if (raiz == null) {
return resultado;
}
Stack<noarvore> pilha = new Stack<>();
NoArvore noAtual = raiz;
NoArvore ultimoVisitado = null; // Para controlar se o filho direito já foi visitado
while (noAtual != null || !pilha.isEmpty()) {
// Navega para a esquerda, empilhando os nós
while (noAtual != null) {
pilha.push(noAtual);
noAtual = noAtual.filhoEsquerdo;
}
// Olha o topo da pilha sem remover
NoArvore topo = pilha.peek();
// Se o filho direito existe e ainda não foi visitado
if (topo.filhoDireito != null && topo.filhoDireito != ultimoVisitado) {
noAtual = topo.filhoDireito; // Move para a direita
} else {
// Se não tem filho direito ou o direito já foi visitado,
// visita o nó atual (Raiz)
resultado.add(topo.valor);
ultimoVisitado = pilha.pop(); // Marca como visitado e remove da pilha
noAtual = null; // Reinicia a busca para o próximo nó na pilha
}
}
return resultado;
}
}
</noarvore></integer></integer>