---
title: "Árvore Binária"
url: "https://rustlang.com.br/estruturas-dados/arvore-binaria/"
markdown_url: "https://rustlang.com.br/estruturas-dados/arvore-binaria.MD"
description: "Entenda os fundamentos das árvores binárias em Rust: terminologia, implementação com enum e Box, e os quatro tipos de travessia (in-order, pre-order, post-order, level-order)."
date: ""
author: "Equipe Rust Brasil"
---

# Árvore Binária

Entenda os fundamentos das árvores binárias em Rust: terminologia, implementação com enum e Box, e os quatro tipos de travessia (in-order, pre-order, post-order, level-order).


## 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:

```text
            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

```text
  Á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.

```rust
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

```text
Á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.

```rust
/// 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.

```text
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:

```text
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.