Recorrido por niveles

Lección 15 de 16 del curso Árbol AVL - Serie de Estructuras de Datos #10 de Coddy.

Un recorrido por niveles (también llamado búsqueda en anchura) visita el árbol fila por fila: primero la raíz, luego sus dos hijos, después los cuatro nietos, y así sucesivamente, en lugar de sumergirse en profundidad como lo hacen los recorridos in-orden o pre-orden.

La forma estándar de hacer esto es mediante una cola: se comienza con la raíz dentro de ella, luego se elimina repetidamente el nodo frontal, se registra su valor y se añaden sus hijos (el izquierdo antes que el derecho) al final de la cola.

Desafío

Fácil

Escribe una función levelOrder(tree) que devuelva una lista de cada valor en el árbol, nivel por nivel, de izquierda a derecha dentro de cada nivel.

Pruébalo tú mismo

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