Struttura dei dati e algoritmi - Attraversamento dell'albero

L'attraversamento è un processo per visitare tutti i nodi di un albero e può anche stampare i loro valori. Poiché tutti i nodi sono collegati tramite bordi (collegamenti), iniziamo sempre dal nodo radice (testa). Cioè, non possiamo accedere in modo casuale a un nodo in un albero. Ci sono tre modi che usiamo per attraversare un albero:

• Attraversamento in ordine
• Preordina Traversal
• Post-order Traversal

In genere, attraversiamo un albero per cercare o individuare un determinato elemento o chiave nell'albero o per stampare tutti i valori in esso contenuti.

Attraversamento in ordine

In questo metodo di attraversamento, viene visitato prima il sottoalbero sinistro, quindi la radice e successivamente il sottoalbero destro. Dobbiamo sempre ricordare che ogni nodo può rappresentare una sottostruttura stessa.

Se viene attraversato un albero binario in-order, l'output produrrà valori chiave ordinati in ordine crescente.

Partiamo da Ae, seguendo l'attraversamento in ordine, ci spostiamo alla sua sottostruttura sinistra B. Bè anche attraversato in ordine. Il processo continua finché tutti i nodi non vengono visitati. L'output dell'attraversamento in ordine di questo albero sarà:

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.

Preordina Traversal

In questo metodo di attraversamento, viene visitato per primo il nodo radice, quindi la sottostruttura sinistra e infine la sottostruttura destra.

Partiamo da Ae dopo l'attraversamento del preordine, visitiamo prima A stesso e quindi spostarsi nella sua sottostruttura sinistra B. Bè anche attraversato il preordine. Il processo continua finché tutti i nodi non vengono visitati. L'output dell'attraversamento del preordine di questo albero sarà:

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.

Post-order Traversal

In questo metodo di attraversamento, il nodo radice viene visitato per ultimo, da cui il nome. Per prima cosa attraversiamo la sottostruttura sinistra, quindi la sottostruttura destra e infine il nodo radice.

Partiamo da Ae, dopo l'attraversamento post-ordine, visitiamo prima la sottostruttura di sinistra B. Bè anche attraversato post-ordine. Il processo continua finché tutti i nodi non vengono visitati. L'output dell'attraversamento post-ordine di questo albero sarà:

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.

Per verificare l'implementazione in C dell'attraversamento degli alberi, fare clic qui .