Level-Order-Traversierung

Lektion 15 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

Eine Level-Order-Traversierung (auch Breitensuche genannt) durchläuft den Baum Zeile für Zeile: zuerst die Wurzel, dann beide Kinder, dann alle vier Enkelkinder und so weiter, anstatt wie bei In-Order oder Pre-Order in die Tiefe zu gehen (Tiefensuche).

Der Standardweg hierfür ist eine Warteschlange (Queue): Beginnen Sie mit der Wurzel in der Warteschlange, entfernen Sie dann wiederholt den vordersten Knoten, notieren Sie seinen Wert und fügen Sie seine Kinder (das linke vor dem rechten) am Ende der Warteschlange hinzu.

Aufgabe

Einfach

Schreiben Sie eine Funktion levelOrder(tree), die eine Liste aller Werte im Baum zurückgibt, Ebene für Ebene, von links nach rechts innerhalb jeder Ebene.

Probier es selbst

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