Olá pessoal, tudo bem? Neste artigo iremos aprender como fazer percursos em árvores binárias, ou seja, veremos os métodos utilizados para percorrer os seus nós. Este é o assunto mais cobrado pela Cesgranrio quando nos referimos à estrutura de dados Árvore.
Para termos uma ideia, das 37 questões da Cesgranrio sobre árvores, 12 delas foram sobre como percorrer os nós de uma árvore binária. Dessa forma, se cair alguma questão sobre árvores, é muito provável que seja algo sobre como percorrer os nós.
Este artigo está estruturado da seguinte forma:
O que é uma árvore binária?
Componentes Fundamentais
Propriedades Intrínsecas
Aplicações Práticas
Métodos para percursos em árvores binárias:
Percurso pré-ordem
Percurso em ordem (simétrico)
Percurso pós-ordem
Dicas importantes
O que é uma árvore binária?
Antes de partir para os percursos em árvores binárias, iremos apresentar alguns conceitos fundamentais para seu entendimento.
Uma árvore binária é uma estrutura de dados fundamental na ciência da computação, projetada para organizar dados de maneira hierárquica. Sua estrutura é composta por nós interligados, onde cada nó pode ter, no máximo, dois filhos: um filho à esquerda e outro à direita. A natureza binária dessa estrutura proporciona uma representação eficiente e organizada, frequentemente utilizada em algoritmos e sistemas computacionais.
Componentes Fundamentais
Nó Raiz: O ponto de partida de qualquer árvore binária é o nó raiz. Este nó não tem um nó pai e serve como o ponto de origem para todos os outros nós da árvore.
Nó Folha: Os nós folha, ou terminais, são os nós que não têm filhos. Eles representam as extremidades dos ramos da árvore, constituindo o final de um caminho específico.
Nós Internos: Nós que têm pelo menos um filho são chamados de nós internos. Estes constituem os pontos de bifurcação na árvore, representando decisões ou ramificações na estrutura.
Filhos e Pais: Cada nó pode ter, no máximo, dois filhos. O filho à esquerda e o filho à direita são distintos, permitindo que a árvore cresça de maneira organizada. Além disso, cada nó, exceto o nó raiz, tem um nó pai que o precede na hierarquia.
Propriedades Intrínsecas:
Níveis e Profundidade: O nível de um nó é a distância desse nó até o nó raiz, enquanto a profundidade é o número de arestas no caminho do nó raiz até o nó. Essas medidas fornecem informações sobre a posição relativa dos nós na árvore.
Altura: A altura de uma árvore binária é o comprimento do caminho mais longo da raiz até uma folha. Ela reflete a complexidade e a profundidade da árvore, sendo uma métrica importante na análise de desempenho de algoritmos que utilizam árvores binárias.
Aplicações Práticas
Árvores binárias são amplamente utilizadas em diversas áreas da ciência da computação, desde estruturas de dados até algoritmos de busca e ordenação. Sua natureza hierárquica e eficiente possibilita a implementação de algoritmos complexos, como árvores de expressões, árvores AVL para balanceamento, e a busca binária. O entendimento dessas estruturas é essencial para profissionais da área, proporcionando uma base sólida para o desenvolvimento e otimização de sistemas computacionais.
Percorrendo uma árvore binária
Métodos para percorrer uma árvore binária
Há três métodos utilizados para percorrer uma árvore binária:
Pré-ordem: No percurso pré-ordem, ou “pre order”, os nós são visitados na seguinte ordem: primeiro o nó pai, em seguida o filho esquerdo e, por último, o filho direito. Essa técnica é útil para criar uma cópia da árvore ou para realizar operações de pré-processamento antes de visitar os nós filhos.
Em ordem (Simétrico): No percurso em ordem, também conhecido como “in order”, a árvore é percorrida de forma que os nós sejam visitados na seguinte ordem: primeiro o filho esquerdo, depois o nó pai e, por fim, o filho direito. Essa técnica é comumente utilizada para obter os elementos de uma árvore binária de busca em ordem crescente.
Pós-ordem: O percurso pós-ordem, ou “post order”, envolve a visita aos nós na seguinte ordem: primeiro o filho esquerdo, depois o filho direito e, por último, o nó pai. Essa técnica é frequentemente empregada em cálculos que requerem informações dos nós filhos antes de processar o nó pai, como a avaliação de expressões aritméticas.
A dica pra entender rapidamente esses métodos de percursos em árvores binárias é seguir essas duas regras:
O nó filho da esquerda é sempre visitado antes que o da direita:
O nome do método se refere ao momento em que o nó pai é visitado, ou seja:
Pré-ordem: o pai é visitado antes dos filhos, ou seja, Pai-Esquerda-Direita;
Em ordem: o pai é visitado entre os filhos, ou seja, Esquerda-Pai-Direita;
Pós-ordem: o pai é visitado após os filhos, ou seja, Esquerda-Direita-Pai;
Exemplo
Para exemplo, iremos utilizar a seguinte árvore binária:
Pré-ordem (Pai – Esquerda – Direita):
Visitar o nó 5 (Nó pai): Começamos visitando o nó raiz, que é o nó 5.
Visitar o nó 3 (filho esquerdo do nó 5): Em seguida, movemos para o filho esquerdo do nó 5, que é o nó 3.
Visitar o nó 1 (filho esquerdo do nó 3): Continuamos descendo pela esquerda até o nó 1, que é o filho esquerdo do nó 3.
Visitar o nó 2 (filho direito do nó 1): Observe que o nó 1 não possui filho esquerdo. Assim, visitamos seu filho direito, que é o nó 2.
Visitar o nó 4 (filho direito do nó 3): Retornamos para o nó 3 e agora visitamos seu filho direito, que é o nó 4.
Visitar o nó 8 (filho direito do nó 5): Voltamos ao nó raiz e agora nos movemos para seu filho direito, que é o nó 8.
Visitar o nó 7 (filho esquerdo do nó 8): Descemos pela esquerda do nó 8, visitando o nó 7.
Vistar o nó 6 (filho esquerdo do nó 7): Continuamos descendo pela esquerda do nó 7, visitando seu filho esquerdo, o nó 6.
Visitar o nó 9 (filho direito do nó 8): Voltamos para o nó 7, e como este não possui filho direito, voltamos para o nó 8 e visitamos o seu filho direito, o nó 9.
Em ordem (Esquerda – Pai – Direita):
Visitar o nó 1 (filho esquerdo do nó 3): Começamos pelo nó mais à esquerda, que é o nó 1.
Visitar o nó 2 (filho direito do nó 1): Em seguida, visitamos seu filho direito, o nó 2.
Visitar o nó 3 (pai do nó 1): Visitamos, agora, o nó 3, que é pai do nó 1.
Visitar o nó 4 (filho direito do nó 3): Em seguida, visitamos o nó 4, que é filho direito do nó 3.
Visitar o nó 5 (nó raiz): Após visitar todo o lado esquerdo, visitamos o nó 5, que é a raiz e pai do nó 3.
Visitar o nó 6 (filho esquerdo do nó 7): Agora, vamos para o lado direito da árvore e visitamos o nó que está mais à esquerda, que é o nó 7.
Visitar o nó 7 (pai do nó 6): Visitamos o nó 7, que é o pai do nó 6.
Visitar o nó 8 (pai dos nós 7 e 9): Como o nó 7 não tem filho direito, visitamos seu pai, o nó 8.
Visitar o nó 9 (filho direito do nó 8): Por fim, visitamos o nó 9, que é o filho direito do nó 8.
Pós-ordem (Esquerda – Direita – Pai):
Visitar o nó 2 (filho direito do nó 1): No pós-ordem, os filhos são visitados antes do pai. Assim, pegamos o nó mais à esquerda (que é o nó 1) e visitamos primeiro seu filho direito, que é o nó 2.
Visitar o nó 1 (pai do nó 2 e filho esquerdo do nó 3): Após isso, visitamos o nó 1, que é pai do nó 2 e filho esquerdo do nó 3.
Visitar o nó 4 (filho direito do nó 3): Em seguida, visitamos o nó 4, que é filho esquerdo do nó 3.
Visitar o nó 3 (nó pai): Depois, visitamos o nó 3, pai dos nós 1 e 4, e filho esquerdo do nó 5.
Visitar o nó 6 (filho esquerdo do nó 7): Após isso, passamos para a sub-árvore da direita e visitamos o nó mais à esquerda, que é o nó 6, filho esquerdo do nó 7.
Visitar o nó 7 (pai do nó 6 e filho esquerdo do nó 8): Como o nó 7 não tem filho direito, o visitamos em seguida.
Visitar o nó 9 (filho direito do nó 8): Após isso, visitamos o nó 9, filho direito do nó 8.
Visitar o nó 8 (pai dos nós 7 e 9; e filho direito do nó raiz): Em seguida, visitamos o nó 8, filho direito do nó raiz.
Visitar o nó 5 (nó raiz): Por último, visitamos o nó 5, que é o nó raiz da árvore.
Algumas dicas importantes
Ordem de visita do nó raiz:
No percurso pré-ordem, o nó raiz é sempre o primeiro a ser visitado.
No percurso pós-ordem, o nó raiz é sempre o último a ser visitado.
Uma árvore binária pode ter apenas um nó. Neste caso, as sub-árvores da direita e da esquerda são vazias.
Em uma árvore binária de busca, o método “em ordem” visita os nós em ordem crescente.
Embora tenham conceitos diferentes, o nível e a profundidade de um nó tem valores iguais, ou seja, se um nó tem o nível 7, sua profundidade também é 7. O nível é a posição de um nó em relação ao nó raiz, já a profundidade é obtida pela quantidade de arestas de um nó até chegar ao nó raiz da árvore.
Conclusão
Bom concurseiro, concluímos por aqui este artigo. Nele, vimos os métodos utilizados para percursos em árvores binárias. Espero que você tenha compreendido o assunto aqui abordado e que seja útil para sua tão sonhada aprovação no concurso nacional unificado. Bons estudos!
