Ordens de percursos em árvores binárias

Fala, meus consagrados! Beleza?

Uma das operações mais cruciais em árvores binárias é o percurso dos seus nós, onde cada nó é visitado numa sequência específica. Este artigo explora as três principais ordens de percurso em árvores binárias: pré-ordem, em-ordem e pós-ordem.

Esse assunto é uma fonte extensa de questões de concursos sobre a estrutura de dados  árvore. Neste artigo, vamos falar um pouco sobre essas ordens e ter um material excelente para revisão. Venham comigo!

Nas árvores binárias, existem três formas principais de percorrer uma árvore binária, o que significa visitar todos os seus nós em uma ordem específica, o que são chamadas de ordens de percursos.

Estes métodos de percurso são fundamentais para muitas operações em árvores binárias, incluindo busca, inserção e remoção de nós. Cada estratégia de percurso tem suas aplicações específicas dependendo da operação que você deseja realizar e da estrutura da árvore.

As ordens de percursos para árvores binárias são:

• Pré-ordem;
• Em-ordem; e
• Pós-ordem.

Figura 1: Ordens de percurso em uma árvore binária.

Pré-ordem

O percurso em pré-ordem é talvez o mais intuitivo dos três.

Nesta abordagem, cada nó é processado antes de seus subnós. Isso significa que, ao visitar um nó, primeiro processamos a informação contida nele, e só depois prosseguimos para explorar sua subárvore da esquerda, seguido pela sua subárvore da direita.

Esta ordem de percurso é particularmente útil em cenários onde precisamos replicar ou examinar a estrutura da árvore antes de considerar seus elementos internos, como na clonagem de árvores ou na implementação de algoritmos de busca.

Revisão da ordem de percurso pré-ordem:

• Raiz-esquerda-direita;
• Visita-se primeiro a raiz;
• Em seguida, percorre a subárvore da esquerda em pré-ordem; e
• Por último, percorre a subárvore da direita em pré-ordem;

Em-ordem

O percurso em-ordem é exclusivo das árvores binárias de busca (BST – Binary Search Trees), onde a árvore é organizada de tal forma que, para cada nó, todos os elementos à esquerda são menores e todos os elementos à direita são maiores.

Nesta ordem de percurso, visitamos primeiro a subárvore esquerda, depois o nó atual, e finalmente a subárvore da direita.

O resultado é uma visita aos nós da árvore em uma sequência ascendente, o que faz do percurso em-ordem a escolha ideal para:

• Operações de ordenação; e
• Obtenção de uma visão sequencial dos elementos contidos na árvore.

Revisão da ordem de percurso em-ordem:

• Esquerda-raiz-direita;
• Percorre primeiro a subárvore da esquerda em em-ordem;
• Em seguida, visita-se a raiz; e
• Por último, percorre a subárvore da direita em em-ordem;

Pós-ordem

Por último, no percurso em pós-ordem, um nó é visitado após todos os seus subnós terem sido processados.

Isso significa que primeiro exploramos a subárvore da esquerda, depois a subárvore da direita, e só então o nó atual.

Esta ordem é particularmente útil para operações que dependem de informações agregadas dos subnós antes de poder processar o nó pai, como o cálculo de profundidade ou a liberação de memória alocada para a árvore, visto que garante que todos os recursos dos filhos sejam devidamente liberados ou computados antes de lidar com o pai.

Revisão da ordem de percurso pós-ordem:

• Esquerda-direita-raiz;
• Percorre primeiro a subárvore da esquerda em pós-ordem;
• Em seguida, percorre a subárvore da direita em pós-ordem; e
• Por último, visita-se a raiz.

Figura 2: Dicas para as ordens de percurso em uma árvore binária.

Vamos colocar em prática o que estudamos? Considere então a seguinte árvore binária:

Aplicando as ordens de percurso nessa árvore binária, temos:

• Pré-ordem: 42 16 8 5 11 35 57 48;
• Em-ordem: 5 8 11 16 35 42 48 57; e
• Pós-ordem: 5 11 8 35 16 48 57 42.

Agora, pratiquem essas ordens fazendo questões de concursos. Vocês verão que com a prática, conseguirão pegar o padrão de cada ordem e vão matar diversas questões de concursos. E bem complexas, o que farão vocês saírem na frente!

Espero que tenham gostado! 

Forte abraço e até a próxima jornada!

_________________________

Professor Rogerão Araújo