Estrutura de dados e algoritmos - árvore transversal

Traversal é um processo para visitar todos os nós de uma árvore e pode imprimir seus valores também. Porque, todos os nós são conectados por meio de arestas (links), sempre começamos a partir do nó raiz (cabeça). Ou seja, não podemos acessar aleatoriamente um nó em uma árvore. Existem três maneiras que usamos para atravessar uma árvore -

• Transversal em ordem
• Pré-encomendar Traversal
• Traversal pós-pedido

Geralmente, atravessamos uma árvore para pesquisar ou localizar um determinado item ou chave na árvore ou para imprimir todos os valores que ela contém.

Transversal em ordem

Neste método transversal, a subárvore esquerda é visitada primeiro, então a raiz e depois a subárvore direita. Devemos sempre lembrar que cada nó pode representar uma subárvore em si.

Se uma árvore binária for percorrida in-order, a saída produzirá valores-chave classificados em ordem crescente.

Nós começamos de A, e seguindo a travessia em ordem, nos movemos para sua subárvore esquerda B. Btambém é percorrido em ordem. O processo continua até que todos os nós sejam visitados. A saída da travessia em ordem desta árvore será -

D → B → E → A → F → C → G

Algoritmo

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pré-encomendar Traversal

Nesse método de passagem, o nó raiz é visitado primeiro, depois a subárvore esquerda e, finalmente, a subárvore direita.

Nós começamos de Ae, após a travessia da pré-encomenda, visitamos primeiro A e, em seguida, mova para sua subárvore esquerda B. Btambém é percorrido na pré-encomenda. O processo continua até que todos os nós sejam visitados. O resultado da passagem de pré-encomenda desta árvore será -

A → B → D → E → C → F → G

Algoritmo

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Traversal pós-pedido

Nesse método de passagem, o nó raiz é visitado por último, daí o nome. Primeiro, percorremos a subárvore esquerda, depois a subárvore direita e, finalmente, o nó raiz.

Nós começamos de Ae, após a travessia de pós-pedido, primeiro visitamos a subárvore esquerda B. Btambém é percorrido pós-pedido. O processo continua até que todos os nós sejam visitados. A saída da travessia pós-pedido desta árvore será -

D → E → B → F → G → C → A

Algoritmo

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Para verificar a implementação de travessia de árvore em C, clique aqui .