Árvore Binária | Rust Brasil

Introdução

A árvore binária é uma das estruturas de dados mais fundamentais da ciência da computação. Ela organiza elementos de forma hierárquica, onde cada nó pode ter no máximo dois filhos: um à esquerda e outro à direita. Essa estrutura serve de base para diversas outras árvores especializadas, como BSTs, árvores AVL e heaps.

Em Rust, a implementação de árvores binárias é um excelente exercício para compreender o sistema de ownership, o uso de Box<T> para alocação no heap e o pattern matching com enum. Neste artigo, exploraremos a teoria por trás das árvores binárias, implementaremos uma versão completa em Rust e veremos aplicações práticas.

Conceito e Teoria

Terminologia Fundamental

Antes de mergulhar na implementação, é essencial entender a terminologia das árvores:

            Raiz (Root)
              [10]              <- Nível 0 (Profundidade 0)
             /    \
           [5]    [15]          <- Nível 1 (Profundidade 1)
          /   \      \
        [3]   [7]   [20]       <- Nível 2 (Profundidade 2)
        /       \
      [1]      [8]             <- Nível 3 (Profundidade 3)
       ^        ^
     Folhas (sem filhos)

Raiz (Root): O nó no topo da árvore, sem pai. No exemplo acima, é o nó [10].
Folha (Leaf): Um nó sem filhos. No exemplo, [1], [8] e [20] são folhas.
Altura (Height): O comprimento do caminho mais longo da raiz até uma folha. A árvore acima tem altura 3.
Profundidade (Depth): A distância de um nó até a raiz. O nó [7] tem profundidade 2.
Grau: O número de filhos de um nó. Em uma árvore binária, o grau máximo é 2.
Subárvore: Qualquer nó junto com todos os seus descendentes forma uma subárvore.

Tipos de Árvores Binárias

  Árvore Completa         Árvore Cheia         Árvore Degenerada
      [A]                    [A]                    [A]
     /   \                  /   \                     \
   [B]   [C]              [B]   [C]                  [B]
  /   \                  / \   / \                      \
[D]   [E]              [D][E][F][G]                    [C]
                                                          \
Todos os níveis       Cada nó tem            Cada nó tem    [D]
preenchidos da        0 ou 2 filhos          apenas 1 filho
esquerda p/ direita

Completa: Todos os níveis preenchidos, exceto possivelmente o último, que é preenchido da esquerda para a direita.
Cheia (Full): Todo nó tem exatamente 0 ou 2 filhos.
Degenerada: Cada nó tem no máximo 1 filho, comportando-se como uma lista encadeada.

Complexidade

Operação	Melhor Caso	Caso Médio	Pior Caso
Busca	O(1)	O(n)	O(n)
Inserção	O(1)	O(n)	O(n)
Remoção	O(1)	O(n)	O(n)
Travessia (qualquer)	O(n)	O(n)	O(n)
Altura	O(n)	O(n)	O(n)
Contar nós	O(n)	O(n)	O(n)
Espaço	—	O(n)	O(n)

Nota: Em uma árvore binária genérica (sem ordenação), a busca exige percorrer todos os nós. Árvores de busca binária (BSTs) melhoram isso para O(log n) no caso médio.

Implementação em Rust

A seguir, implementamos uma árvore binária genérica com suporte a todas as operações fundamentais e os quatro tipos de travessia.

use std::collections::VecDeque;
use std::fmt::Display;

/// Representa uma árvore binária usando enum recursivo.
/// `Vazia` indica ausência de nó, e `No` contém o valor e dois filhos.
#[derive(Debug, Clone)]
enum ArvoreBinaria<T> {
    Vazia,
    No {
        valor: T,
        esquerda: Box<ArvoreBinaria<T>>,
        direita: Box<ArvoreBinaria<T>>,
    },
}

impl<T: Display + Clone> ArvoreBinaria<T> {
    /// Cria uma árvore vazia
    fn nova() -> Self {
        ArvoreBinaria::Vazia
    }

    /// Cria um nó folha (sem filhos)
    fn folha(valor: T) -> Self {
        ArvoreBinaria::No {
            valor,
            esquerda: Box::new(ArvoreBinaria::Vazia),
            direita: Box::new(ArvoreBinaria::Vazia),
        }
    }

    /// Cria um nó com filhos especificados
    fn novo_no(valor: T, esquerda: ArvoreBinaria<T>, direita: ArvoreBinaria<T>) -> Self {
        ArvoreBinaria::No {
            valor,
            esquerda: Box::new(esquerda),
            direita: Box::new(direita),
        }
    }

    /// Verifica se a árvore está vazia
    fn esta_vazia(&self) -> bool {
        matches!(self, ArvoreBinaria::Vazia)
    }

    /// Retorna a altura da árvore (-1 para árvore vazia)
    fn altura(&self) -> i32 {
        match self {
            ArvoreBinaria::Vazia => -1,
            ArvoreBinaria::No { esquerda, direita, .. } => {
                let alt_esq = esquerda.altura();
                let alt_dir = direita.altura();
                1 + alt_esq.max(alt_dir)
            }
        }
    }

    /// Conta o número total de nós na árvore
    fn contar_nos(&self) -> usize {
        match self {
            ArvoreBinaria::Vazia => 0,
            ArvoreBinaria::No { esquerda, direita, .. } => {
                1 + esquerda.contar_nos() + direita.contar_nos()
            }
        }
    }

    /// Conta o número de folhas (nós sem filhos)
    fn contar_folhas(&self) -> usize {
        match self {
            ArvoreBinaria::Vazia => 0,
            ArvoreBinaria::No { esquerda, direita, .. } => {
                if esquerda.esta_vazia() && direita.esta_vazia() {
                    1
                } else {
                    esquerda.contar_folhas() + direita.contar_folhas()
                }
            }
        }
    }

    // === TRAVESSIAS ===

    /// Travessia em pré-ordem: raiz -> esquerda -> direita
    fn pre_ordem(&self, resultado: &mut Vec<T>) {
        if let ArvoreBinaria::No { valor, esquerda, direita } = self {
            resultado.push(valor.clone());
            esquerda.pre_ordem(resultado);
            direita.pre_ordem(resultado);
        }
    }

    /// Travessia em ordem (in-order): esquerda -> raiz -> direita
    fn em_ordem(&self, resultado: &mut Vec<T>) {
        if let ArvoreBinaria::No { valor, esquerda, direita } = self {
            esquerda.em_ordem(resultado);
            resultado.push(valor.clone());
            direita.em_ordem(resultado);
        }
    }

    /// Travessia em pós-ordem: esquerda -> direita -> raiz
    fn pos_ordem(&self, resultado: &mut Vec<T>) {
        if let ArvoreBinaria::No { valor, esquerda, direita } = self {
            esquerda.pos_ordem(resultado);
            direita.pos_ordem(resultado);
            resultado.push(valor.clone());
        }
    }

    /// Travessia em nível (level-order / BFS)
    fn em_nivel(&self) -> Vec<T> {
        let mut resultado = Vec::new();
        let mut fila: VecDeque<&ArvoreBinaria<T>> = VecDeque::new();
        fila.push_back(self);

        while let Some(atual) = fila.pop_front() {
            if let ArvoreBinaria::No { valor, esquerda, direita } = atual {
                resultado.push(valor.clone());
                if !esquerda.esta_vazia() {
                    fila.push_back(esquerda);
                }
                if !direita.esta_vazia() {
                    fila.push_back(direita);
                }
            }
        }

        resultado
    }

    /// Exibe a árvore de forma visual (rotacionada 90 graus)
    fn exibir(&self, prefixo: &str, eh_direita: bool) {
        if let ArvoreBinaria::No { valor, esquerda, direita } = self {
            let conector = if eh_direita { "├── " } else { "└── " };
            let extensao = if eh_direita { "│   " } else { "    " };

            println!("{}{}{}", prefixo, conector, valor);

            let novo_prefixo = format!("{}{}", prefixo, extensao);
            direita.exibir(&novo_prefixo, true);
            esquerda.exibir(&novo_prefixo, false);
        }
    }
}

fn main() {
    // Construção manual da árvore:
    //         1
    //        / \
    //       2   3
    //      / \   \
    //     4   5   6
    let arvore = ArvoreBinaria::novo_no(
        1,
        ArvoreBinaria::novo_no(
            2,
            ArvoreBinaria::folha(4),
            ArvoreBinaria::folha(5),
        ),
        ArvoreBinaria::novo_no(
            3,
            ArvoreBinaria::Vazia,
            ArvoreBinaria::folha(6),
        ),
    );

    println!("=== Árvore Binária ===");
    println!("Altura: {}", arvore.altura());
    println!("Total de nós: {}", arvore.contar_nos());
    println!("Total de folhas: {}", arvore.contar_folhas());

    // Travessias
    let mut pre = Vec::new();
    arvore.pre_ordem(&mut pre);
    println!("\nPré-ordem:  {:?}", pre);

    let mut em = Vec::new();
    arvore.em_ordem(&mut em);
    println!("Em ordem:   {:?}", em);

    let mut pos = Vec::new();
    arvore.pos_ordem(&mut pos);
    println!("Pós-ordem:  {:?}", pos);

    let nivel = arvore.em_nivel();
    println!("Em nível:   {:?}", nivel);

    // Visualização
    println!("\nVisualização da árvore:");
    arvore.exibir("", false);
}

Métodos Principais

Método	Descrição
`nova()`	Cria uma árvore vazia
`folha(valor)`	Cria um nó folha contendo o valor informado
`novo_no(v, e, d)`	Cria um nó com valor `v`, subárvore esquerda `e` e direita `d`
`esta_vazia()`	Retorna `true` se a árvore é vazia
`altura()`	Calcula a altura da árvore recursivamente
`contar_nos()`	Retorna o número total de nós
`contar_folhas()`	Retorna o número de nós folha
`pre_ordem()`	Travessia: raiz, esquerda, direita
`em_ordem()`	Travessia: esquerda, raiz, direita
`pos_ordem()`	Travessia: esquerda, direita, raiz
`em_nivel()`	Travessia por largura (BFS) usando fila

Entendendo as Travessias

Árvore:        [A]
              /   \
            [B]   [C]
           /   \
         [D]   [E]

Pré-ordem  (Raiz-Esq-Dir):  A, B, D, E, C
Em ordem   (Esq-Raiz-Dir):  D, B, E, A, C
Pós-ordem  (Esq-Dir-Raiz):  D, E, B, C, A
Em nível   (BFS):           A, B, C, D, E

Exemplo Prático: Árvore de Expressões Aritméticas

Uma aplicação clássica de árvores binárias é representar e avaliar expressões matemáticas. Cada nó interno é um operador e cada folha é um operando.

/// Representa um token de expressão: número ou operador
#[derive(Debug, Clone)]
enum Token {
    Numero(f64),
    Operador(char), // '+', '-', '*', '/'
}

/// Árvore de expressão aritmética
#[derive(Debug, Clone)]
enum ArvoreExpressao {
    Vazia,
    No {
        token: Token,
        esquerda: Box<ArvoreExpressao>,
        direita: Box<ArvoreExpressao>,
    },
}

impl ArvoreExpressao {
    /// Cria um nó folha numérico
    fn numero(valor: f64) -> Self {
        ArvoreExpressao::No {
            token: Token::Numero(valor),
            esquerda: Box::new(ArvoreExpressao::Vazia),
            direita: Box::new(ArvoreExpressao::Vazia),
        }
    }

    /// Cria um nó operador com duas subárvores
    fn operador(op: char, esq: ArvoreExpressao, dir: ArvoreExpressao) -> Self {
        ArvoreExpressao::No {
            token: Token::Operador(op),
            esquerda: Box::new(esq),
            direita: Box::new(dir),
        }
    }

    /// Avalia a expressão representada pela árvore
    fn avaliar(&self) -> f64 {
        match self {
            ArvoreExpressao::Vazia => 0.0,
            ArvoreExpressao::No { token, esquerda, direita } => {
                match token {
                    Token::Numero(n) => *n,
                    Token::Operador(op) => {
                        let esq = esquerda.avaliar();
                        let dir = direita.avaliar();
                        match op {
                            '+' => esq + dir,
                            '-' => esq - dir,
                            '*' => esq * dir,
                            '/' => {
                                if dir == 0.0 {
                                    panic!("Divisão por zero!");
                                }
                                esq / dir
                            }
                            _ => panic!("Operador desconhecido: {}", op),
                        }
                    }
                }
            }
        }
    }

    /// Gera a expressão em notação infixa com parênteses
    fn para_infixa(&self) -> String {
        match self {
            ArvoreExpressao::Vazia => String::new(),
            ArvoreExpressao::No { token, esquerda, direita } => {
                match token {
                    Token::Numero(n) => format!("{}", n),
                    Token::Operador(op) => {
                        format!(
                            "({} {} {})",
                            esquerda.para_infixa(),
                            op,
                            direita.para_infixa()
                        )
                    }
                }
            }
        }
    }
}

fn main() {
    // Expressão: (3 + 4) * (10 - 2)
    //
    //         [*]
    //        /   \
    //      [+]   [-]
    //     / \   /   \
    //   [3] [4] [10] [2]

    let expressao = ArvoreExpressao::operador(
        '*',
        ArvoreExpressao::operador(
            '+',
            ArvoreExpressao::numero(3.0),
            ArvoreExpressao::numero(4.0),
        ),
        ArvoreExpressao::operador(
            '-',
            ArvoreExpressao::numero(10.0),
            ArvoreExpressao::numero(2.0),
        ),
    );

    println!("Expressão: {}", expressao.para_infixa());
    println!("Resultado: {}", expressao.avaliar());
    // Saída: Expressão: ((3 + 4) * (10 - 2))
    // Saída: Resultado: 56
}

Comparação com Outras Estruturas

Critério	Árvore Binária	Lista Encadeada	Array/Vec
Busca (sem ordem)	O(n)	O(n)	O(n)
Inserção (posição)	O(1)*	O(1)*	O(n)
Representação hierárquica	Excelente	Ruim	Ruim
Uso de memória	Médio	Médio	Baixo
Travessia ordenada	Sim (in-order)	Sim (linear)	Sim (index)

* Quando a posição já é conhecida.

Quando usar Árvore Binária?

Use quando os dados são naturalmente hierárquicos (expressões, árvores de decisão, DOM).
Use como base para estruturas mais especializadas (BST, AVL, heap).
Não use para busca eficiente — prefira uma BST ou tabela hash.
Não use quando a ordem de inserção é mais importante que a hierarquia — prefira listas ou filas.

Exercícios

Exercício 1: Espelhamento de Árvore

Implemente um método espelhar() que inverta a árvore binária (troque todos os filhos esquerdos pelos direitos recursivamente). Após espelhar, a travessia em ordem deve retornar os valores na ordem inversa da original.

Original:       Espelhada:
    [1]            [1]
   /   \          /   \
 [2]   [3]      [3]   [2]
 / \              / \
[4] [5]         [5] [4]

Exercício 2: Verificar se Duas Árvores são Iguais

Escreva uma função sao_iguais(a, b) -> bool que compare duas árvores binárias e retorne true se possuem a mesma estrutura e os mesmos valores em cada posição correspondente.

Exercício 3: Caminho da Raiz até uma Folha

Implemente um método que encontre e imprima todos os caminhos da raiz até cada folha da árvore. Para a árvore do exemplo principal, a saída deve ser:

1 -> 2 -> 4
1 -> 2 -> 5
1 -> 3 -> 6

Conclusão

A árvore binária é o alicerce sobre o qual muitas outras estruturas de dados são construídas. Neste artigo, vimos como implementá-la em Rust usando enum e Box, aproveitando o pattern matching para escrever código elegante e seguro. As quatro formas de travessia — pré-ordem, em ordem, pós-ordem e em nível — são ferramentas essenciais que aparecem constantemente em algoritmos e entrevistas técnicas.

O sistema de tipos de Rust torna a implementação de árvores particularmente interessante: o enum com variantes Vazia e No elimina a necessidade de ponteiros nulos, e o Box garante que a memória é liberada corretamente quando a árvore sai de escopo. Nos próximos artigos, veremos como adicionar propriedades de ordenação (BST) e balanceamento (AVL, rubro-negra) a essa estrutura fundamental.