Travessias de Árvore

Conceito

As três travessias em profundidade — pré, in e pós-ordem — diferem em uma única coisa: quando você visita o nó em relação aos filhos.

pré-ordem:   NÓ,  esq, dir
in-ordem:    esq, NÓ,  dir
pós-ordem:   esq, dir, NÓ

O código é literalmente o mesmo com a linha da visita movida. Entender isso é entender as três de uma vez.

Por que in-order numa BST sai ordenado — a prova mais elegante da semana: o invariante da 2. Árvore de Busca Binária diz esquerda < nó < direita. Visitar nessa ordem é, por construção, visitar em ordem crescente. Não é coincidência nem propriedade emergente: é o invariante, lido em voz alta.

Para que serve cada uma:

Pós-ordem é a menos intuitiva e a mais reveladora: você usa quando o resultado do pai depende do resultado dos filhos. du -sh é uma pós-ordem. Avaliar (2+3)*4 é uma pós-ordem — é literalmente a notação polonesa reversa.

BFS (por nível) é diferente em natureza, não só em ordem. As três acima usam pilha (explícita ou a de chamadas); BFS usa fila (5. Fila). Você quer BFS quando:

• a resposta está provavelmente perto da raiz (busca em largura acha o mais próximo primeiro)
• você precisa processar nível por nível
• você quer o menor caminho em número de arestas (4. Grafos)

O custo é memória: DFS gasta O(altura), BFS gasta O(largura) — e a largura de uma árvore balanceada é ~n/2.

Em Go

Recursivo é o padrão e são cinco linhas. Duas variações idiomáticas valem conhecer.

1. Passar a função de visita (o clássico, funciona em qualquer versão):

func (n *No[T]) EmOrdem(visita func(T)) {
	if n == nil { return }
	n.Esq.EmOrdem(visita)
	visita(n.Val)
	n.Dir.EmOrdem(visita)
}

2. Iterador com range sobre função (Go 1.23+) — hoje é a forma idiomática, porque o consumidor usa for ... range normal e pode dar break:

func (n *No[T]) Ordenado() func(func(T) bool) {
	return func(yield func(T) bool) { n.percorre(yield) }
}

// uso:
for v := range arvore.Ordenado() {
	if v > 10 { break } // e a travessia PARA de verdade
}

O bool que yield devolve é o mecanismo de parada: false significa "o consumidor saiu do laço", e a travessia precisa propagar isso para cima. É o que torna o iterador composável com break — coisa que a versão com func(T) não consegue.

Travessia iterativa com 4. Pilha explícita é a saída quando a profundidade é risco (árvore degenerada com milhões de nós) ou quando você quer controlar o limite. Go não tem TCO, então a recursão consome frames de verdade — mas a stack cresce até 1 GB, o que dá muito espaço.

Respostas às perguntas-guia

1. Pré, in e pós-ordem: qual a única diferença entre as três?

Conceito: a posição da visita em relação às duas chamadas recursivas. Antes, no meio, depois.

Em Go: a linha visita(n.Val) muda de lugar. Nada mais.

2. Por que in-order numa BST sai ordenado?

Conceito: porque o invariante da BST é "esquerda < nó < direita", e in-order visita exatamente nessa sequência.

Em Go: é a base do teste de validação mais simples — percorra in-order e verifique que a saída é crescente. (Cuidado: isso só detecta violação, não distingue de duplicatas mal tratadas.)

3. Para que serve pós-ordem na prática (liberar recursos, avaliar expressão)?

Conceito: quando o pai precisa do resultado dos filhos. Liberar memória (filhos antes do pai, senão você perde o ponteiro), somar tamanho de diretório, avaliar árvore de expressão.

Em Go: liberar não se aplica (GC cuida), mas o padrão "agregar de baixo para cima" aparece em toda travessia de go/ast que calcula algo sobre subárvores — e em filepath.WalkDir quando você precisa somar tamanhos de diretório.

4. Quando você quer BFS por nível em vez de qualquer travessia em profundidade?

Conceito: quando a resposta está perto da raiz, quando você precisa de nível por nível, ou quando quer o menor caminho em número de arestas. Custa O(largura) de memória em vez de O(altura).

Em Go: BFS é um for len(fila) > 0 com um slice, ou um chan se houver concorrência. O truque para separar níveis é capturar len(fila) antes do laço interno — esse número é exatamente o tamanho do nível atual.

Trade-offs

Do conceito:

• DFS recursivo é o código mais curto e usa a pilha do runtime — que tem limite.
• DFS iterativo é mais verboso e te dá controle sobre o limite e sobre a ordem exata.
• BFS troca memória por proximidade: acha o mais perto primeiro, gastando O(largura).
• Escolher a travessia errada não deixa o código lento, deixa errado — pós-ordem onde se precisava de pré produz resultado inválido, não devagar.

Em Go:

• Iterador com range-sobre-função (1.23+) compra composição com break e cobra a propagação manual do bool de parada.
• Callback func(T) é mais simples e não consegue parar no meio.
• Recursão custa frames; a stack de 1 GB torna isso um não-problema para árvores balanceadas e um problema real para degeneradas.

Exemplo prático

package main

import "fmt"

type No struct {
	Val      int
	Esq, Dir *No
}

func pre(n *No, out *[]int) {
	if n == nil { return }
	*out = append(*out, n.Val) // <- visita ANTES
	pre(n.Esq, out)
	pre(n.Dir, out)
}

func in(n *No, out *[]int) {
	if n == nil { return }
	in(n.Esq, out)
	*out = append(*out, n.Val) // <- visita NO MEIO
	in(n.Dir, out)
}

func pos(n *No, out *[]int) {
	if n == nil { return }
	pos(n.Esq, out)
	pos(n.Dir, out)
	*out = append(*out, n.Val) // <- visita DEPOIS
}

// BFS: fila, e o truque dos niveis
func niveis(n *No) [][]int {
	if n == nil { return nil }
	var out [][]int
	fila := []*No{n}
	for len(fila) > 0 {
		tam := len(fila) // <- tamanho do nivel ATUAL, capturado antes
		nivel := make([]int, 0, tam)
		for i := 0; i < tam; i++ {
			no := fila[0]
			fila = fila[1:]
			nivel = append(nivel, no.Val)
			if no.Esq != nil { fila = append(fila, no.Esq) }
			if no.Dir != nil { fila = append(fila, no.Dir) }
		}
		out = append(out, nivel)
	}
	return out
}

// Iterador Go 1.23+: composavel com break
func ordenado(n *No) func(func(int) bool) {
	return func(yield func(int) bool) { percorre(n, yield) }
}

func percorre(n *No, yield func(int) bool) bool {
	if n == nil { return true }
	if !percorre(n.Esq, yield) { return false }
	if !yield(n.Val) { return false } // consumidor deu break: propaga
	return percorre(n.Dir, yield)
}

// Pos-ordem resolvendo algo real: avaliar arvore de expressao
type Exp struct {
	Op          byte // 0 = folha
	Val         int
	Esq, Dir    *Exp
}

func avalia(e *Exp) int {
	if e.Op == 0 { return e.Val }
	a, b := avalia(e.Esq), avalia(e.Dir) // filhos PRIMEIRO
	switch e.Op {
	case '+': return a + b
	case '*': return a * b
	}
	return 0
}

func main() {
	t := &No{4,
		&No{2, &No{Val: 1}, &No{Val: 3}},
		&No{6, &No{Val: 5}, &No{Val: 7}}}

	var a, b, c []int
	pre(t, &a); in(t, &b); pos(t, &c)
	fmt.Println("pré: ", a)
	fmt.Println("in:  ", b, "<- ordenado, porque é BST")
	fmt.Println("pós: ", c)
	fmt.Println("níveis:", niveis(t))

	// break funciona de verdade no iterador
	fmt.Print("primeiros <= 4: ")
	for v := range ordenado(t) {
		if v > 4 { break }
		fmt.Print(v, " ")
	}
	fmt.Println()

	// (2+3)*4 avaliado em pós-ordem
	exp := &Exp{Op: '*',
		Esq: &Exp{Op: '+', Esq: &Exp{Val: 2}, Dir: &Exp{Val: 3}},
		Dir: &Exp{Val: 4}}
	fmt.Println("(2+3)*4 =", avalia(exp))
}

Relacionado

• 2. Árvore de Busca Binária — o invariante que faz in-order funcionar
• 4. Pilha e 5. Fila — semana 2, DFS é pilha, BFS é fila
• 4. Grafos — as mesmas travessias, agora com ciclos
• 5. Recursão — a estrutura recursiva do dado virando código

---

Parte de Semana 03 - Estruturas de Dados II e Recursão · 00 - MOC Fundamentos de Programação