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 T e U che hanno gli stessi nodi, gli stessi figli per ogni nodo e la stessa radice, sono distinti qualora un nodo u sia designato come figlio sinistro in T e come figlio destro in U.
Per esempio, i seguenti due alberi binari sono diversi:

AlberoBinario.png500

๐Ÿ”Ž 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 n nodi รจ ฮ˜(n), in quanto ogni nodo viene visitato al massimo una volta.

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:

/* 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;
}
Implementazione iterativa (usando una coda)

L'idea รจ la seguente:

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);
    }
}