Dato un albero binario, scrivi una soluzione iterativa e ricorsiva per attraversare l’albero usando inorder traversal in C++, Java, e Python.
A differenza delle liste collegate, degli array unidimensionali e di altre strutture di dati lineari, che sono attraversate in ordine lineare, gli alberi possono essere attraversati in più modi in ordine di profondità (preordine, inordine e postordine) o in ordine di ampiezza (attraversamento di livello). Oltre a queste traversate di base, sono possibili vari schemi più complessi o ibridi, come le ricerche limitate in profondità come la ricerca iterativa in profondità-prima. In questo post, l’inorder tree traversal viene discusso in dettaglio.
L’attraversamento di un albero comporta l’iterazione su tutti i nodi in qualche modo. Poiché l’albero non è una struttura dati lineare, ci può essere più di un possibile nodo successivo da un dato nodo, quindi alcuni nodi devono essere differiti, cioè memorizzati in qualche modo per una visita successiva. La traversata può essere fatta in modo iterativo, dove i nodi differiti sono memorizzati nello stack, o può essere fatta per ricorsione, dove i nodi differiti sono memorizzati implicitamente nello stack delle chiamate.
Per attraversare un albero binario (non vuoto) in modo ordinato, dobbiamo fare queste tre cose per ogni nodo n partendo dalla radice dell’albero:
(L) Traversare ricorsivamente il suo sottoalbero sinistro. Quando questo passo è finito, siamo di nuovo a n.(N) Elabora n stesso.(R) Percorre ricorsivamente il suo sottoalbero destro. Quando questo passo è finito, siamo di nuovo a n.Nel normale attraversamento dell’ordine, visitiamo il sottoalbero sinistro prima del sottoalbero destro. Se visitiamo il sottoalbero di destra prima di visitare il sottoalbero di sinistra, si parla di inversione dell’ordine.
Come possiamo vedere, prima di elaborare qualsiasi nodo, il sottoalbero di sinistra viene elaborato per primo, seguito dal nodo, e il sottoalbero di destra viene elaborato per ultimo. Queste operazioni possono essere definite ricorsivamente per ogni nodo. L’implementazione ricorsiva è chiamata ricerca di profondità (DFS), poiché l’albero di ricerca viene approfondito il più possibile su ogni figlio prima di passare al fratello successivo.
Di seguito il programma C++, Java e Python che lo dimostra:
Implementazione iterativa –
Per convertire la procedura ricorsiva di cui sopra in una iterativa, abbiamo bisogno di uno stack esplicito. Di seguito è riportato un semplice algoritmo iterativo basato sullo stack per eseguire l’inorder traversal.
iterativoInorder(nodo)
L’algoritmo può essere implementato come segue in C++, Java e Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// Iterativo funzione per eseguire la traversata in ordine sull’albero
void inorderIterative(Node *root)
{
// crea uno stack vuoto
stack<Node*> stack;
// inizia dal nodo radice (imposta il nodo corrente sul nodo radice)
Nodo *curr = radice;
// se il nodo corrente è nullo e anche lo stack è vuoto, abbiamo finito
while (!stack.empty() || curr != nullptr)
{
// se il nodo corrente esiste, spingilo nello stack (rinvialo)
// e passa al suo figlio sinistro
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else
{
// altrimenti, se il nodo corrente è nullo, pop un elemento dallo stack,
// stamparlo, e infine impostare il nodo corrente al suo figlio destro
curr = stack.top();
stack.pop();
cout << curr->data << ” “;
curr = curr->right;
}
}
}
|
Scarica il codice completo
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// Iterativo per eseguire la traversata in ordine sull’albero
public static void inorderIterative(TreeNode root)
{
// creare uno stack vuoto
Stack<TreeNode> stack = new Stack();
// inizia dal nodo radice (imposta il nodo corrente sul nodo radice)
TreeNode curr = root;
// se il nodo corrente è nullo e anche lo stack è vuoto, abbiamo finito
while (!stack.empty() || curr != null)
{
// se il nodo corrente esiste, spingerlo nello stack (rinviarlo)
// e passare al suo figlio sinistro
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
else
{
// altrimenti, se il nodo corrente è nullo, pop un elemento dallo stack,
// stamparlo, e infine impostare il nodo corrente al suo figlio destro
curr = stack.pop();
System.out.print(curr.data + ” “);
curr = curr.right;
}
}
}
|
Scarica il codice completo
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Funzione iterativa per eseguire la traversata in ordine sull’albero
def inorderIterative(root):
# crea uno stack vuoto
stack = deque()
# inizia dal nodo radice (imposta il nodo corrente sul nodo radice)
curr = radice
# se il nodo corrente è None e lo stack è anche vuoto, abbiamo finito
while stack o curr:
# se il nodo corrente esiste, spingerlo nello stack (rinviarlo)
# e passare al suo figlio sinistro
if curr:
stack.append(curr)
curr = curr.left
else:
# altrimenti, se il nodo corrente è None, pop un elemento dallo stack,
# stamparlo, e infine impostare il nodo corrente al suo figlio destro
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.right
|
Download Run Complete Code
La complessità temporale delle soluzioni di cui sopra è O(n), dove n è il numero totale di nodi dell’albero binario. La complessità spaziale del programma è O(n) poiché lo spazio richiesto è proporzionale all’altezza dell’albero, che può essere uguale al numero totale di nodi dell’albero nel caso peggiore per alberi obliqui.