Apostilas em PDF – Ordens de percursos em árvores binárias

Baixe o material de estudo



baixar curso online

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:

Imagem em preto e branco de um relógio

Descrição gerada automaticamente com confiança média

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

Quer ficar por dentro dos concursos públicos abertos e previstos pelo Brasil?
clique nos links abaixo:

Concursos Abertos

Concursos 2024

Receba gratuitamente no seu celular as principais notícias do mundo dos concursos!
clique no link abaixo e inscreva-se gratuitamente:

Telegram

Fonte: Gran Cursos Online

Download disponível – Ordens de percursos em árvores binárias



Baixar video aula

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *