Tree Traversal

author
6 minutes, 7 seconds Read

Unlike linked lists, one-dimensional arrays and other linear data structures, which are canonically traversed in linear order, trees may be traversed in multiple ways. Elas podem ser atravessadas em ordem de profundidade-primeira ou largura-primeira. Existem três formas comuns de atravessá-las em ordem de profundidade-primeira ordem: em ordem, pré-ordem e pós-ordem. Para além destas travessias básicas, são possíveis vários esquemas mais complexos ou híbridos, tais como buscas de profundidade limitada, como a busca iterativa de aprofundamento em ordem de profundidade. Esta última, assim como a busca de profundidade-primeira, também pode ser usada para atravessar árvores infinitas, veja abaixo.

Estruturas de dados para a travessia de árvoresEditar

Passar uma árvore envolve iteração sobre todos os nós de alguma forma. Como a partir de um determinado nó há mais de um possível nó seguinte (não é uma estrutura de dados linear), então, assumindo cálculo seqüencial (não paralelo), alguns nós devem ser armazenados de alguma forma para posterior visita. Isso geralmente é feito através de uma pilha (LIFO) ou fila (FIFO). Como uma árvore é uma estrutura de dados auto-referencial (recursivamente definida), a travessia pode ser definida por recursividade ou, mais sutilmente, por corecursividade, de forma muito natural e clara; nestes casos os nós diferidos são armazenados implicitamente na pilha de chamadas.

Profunde-primeira busca é facilmente implementada através de uma pilha, incluindo recursivamente (através da pilha de chamadas), enquanto que a busca de largura-primeiro é facilmente implementada através de uma fila, incluindo corecursivamente.:45-61

Pesquisa de profundidade-primeira busca de árvore bináriaEditar

Pesquisa de profundidade-primeira busca de árvore binária:

  • Pré-ordem (acesso do nó na posição vermelha ●):

    F, B, A, D, C, E, G, I, H;

  • Em ordem (acesso do nó na posição verde ●):

    A, B, C, D, D, E, F, G, H, I;

  • Pós-ordem (acesso do nó na posição azul ●):

    A, C, E, D, B, H, I, G, F.

Estas buscas são referidas como busca de profundidade-primeira busca (DFS), uma vez que a árvore de busca é aprofundada o máximo possível em cada criança antes de ir para o próximo irmão. Para uma árvore binária, elas são definidas como operações de acesso em cada nó, começando com o nó atual, cujo algoritmo é o seguinte:

O padrão geral recursivo para atravessar uma árvore binária é este:

  1. Vá para baixo um nível até o argumento recursivo N. Se N existir (não está vazio) execute as três operações seguintes em uma determinada ordem: L: Atravessar recursivamente a sub-árvore esquerda de N. R: Atravessar recursivamente a sub-árvore direita de N. N: Acessar (visitar) o próprio nó N atual.
  2. Retroceder subindo um nível e chegando ao nó pai de N.

Existem três métodos (padrões) em que posição das parcelas (travessias) em relação ao nó (na figura: vermelho, verde ou azul) deve ocorrer a visita (acesso) do nó. A escolha de exatamente uma cor determina exatamente uma visita de um nó, como descrito abaixo. O acesso em todas as três cores resulta em uma visita tripla do mesmo nó, produzindo a sequenciação de “toda ordem”:

F-B-A-A-A-B-D-C-C-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F

Pré-ordem, NLREdit

  1. Acesso à parte de dados do nó atual (na figura: posição vermelha).
  2. Passar a sub-árvore esquerda chamando recursivamente a função de pré-encomenda.
  3. Passar a sub-árvore direita chamando recursivamente a função de pré-encomenda.

Atravessar a sub-árvore de pré-ordem é uma classificação topológica, porque um nó pai é processado antes que qualquer um dos seus nós filhos seja feito.

Na ordem, LNREdit

  1. Passar a sub-árvore esquerda chamando recursivamente a função de pré-ordem.
  2. Acesso à parte de dados do nó atual (na figura: posição verde).
  3. Passar a sub-árvore direita chamando recursivamente a função dentro da ordem.

Em uma árvore de busca binária ordenada de forma que em cada nó a chave seja maior que todas as chaves em sua sub-árvore esquerda e menor que todas as chaves em sua sub-árvore direita, a travessia da ordem recupera as chaves em ordem ascendente ordenada.

Inverter em ordem, RNLEdit

  1. Passar a sub-árvore direita chamando recursivamente a função inverter em ordem.
  2. Acesso à parte de dados do nó atual.
  3. Passar a sub-árvore esquerda chamando recursivamente a função inverter em ordem.

Em uma árvore de busca binária, a travessia inversa da ordem recupera as chaves em ordem decrescente.

Pós-ordem, LRNEdit

  1. Volta a sub-árvore esquerda chamando recursivamente a função de pós-ordem.
  2. Passar a sub-árvore direita chamando recursivamente a função de pós-ordem.
  3. Acesso à parte de dados do nó actual (na figura: posição azul).

O traço de uma travessia é chamado de sequenciação da árvore. O traço de uma travessia é uma lista de cada nó visitado. Nenhuma sequenciação de acordo com pré-, in- ou post-order descreve a árvore subjacente de forma única. Dada uma árvore com elementos distintos, tanto a pré-ordem como a pós-ordem emparelhada com a in-order é suficiente para descrever a árvore de forma única. No entanto, a pré-ordem com pós-ordem deixa alguma ambiguidade na estrutura da árvore.

Árvore genéricaEditar

Para atravessar qualquer árvore com pesquisa de profundidade-primeiro lugar, execute as seguintes operações em cada nó:

  1. Se o nó não apresentar retorno.
  2. Acesso (= visita) ao nó (posição de pré-encomenda).
  3. Para cada i de 1 ao número_de_crianças – 1 do:
    1. Passar recursivamente o i-ésimo filho.
    2. Nó de acesso (posição dentro da ordem).
  4. Ponto de passagem do último filho.
  5. Nó de acesso (posição após a ordem).

Dependente do problema em questão, a pré-ordem, a pós-ordem, e especialmente uma das (número_de_filhos – 1) operações na ordem pode ser nula, ou o acesso apenas a um filho específico é desejado, portanto estas operações são opcionais. Além disso, na prática, mais do que uma das operações de pré-encomenda, encomenda e pós-encomenda pode ser necessária. Por exemplo, ao inserir em uma árvore ternária, uma operação de pré-ordem é realizada através da comparação de itens. Uma operação pós-ordem pode ser necessária depois para re-equilibrar a árvore.

Busca por ordem de nível ou de nívelEditar

Level-order: F, B, G, A, D, I, C, E, H.

>

Artigo principal: Pesquisa por ordem de nível

As árvores também podem ser atravessadas em ordem de nível, onde visitamos cada nó de um nível antes de irmos para um nível inferior. Esta busca é referida como busca por ordem de largura (BFS), pois a árvore de busca é ampliada o máximo possível em cada profundidade antes de ir para a próxima profundidade.

Outros tiposEditar

Também existem algoritmos de atravessamento de árvore que não classificam como busca por ordem de largura nem como busca por ordem de largura. Um desses algoritmos é a busca em árvore Monte Carlo, que se concentra na análise dos movimentos mais promissores, baseando a expansão da árvore de busca na amostragem aleatória do espaço de busca.

Similar Posts

Deixe uma resposta

O seu endereço de email não será publicado.