Обход по уровням

Урок 15 из 16 курса AVL-дерево — Серия «Структуры данных» №10 на Coddy.

Поуровневый обход (также называемый обходом в ширину) посещает дерево уровень за уровнем: сначала корень, затем оба его дочерних узла, затем все четыре внучатых узла и так далее, вместо того чтобы погружаться в глубину, как это делают центрированный (in-order) или префиксный (pre-order) обходы.

Стандартный способ реализации такого обхода — использование очереди: поместите корень в очередь, затем последовательно извлекайте узел из начала очереди, записывайте его значение и добавляйте его дочерние узлы (сначала левый, затем правый) в конец очереди.

Задание

Легко

Напишите функцию levelOrder(tree), которая возвращает список всех значений в дереве, уровень за уровнем, слева направо на каждом уровне.

Попробуйте сами

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