Explique o mecanismo de busca de um elemento numa árvore binária e como é realizado o seu percurso

Numa árvore binária de pesquisa (BST), a busca de um elemento ocorre da seguinte forma:

1. Começamos pela raiz da árvore.
2. Comparamos o valor procurado com o nó atual:
   • Se o valor for igual, o elemento foi encontrado.
   • Se o valor for menor, passamos para o subárvore esquerdo.
   • Se o valor for maior, passamos para o subárvore direito.
3. Repetimos o processo até encontrar o elemento ou atingir um nó vazio (elemento ausente).

A travessia de uma árvore binária é uma forma de visitar todos os nós sequencialmente. Os principais tipos de travessia são:

• In-order (simétrico): subárvore esquerdo → nó → subárvore direito. Permite obter os elementos em ordem ordenada.
• Pre-order (pré-ordem): nó → subárvore esquerdo → subárvore direito.
• Post-order (pós-ordem): subárvore esquerdo → subárvore direito → nó.

Exemplo de busca e travessia em Go:

package main
import "fmt"

type Node struct {
    Value int
    Left, Right *Node
}

func (n *Node) Search(val int) *Node {
    if n == nil || n.Value == val {
        return n
    }
    if val < n.Value {
        return n.Left.Search(val)
    }
    return n.Right.Search(val)
}

func (n *Node) InOrder() {
    if n == nil {
        return
    }
    n.Left.InOrder()
    fmt.Print(n.Value, " ")
    n.Right.InOrder()
}

func main() {
    root := &Node{Value: 10}
    root.Left = &Node{Value: 5}
    root.Right = &Node{Value: 15}

    node := root.Search(5)
    if node != nil {
        fmt.Println("Nó encontrado com valor:", node.Value)
    } else {
        fmt.Println("Elemento não encontrado")
    }

    fmt.Print("Travessia in-order: ")
    root.InOrder() // Vai imprimir: 5 10 15
}