Métodos de travessia de árvores são técnicas usadas para visitar todos os nós de uma estrutura de dados de árvore sistematicamente. Compreender esses métodos é essencial para várias aplicações, como pesquisa, ordenação e avaliação de expressões. Este artigo compara os três métodos de travessia primários: pré-ordenação, ordem e pós-ordem, com cálculos práticos para ilustrar suas diferenças.

Pré-ordenar a Traversal

A pré- ordem de travessia visita o nó raiz primeiro, depois atravessa recursivamente a sub- árvore esquerda, seguida pela sub- árvore direita. Este método é útil para copiar árvores ou criar expressões prefixas.

Por exemplo, dada a árvore:

A
/
] B C
/
D E F

A sequência de travessia pré-ordem é: A, B, D, E, C, F.

Inordem Traversal

A ordem transversal visita a sub- árvore esquerda primeiro, depois o nó raiz, e finalmente a sub- árvore direita. Este método é comumente usado para árvores de pesquisa binárias para recuperar dados em ordem ordenada.

Usando a mesma árvore, a sequência de travessia é: D, B, E, A, C, F.

Traversal de Postord

A travessia de pós- ordem visita a subárvore esquerda, depois a subárvore direita, e finalmente o nó raiz. Esta abordagem é útil para remover árvores ou avaliar expressões postfix.

Para a árvore de exemplo, a sequência de travessia pós-ordem é: D, E, B, F, C, A.

Cálculos práticos

Considere a árvore:

1
/
] 2 3
/
] 4 5 6

Pré-encomenda de travessia: 1, 2, 4, 5, 3, 6

Inordem de travessia: 4, 2, 5, 1, 3, 6

Transversal de pós-ordem: 4, 5, 2, 6, 3, 1