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
- 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:
- 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.
- 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
- Acesso à parte de dados do nó atual (na figura: posição vermelha).
- Passar a sub-árvore esquerda chamando recursivamente a função de pré-encomenda.
- 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
- Passar a sub-árvore esquerda chamando recursivamente a função de pré-ordem.
- Acesso à parte de dados do nó atual (na figura: posição verde).
- 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
- Passar a sub-árvore direita chamando recursivamente a função inverter em ordem.
- Acesso à parte de dados do nó atual.
- 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
- Volta a sub-árvore esquerda chamando recursivamente a função de pós-ordem.
- Passar a sub-árvore direita chamando recursivamente a função de pós-ordem.
- 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ó:
- Se o nó não apresentar retorno.
- Acesso (= visita) ao nó (posição de pré-encomenda).
- Para cada i de 1 ao número_de_crianças – 1 do:
- Passar recursivamente o i-ésimo filho.
- Nó de acesso (posição dentro da ordem).
- Ponto de passagem do último filho.
- 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
>
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.