Visita in ordine per livelli

Lezione 15 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

Una visita in ordine di livello (chiamata anche visita in ampiezza) attraversa l’albero riga per riga: prima la radice, poi entrambi i suoi figli, poi tutti e quattro i nipoti, e così via, invece di scendere in profondità come fanno le visite in ordine o in preordine.

Il modo standard per farlo è usare una coda: inizia con la radice al suo interno, poi rimuovi ripetutamente il nodo in testa, registrane il valore e inserisci i suoi figli (prima quello sinistro e poi quello destro) in fondo alla coda.

Sfida

Facile

Scrivi una funzione levelOrder(tree) che restituisca un elenco di tutti i valori dell’albero, livello per livello, da sinistra a destra all’interno di ciascun livello.

Provalo tu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
        int result[1024];
    int resultCount = levelOrder(tree, result);
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(" ");
        printf("%d", result[i]);
    }
    printf("\n");
    return 0;
}