1. Além de sequências
Vetores, listas, pilhas e filas (capítulos 2 e 4) têm algo em comum: são estruturas lineares — cada item tem, no máximo, um "próximo" e um "anterior". Muitos dados do mundo real, porém, não são lineares — eles têm relações mais ricas, com ramificações e conexões múltiplas. Árvores e grafos são as estruturas que capturam esse tipo de relação. Este capítulo é uma introdução conceitual: o objetivo é reconhecer essas estruturas e entender seu vocabulário, não implementar os algoritmos de percurso em detalhe.
2. Árvore: estrutura hierárquica
Uma árvore é uma estrutura de dados hierárquica, organizada em nós conectados por relações de pai/filho. Ela começa num único nó chamado raiz, que pode ter zero ou mais filhos; cada filho, por sua vez, pode ter seus próprios filhos, e assim por diante. Um nó sem filhos é chamado de folha.
Uma árvore binária é o caso particular em que cada nó tem, no máximo, dois filhos — comumente chamados de filho esquerdo e filho direito.
Fig. 1 — Árvore binária: raiz no topo, cada nó com até dois filhos, folhas sem filhos.
3. Vocabulário de árvores
| Termo | Significado |
|---|---|
| Raiz | O nó do topo, sem pai — ponto de partida da árvore |
| Pai / filho | Relação direta entre um nó e os nós imediatamente abaixo dele |
| Folha | Nó sem nenhum filho |
| Altura | Número de níveis da raiz até a folha mais distante |
| Subárvore | Qualquer nó e tudo que está abaixo dele, tratado como uma árvore menor independente |
Repare que a definição de subárvore é o motivo pelo qual árvores combinam tão naturalmente com recursão (capítulo 5): processar uma árvore inteira normalmente significa "processar a raiz, depois processar recursivamente cada subárvore filha" — o mesmo padrão de "resolver uma peça pequena e delegar o resto" visto no capítulo anterior.
4. Árvores que você já usa todos os dias
Essa estrutura não é um exercício teórico — você já convive com árvores constantemente:
- Sistema de arquivos: uma pasta (nó) contém arquivos e outras pastas (filhos); a raiz é o diretório principal do disco.
- DOM do HTML: você já conhece isso de JavaScript/web.
<html>é a raiz, contendo<head>e<body>como filhos, que por sua vez contêm outros elementos — e cadadocument.querySelectorque você já escreveu estava, literalmente, navegando numa árvore. - Estrutura de comentários aninhados num fórum ou rede social: um comentário raiz pode ter respostas, que podem ter suas próprias respostas.
- Organograma de uma empresa: um cargo (nó) tem subordinados diretos (filhos).
Toda vez que você escreveu elemento.parentElement ou
elemento.children em JavaScript, você estava navegando pelas
relações de pai e filho de uma árvore — o DOM inteiro é, estruturalmente, uma árvore.
5. Grafo: a generalização
Um grafo generaliza a ideia de árvore removendo a exigência de hierarquia. Um grafo é formado por nós (também chamados de vértices) conectados por arestas — mas, diferente da árvore, não existe raiz obrigatória, um nó pode se conectar a quantos outros nós fizer sentido, e as conexões podem até formar ciclos (voltar ao ponto de partida).
Toda árvore é, tecnicamente, um tipo particular de grafo (um grafo hierárquico, sem ciclos, com um nó raiz definido) — mas nem todo grafo é uma árvore.
Fig. 2 — Grafo: nós conectados por arestas, sem hierarquia obrigatória — aqui, uma rede social simplificada.
6. Grafos no mundo real
- Rede social: cada pessoa é um nó; uma amizade ou conexão é uma aresta entre dois nós. Não existe uma "pessoa raiz" — todos podem se conectar a todos.
- Mapa de rotas: cada cidade (ou cruzamento) é um nó; cada estrada é uma aresta. Encontrar o caminho mais curto entre dois pontos — o que um aplicativo de GPS faz — é fundamentalmente um problema sobre grafos.
- Links entre páginas web: cada página é um nó; cada link para outra página é uma aresta direcionada.
- Dependências entre pacotes (como as do
package.jsonde um projeto Node): cada pacote é um nó; "pacote A depende de pacote B" é uma aresta.
Esse último exemplo é especialmente concreto: toda vez que o npm
resolve as dependências do seu projeto, ele está, por baixo dos panos, percorrendo um grafo
de dependências para descobrir a ordem certa de instalação e detectar conflitos ou
dependências circulares.
Percorrer um grafo (visitar todos os nós alcançáveis, ou encontrar um caminho entre dois nós específicos) é resolvido por algoritmos como busca em profundidade e busca em largura — nomes que você vai encontrar com frequência daqui para frente. Este capítulo não entra no detalhe de implementação desses dois algoritmos; o objetivo aqui foi reconhecer a estrutura e o vocabulário, que é a base necessária para estudá-los a fundo quando chegar a hora.
7. Onde isso te leva
Este é o último capítulo do Módulo 3, e com ele se encerram os três módulos de fundamentos do curso. Reveja o caminho percorrido: no Módulo 1 (Lógica de Programação) você aprendeu a estruturar o raciocínio de um algoritmo — sequência, decisão, repetição. No Módulo 2 (Matemática para Programação) você reforçou a base matemática que sustenta esse raciocínio. E neste Módulo 3, você aprendeu a medir a eficiência de um algoritmo (Big O) e conheceu as estruturas de dados que aparecem, com um nome ou outro, em qualquer linguagem de programação: vetores e matrizes, busca e ordenação, listas, pilhas e filas, recursividade, árvores e grafos.
Nada disso foi amarrado a uma linguagem específica de propósito — essa é precisamente a
ideia. A partir do próximo módulo, o Módulo 4, o curso mergulha
especificamente em C#. E boa parte do que você acabou de aprender vai reaparecer ali, agora
com nomes concretos e sintaxe própria: o vetor genérico vira array
e List<T>, a pilha e a fila ganham implementações prontas
chamadas Stack<T> e Queue<T>,
a recursão vira métodos C# chamando a si mesmos, e a notação Big O vai voltar quando o curso
discutir LINQ e o custo de cada operação sobre coleções. Você não vai aprender essas coisas
do zero — vai reconhecer conceitos que já são seus, só que com roupagem nova.