© NicoElNino/Shutterstock.com
Na ciência da computação, os dados podem ser estruturados e percorridos de várias maneiras. As árvores binárias são uma forma de armazenamento hierárquico de dados que usa percursos de árvore como o método principal de visitar todos os nós constituintes para pesquisa, classificação e outros propósitos. Compreender os vários métodos usados para percursos de árvore pode ajudá-lo a concluir as operações básicas em uma árvore binária. Neste artigo, explicamos o que são percursos de árvore, incluindo percursos em ordem, pré-ordem e pós-ordem, com exemplos para ajudá-lo a começar.
O que são percursos de árvore?
Passeios de árvore são os métodos que cientistas da computação, desenvolvedores e engenheiros de software usam para percorrer uma árvore binária. Também é conhecido como:
Percorrendo a árvore Pesquisa em árvore
Esses métodos envolvem a visita sequencial de cada nó dentro da árvore binária. Em contraste com uma estrutura de dados linear como uma lista encadeada ou fila, essas travessias podem ser concluídas de várias maneiras. Os principais métodos, explicados abaixo, são usados para atualizar, excluir, pesquisar, classificar e recuperar dados com eficiência.
Sobre árvores binárias
Árvores binárias são a forma de árvore mais comumente usada, que é uma estrutura de dados hierárquica composta de nós interconectados. Cada nó consiste em referências à esquerda e à direita e um elemento de dados. Cada nó em uma árvore binária está conectado a um pai, mas cada nó pai pode ter no máximo 2 filhos. Nós sem filhos são chamados de folhas. Os nós que compartilham um nó pai são chamados de irmãos. O nó no topo de uma árvore binária é chamado de raiz.
Se uma árvore binária estiver completamente preenchida, ela é chamada de árvore completa. As árvores são preenchidas com nós da esquerda para a direita. Você pode posicionar os nós por sua altura, que é o número de arestas entre a raiz e o nó de índice, ou sua profundidade, que é o número de arestas entre o nó e o nó folha mais distante.
Usar percursos de árvore para visitar todos os nós em uma árvore
Uma característica importante desses percursos é que todos os nós da árvore são visitados. Como as árvores são estruturas de dados não lineares, há muitas maneiras e ordens nas quais você pode garantir que cada nó seja visitado por vez. Não há uma travessia única, mas vários algoritmos de travessia com os quais você pode trabalhar.
Tree Traversals são importantes
Dominar as tree traversals é uma habilidade fundamental para organizar e trabalhar com dados. Isso ocorre porque as árvores são uma estrutura de dados extremamente comum e são amplamente utilizadas por causa de sua representação clara de relacionamentos e hierarquias de dados.
Você pode usar esses métodos de passagem e exemplos para pesquisas ou inserções de dados mais eficientes. Vamos dar uma olhada nos principais métodos abaixo:
Aqui está um exemplo de árvore:
Uma ilustração de uma estrutura de árvore.
©”TNGD.com
1. Percurso de pré-ordem
Este é um tipo de percurso em profundidade em que o nó pai é visitado primeiro, depois o nó filho esquerdo e, por fim, o nó filho direito. Se uma árvore é percorrida usando o método preOrder, o nó raiz é visitado primeiro, em seguida, as subárvores esquerda e direita seqüenciais primeiro até que toda a árvore seja percorrida. A passagem de pré-ordem fornece um método eficiente para copiar uma árvore.
Aqui está o exemplo de passagem de pré-ordem para a árvore acima: A > B > D > E > C > F > G
E aqui está o algoritmo de pré-encomenda:
Algoritmo para o PreOrder Traversal de uma estrutura em árvore.
©”TNGD”.com
2. Percurso InOrder
Este é um tipo de percurso em profundidade em que o nó filho esquerdo é visitado, depois o pai e, por fim, o nó filho direito. Traversals InOrder prosseguem através da subárvore mais à esquerda e terminam na subárvore mais à direita. Esse tipo de passagem produz dados organizados em ordem crescente.
Aqui está o exemplo de percurso inOrder para a árvore acima: D > B > E > A > F > C > G
E aqui está o algoritmo inOrder:
Algoritmo para inOrder Traversal de uma estrutura de árvore.
©”TNGD”.com
3. Passagem PostOrder
Este terceiro tipo de travessia em profundidade visita o nó filho esquerdo, depois o nó filho direito e depois o pai. Com a travessia da árvore postOrder, as subárvores são todas visitadas primeiro (a partir do canto inferior esquerdo) com a raiz visitada por último. Traversal PostOrder é uma maneira eficiente de excluir uma árvore.
Aqui está o exemplo de passagem postOrder para a árvore acima: D > E > B > F > G > C > A
E aqui está o algoritmo postOrder:
Algoritmo para PostOrder Traversal de uma estrutura em árvore.
©”TNGD.com
Há também uma travessia em largura que visita os nós de cima para baixo e da esquerda para a direita. Esta é a única forma de travessia em largura.
Arredondamento
Como você pode ver, travessias em árvore fazem o gerenciamento de dados hierárquicos muito simples. Os algoritmos são diretos e, se você se perder, pode desenhar uma árvore básica para se orientar. Esses métodos são tão eficientes que você pode construir árvores binárias completas a partir de percursos pré e pós-ordem fornecidos. Pratique esses métodos para dominá-los e ampliar seu conhecimento.
O que são percursos de árvore (em ordem, pré-ordem e pós-ordem) – com exemplos Perguntas frequentes (perguntas frequentes)
O que é uma estrutura de dados?
As estruturas de dados são os formatos específicos usados para organizar dados para que possam ser armazenados com segurança e gerenciados e acessados com eficiência.
Quais são os principais tipos de árvores?
Além das árvores binárias, os principais tipos de árvores incluem:
Árvores de pilha Árvores de sintaxe Tentativas Árvores B Árvores T
O que é uma árvore binária perfeita?
Uma árvore binária perfeita tem todos os nós de folha na mesma profundidade e todos os nós pais têm dois filhos. Essa é outra maneira de descrever uma árvore completamente preenchida e sem lacunas.
Quais são exemplos de estruturas de dados não-árvore?
Estruturas de dados não-árvore são principalmente estruturas de dados lineares que incluem:
Arrays A bitmap Matriz Matriz paralela Lista duplamente vinculada Lista auto-organizada
O que são tipos de dados abstratos?
Tipos de dados abstratos (ADT) são modelos matemáticos que podem ser usados para estruturar dados e facilitar a programação em larga escala. Na ciência da computação, os ADTs podem ser usados para empacotar e gerenciar dados para uma variedade de aplicativos de computação.