Parcours par niveau

Leçon 15 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

Un parcours par niveaux (également appelé parcours en largeur) visite l'arbre ligne par ligne : d'abord la racine, puis ses deux enfants, puis les quatre petits-enfants, et ainsi de suite, au lieu de plonger en profondeur comme le font les parcours infixe ou pré-ordre.

La méthode standard pour y parvenir est d'utiliser une file : commencez par y placer la racine, puis retirez de manière répétée le nœud à l'avant, enregistrez sa valeur et ajoutez ses enfants (le gauche avant le droit) à l'arrière de la file.

Défi

Facile

Écrivez une fonction levelOrder(tree) qui retourne une liste de chaque valeur de l'arbre, niveau par niveau, de gauche à droite au sein de chaque niveau.

Essayez vous-même

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