Alberi binari
Indice
๐Definizione
Un albero binario รจ un albero in cui ogni nodo ha al massimo due figli, identificati come figlio sinistro e figlio destro.
Nota: Due alberi
Per esempio, i seguenti due alberi binari sono diversi:
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/AlberoBinario.png)
๐ Visita di un albero
Due strategie per analizzare (visitare) tutti i nodi di un albero:
| Visita in profonditร Depth-First Search (DFS) | Visita in ampiezza Breadth First Search (BFS) |
|---|---|
| Per visitare un albero, si visita ricorsivamente ognuno dei suoi sottoalberi | Ogni livello dellโalbero viene visitato, uno dopo lโaltro |
| Tre varianti: Pre-Order, In-Order, Post-Order | Level Order Traversal |
| Richiede uno stack | Richiede una queue |
Depth-First Search (DFS)
Visto che si visita ricorsivamente ognuno dei sottoalberi dell'albero, in base al momento in cui decidiamo di stampare il nodo, la visita si suddivide in 3 modi. Qualunque metodo si scelga, il costo di una visita di un albero contenente
- Time complexity:
(n รจ il numero di elementi) - Space complexity:
(h รจ l'altezza dell'albero)
Pre-Order Traversal
Nella visita in pre-order prima si stampa il nodo corrente, poi si visitano i figli. Nella visita in pre-order la radice รจ sempre il nodo visitato per primo.
void preOrder(TreeNode t) {
if (t != NULL) {
print(t);
preOrder(t.left);
preOrder(t.right);
}
}
Esempio
graph TD A((A)) B((B)) C((C)) D((D)) E((E)) F((F)) G((G)) A-->B A-->E B-->C B-->D E-->F E-->G
Sequenza: A B C D E F G
In-Order Traversal
Nella visita in in-order prima si stampa il ramo sinistro, poi il nodo corrente e infine il ramo destro. Quando eseguita in un albero binario di ricerca, la visita in in-order visita i nodi in ordine crescente (da qui il nome "in-order").
void inOrder(TreeNode t) {
if (t != NULL) {
inOrder(t.left);
print(t);
inOrder(t.right);
}
}
Esempio
graph TD A((A)) B((B)) C((C)) D((D)) E((E)) F((F)) G((G)) A-->B A-->E B-->C B-->D E-->F E-->G
Sequenza: C B D A F E G
Post-Order Traversal
Nella visita in post-order vengono visitati prima i figli, poi il nodo corrente. Nella visita in post-order la radice รจ sempre il nodo visitato per ultimo.
void postOrder(TreeNode t) {
if (t != NULL) {
postOrder(t.left);
postOrder(t.right);
print(t);
}
}
Esempio
graph TD A((A)) B((B)) C((C)) D((D)) E((E)) F((F)) G((G)) A-->B A-->E B-->C B-->D E-->F E-->G
Sequenza: C D B F G E A
Breadth First Search (BFS)
Partendo dalla radice si visitano tutti i nodi livello per livello. La visita รจ chiamata Level Order Traversal.
Possiamo implementarlo sia ricorsivamente sia iterativamente.
Level Order Traversal
Esempio
graph TD A((A)) B((B)) C((C)) D((D)) E((E)) F((F)) G((G)) A-->B A-->E B-->C B-->D E-->F E-->G
Sequenza: A B E C D F G
Implementazione ricorsiva
L'idea รจ la seguente:
- Usiamo un for che va da
a (l'altezza dell'albero) - Ad ogni iterazione, utilizziamo il Depth-First Search (DFS) per attraversare l'albero, mantenendoci l'altezza del nodo corrente.
- Se il nodo รจ nullo ->
return - Se il livello รจ
siamo arrivati al livello desiderato, quindi stampiamo tree->data - Se il livello รจ maggiore di
, allora - Ricorsivamente, visitiamo il figlio sinistro, decrementando il livello di
- Ricorsivamente, visitiamo il figlio destro, decrementando il livello di
- Ricorsivamente, visitiamo il figlio sinistro, decrementando il livello di
- Se il nodo รจ nullo ->
/* Function to print level order traversal a tree */
void levelOrderTraversal(Tree root)
{
int h = height(root);
for(int level = 1; level < h + 1; ++level)
printCurrentLevel(root, level);
}
/* Print nodes at a current level */
void printCurrentLevel(Tree root, int level)
{
if(root == NULL)
return;
else if(level == 1)
cout << root.data << " ";
else {
printCurrentLevel(root.left, level - 1);
printCurrentLevel(root.right, level - 1);
}
}
/* Compute the "height" of a tree -- the number of nodes along the longest path from the root node
down to the farthest leaf node. */
int height(Tree node)
{
if (node == NULL)
return 0;
int leftHeight = height(node.left);
int rightHeight = height(node.right);
return max(leftHeight, rightHeight) + 1;
}
- Time complexity:
(n รจ il numero di elementi) - Questo perchรจ
levelOrderTraversal()รจ, cioรจ
- Questo perchรจ
- Space complexity:
(se l'albero non รจ bilanciato, nel caso peggiore รจ praticamente una lista) (se l'albero รจ bilanciato, nel caso pessimo non devi tenere tutti gli elementi nello stack)
Implementazione iterativa (usando una coda)
L'idea รจ la seguente:
- Per ogni nodo, prima stampiamo il suo valore, poi lo rimuoviamo dalla coda e successivamente aggiungiamo i suoi figli nella coda.
void levelOrderTraversal(Tree root) {
/* Base case */
if (root == NULL)
return;
/* Create an empty queue for level order traversal */
queue<Tree> queue;
/* Enqueue root */
queue.push(root);
while(!queue.empty()) {
/* Print front of queue and remove it from queue */
Tree node = queue.front();
cout << node.data << " ";
queue.pop();
/* Enqueue left child */
if(node.left != NULL)
queue.push(node.left);
/* Enqueue right child */
if(node.right != NULL)
queue.push(node.right);
}
}
- Time complexity:
(n รจ il numero di elementi) - Space complexity:
(w รจ la massima larghezza dell'albero)