O percurso de uma árvore binária é uma operação fundamental que envolve visitar cada nó da árvore exatamente uma vez. Existem três ordens principais de percurso: pré-ordem, in-ordem e pós-ordem. Cada método define uma sequência específica para processar o nó raiz, o subárvore esquerdo e o subárvore direito.
Para todas as implementações, utilizaremos a seguinte estrutura de nó de árvore em Golang:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
Percursos Recursivos
A natureza recursiva das árvores binárias torna a recursão uma abordagem natural e elegante para a implementação de percursos. Cada tipo de percurso pode ser conceituado em três etapas básicas que se aplicam a cada nó:
- Processar o nó atual (Raiz).
- Percursar a subárvore esquerda.
- Percursar a subárvore direita.
A ordem em que essas etapas são executadas define o tipo de percurso.
Percurso em Pré-ordem (Raiz, Esquerda, Direita)
Neste percurso, o nó raiz é processado primeiro, seguido por uma chamada recursiva para o subárvore esquerdo e, finalmente, para o subárvore direito. Isso garante que o nó pai seja visitado antes de seus filhos.
func PreOrderTraversal(root *TreeNode) []int {
var resultSlice []int
var visit func(*TreeNode)
visit = func(node *TreeNode) {
if node == nil {
return
}
resultSlice = append(resultSlice, node.Val) // 1. Visita o nó atual (Raiz)
visit(node.Left) // 2. Percursa a subárvore esquerda
visit(node.Right) // 3. Percursa a subárvore direita
}
visit(root)
return resultSlice
}
Percurso em In-ordem (Esquerda, Raiz, Direita)
O percurso em in-ordem processa a subárvore esquerda, depois o nó raiz e, por último, a subárvore direita. Para uma Árvore de Busca Binária (BST), este percurso é notável por retornar os valores dos nós em ordem crescente.
func InOrderTraversal(root *TreeNode) []int {
var resultSlice []int
var visit func(*TreeNode)
visit = func(node *TreeNode) {
if node == nil {
return
}
visit(node.Left) // 1. Percursa a subárvore esquerda
resultSlice = append(resultSlice, node.Val) // 2. Visita o nó atual (Raiz)
visit(node.Right) // 3. Percursa a subárvore direita
}
visit(root)
return resultSlice
}
Percurso em Pós-ordem (Esquerda, Direita, Raiz)
No percurso em pós-ordem, a subárvore esquerda é processada primeiro, seguida pela subárvore direita e, por fim, o nó raiz. Este método é frequentemente utilizado em operações como a deleção de nós de uma árvore, pois garante que os filhos sejam tratados antes do pai.
func PostOrderTraversal(root *TreeNode) []int {
var resultSlice []int
var visit func(*TreeNode)
visit = func(node *TreeNode) {
if node == nil {
return
}
visit(node.Left) // 1. Percursa a subárvore esquerda
visit(node.Right) // 2. Percursa a subárvore direita
resultSlice = append(resultSlice, node.Val) // 3. Visita o nó atual (Raiz)
}
visit(root)
return resultSlice
}
Percursos Iterativos (Não Recursivos)
Embora a recursão seja intuitiva para árvores, ela pode levar a estouro de pilha para árvores muito proufndas ou ser menos eficiente em alguns contextos. Os percursos iterativos utilizam uma estrutura de dados de pilha explícita para simular o comportamento da recursão, evitando essas limitações.
Percurso em Pré-ordem Iterativo
Para um percurso em pré-ordem iterativo, uma pilha é utilizada para gerenciar os nós. A abordagem é: empilhar o nó raiz, e enquanto a pilha não estiver vazia, desempilhar um nó, adicionar seu valor ao resultado, e então empilhar seu filho direito (se existir) e depois seu filho esquerdo (se existir). Essa ordem de empilhamento (direito antes do esquerdo) garante que o filho esquerdo seja processado antes do direito ao ser desempilhado, seguindo a lógica Raiz-Esquerda-Direita.
func PreOrderIterative(root *TreeNode) []int {
var traversalResult []int
if root == nil {
return traversalResult
}
var nodeStack []*TreeNode
nodeStack = append(nodeStack, root) // Inicializa a pilha com a raiz
for len(nodeStack) > 0 {
// Desempilha o nó atual
currentNode := nodeStack[len(nodeStack)-1]
nodeStack = nodeStack[:len(nodeStack)-1]
traversalResult = append(traversalResult, currentNode.Val) // Adiciona ao resultado (Raiz)
// Empilha o filho direito primeiro, depois o esquerdo.
// Assim, o esquerdo estará no topo e será processado antes do direito.
if currentNode.Right != nil {
nodeStack = append(nodeStack, currentNode.Right)
}
if currentNode.Left != nil {
nodeStack = append(nodeStack, currentNode.Left)
}
}
return traversalResult
}
Percurso em In-ordem Iterativo
O percurso em in-ordem iterativo é um pouco mais elaborado. Ele envolve empilhar todos os nós esquerdos de um caminho até que um nó nulo seja alcançado. Em seguida, um nó é desempilhado, processado e, então, a lógica se move para sua subárvore direita.
func InOrderIterative(root *TreeNode) []int {
var traversalResult []int
var nodeStack []*TreeNode
currentNode := root
for currentNode != nil || len(nodeStack) > 0 {
// Percorre para o nó mais à esquerda, empilhando todos os nós no caminho
for currentNode != nil {
nodeStack = append(nodeStack, currentNode)
currentNode = currentNode.Left
}
// Desempilha o nó mais à esquerda não visitado (que agora está no topo da pilha)
currentNode = nodeStack[len(nodeStack)-1]
nodeStack = nodeStack[:len(nodeStack)-1]
traversalResult = append(traversalResult, currentNode.Val) // Adiciona ao resultado (Raiz)
// Move para a subárvore direita para o próximo ciclo
currentNode = currentNode.Right
}
return traversalResult
}
Percurso em Pós-ordem Iterativo
O percurso em pós-ordem iterativo é frequentemente considerado o mais complexo das três abordagens iterativas. Uma estratégia comum envolve o uso de uma pilha e um ponteior para o nó que foi visitado mais recentemente (lastVisited). Um nó só pode ser processado (adicionado ao resultado) se for uma folha ou se ambos os seus filhos já foram visitados e processados.
func PostOrderIterative(root *TreeNode) []int {
var traversalResult []int
if root == nil {
return traversalResult
}
var nodeStack []*TreeNode
nodeStack = append(nodeStack, root) // Começa empilhando a raiz
var lastVisited *TreeNode // Rastreia o último nó que foi adicionado ao resultado
for len(nodeStack) > 0 {
topNode := nodeStack[len(nodeStack)-1] // Espia o nó do topo da pilha
// Condição para processar o nó:
// 1. É um nó folha (não tem filhos), ou
// 2. O filho direito foi o último nó visitado (o que significa que a subárvore direita foi processada), ou
// 3. O filho esquerdo foi o último nó visitado E não há filho direito (o que significa que a subárvore esquerda foi processada e não há direita).
if (topNode.Left == nil && topNode.Right == nil) ||
(lastVisited != nil && (lastVisited == topNode.Right || (lastVisited == topNode.Left && topNode.Right == nil))) {
traversalResult = append(traversalResult, topNode.Val) // Adiciona ao resultado (Raiz)
nodeStack = nodeStack[:len(nodeStack)-1] // Desempilha
lastVisited = topNode // Atualiza o nó processado mais recentemente
} else {
// Se o nó atual não pode ser processado, empilha seus filhos (direito, depois esquerdo)
// para que o esquerdo seja explorado primeiro.
if topNode.Right != nil {
nodeStack = append(nodeStack, topNode.Right)
}
if topNode.Left != nil {
nodeStack = append(nodeStack, topNode.Left)
}
}
}
return traversalResult
}