Przejście poziomami

Lekcja 15 z 16 w kursie Drzewo AVL – struktury danych, seria #10 w Coddy.

Przejście poziomami (nazywane też przejściem wszerz) odwiedza węzły drzewa wiersz po wierszu: najpierw korzeń, potem oboje jego dzieci, następnie wszystkich czworo wnuków i tak dalej, zamiast zagłębiać się w drzewie jak przy przejściu inorder lub preorder.

Standardowym sposobem wykonania tego jest użycie kolejki: umieść w niej korzeń, a następnie wielokrotnie usuwaj węzeł z początku kolejki, zapisuj jego wartość i dodawaj jego dzieci (najpierw lewe, potem prawe) na końcu kolejki.

Wyzwanie

Łatwy

Napisz funkcję levelOrder(tree), która zwraca listę wszystkich wartości w drzewie, poziom po poziomie, od lewej do prawej w obrębie każdego poziomu.

Spróbuj swoich sił

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