Como funciona a pesquisa na árvore?

A procura numa árvore depende da sua estrutura e do objetivo da procura.

Principais métodos de procura:

Procura em profundidade (DFS - Depth-First Search): Vai o mais fundo possível numa rama antes de passar para a seguinte. Implementa-se usando uma pilha (explícita ou implicitamente via recursão).
- Percurso pré-ordem: Visitar a raiz, depois o subárvore esquerdo, depois o subárvore direito.
- Percurso em ordem (In-order): Visitar o subárvore esquerdo, depois a raiz, depois o subárvore direito. Usado em árvores binárias de procura para obter uma lista ordenada de elementos.
- Percurso pós-ordem: Visitar o subárvore esquerdo, depois o direito, depois a raiz.
Procura em largura (BFS - Breadth-First Search): Explora todos os vizinhos do nó atual num nível antes de passar ao próximo nível. Implementa-se usando uma fila.

Exemplo de DFS (In-order) para uma árvore binária:

// TreeNode representa um nó de árvore binária
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal realiza uma travessia inorder
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Chamada recursiva para o subárvore esquerdo
	result = append(result, InOrderTraversal(root.Left)...)
	// Visitar o nó atual
	result = append(result, root.Val)
	// Chamada recursiva para o subárvore direito
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Exemplo BFS:

// TreeNode representa um nó de árvore binária
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal realiza uma travessia BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Fila para armazenar os nós no nível atual
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Extrair o primeiro elemento da fila
		node := queue[0]
		queue = queue[1:]

		// Adicionar o valor do nó aos resultados
		result = append(result, node.Val)

		// Adicionar o filho esquerdo à fila se existir
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Adicionar o filho direito à fila se existir
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Para árvores binárias de procura (BST), onde o subárvore esquerdo é menor que a raiz e o direito é maior:

Procura binária: Ao procurar um valor específico, compara-se com a raiz. Se o valor for menor, procura-se no subárvore esquerdo; se for maior, procura-se no direito. Esta é a estratégia mais eficiente para procurar em BST.

// TreeNode representa um nó de árvore binária de procura
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST realiza uma procura binária em um BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Nó encontrado ou árvore vazia
	}

	if target < root.Val {
		// Procurar no subárvore esquerdo
		return SearchBST(root.Left, target)
	}
	// Procurar no subárvore direito
	return SearchBST(root.Right, target)
}

A escolha do algoritmo de procura depende da tarefa e das características da árvore. DFS é adequado para tarefas onde é necessário percorrer profundamente uma rama ou encontrar um caminho para o objetivo. BFS é adequado para encontrar o caminho mais curto ou percorrer por níveis. A procura binária é eficiente para encontrar um valor específico em estruturas ordenadas, como BST.