Stapel und Bäume in C: Schiffsquartiere mit Stack und Tiefensuche zählen

Einführung: Das Problem der neuen Schiffsanordnung

Stell dir vor, du bist Kapitän eines Raumschiffs. Die Reparaturcrew hat das Innere völlig umgestaltet – Gänge sind blockiert, Wände entfernt. Du erhältst eine Liste von Raum-IDs, die ein Mitarbeiter beim Durchlaufen notiert hat. Jeder Raum wird jedes Mal notiert, wenn er betreten wird. Deine Aufgabe: Finde heraus, wie viele potenzielle Schlafquartiere es gibt (Räume ohne „Kinder“) und wie weit diese vom Haupteingang entfernt sind. Dieses Problem aus der Programmierung in C kombiniert Stapel (Stacks) und Bäume (Trees) – ideale Datenstrukturen für diese Aufgabe.

Warum ist das relevant? Stell dir vor, du entwickelst eine KI-gestützte App zur Navigation in großen Gebäuden – ähnliche Algorithmen helfen, optimale Wege zu finden. Oder denk an ein Turnier-Bracket in E-Sports: Jeder Spieler ist ein Knoten, und der Weg zum Finale entspricht der Tiefe im Baum. Genau so funktioniert auch die Tiefensuche hier.

Grundlagen: Stapel und Bäume in C

Ein Stapel (Stack) ist eine Datenstruktur nach dem LIFO-Prinzip (Last In, First Out). In C implementieren wir ihn oft als Array oder verkettete Liste. Ein Baum (Tree) besteht aus Knoten (Räumen) und Kanten (Korridoren). Da es genau einen Pfad zwischen zwei Knoten gibt, handelt es sich um einen Baum.

Die Eingabe ist eine Liste von Raum-IDs, die der Mitarbeiter in der Reihenfolge seines Besuchs notiert hat. Die Liste endet mit -1; die letzte ID vor -1 ist der Haupteingang. Der Mitarbeiter läuft jeden Korridor genau zweimal (hin und zurück). Das entspricht einer DFS-Traversierung (Depth-First Search) des Baums.

Schritt 1: Einlesen der Daten

Verwende eine while-Schleife, um die IDs zu lesen, bis -1 erscheint. Speichere die IDs in einem Array oder verarbeite sie direkt. Wir brauchen eine Möglichkeit, den Elternknoten und die Tiefe jedes Raums zu speichern. Ein Stack hilft uns, den aktuellen Pfad vom Haupteingang zum aktuellen Raum zu verfolgen.

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int stack[MAX];
int top = -1;

void push(int id) { stack[++top] = id; }
int pop() { return stack[top--]; }
int peek() { return stack[top]; }

Schritt 2: Eltern und Kinder verfolgen

Jedes Mal, wenn wir eine neue Raum-ID sehen, die nicht der aktuelle Raum ist (also nicht das oberste Element des Stapels), betreten wir einen neuen Raum. Dann schieben wir die ID auf den Stack und merken uns den Elternknoten (das vorherige oberste Element). Wenn wir eine ID sehen, die dem obersten Element entspricht, verlassen wir den Raum (pop). So bauen wir den Baum auf.

Zusätzlich zählen wir, wie viele Kinder jeder Raum hat. Ein Raum ist ein potenzielles Quartier, wenn er keine Kinder hat (d.h. er ist ein Blattknoten).

int parent[MAX] = {0}; // Elternknoten für jeden Raum (0 = unbekannt)
int children_count[MAX] = {0}; // Anzahl Kinder
int depth[MAX] = {0}; // Tiefe (Entfernung zum Haupteingang)

// Angenommen, der erste gelesene Raum ist der Start
int current = -1;
int id;
while (scanf("%d", &id) == 1 && id != -1) {
    if (top == -1) {
        // Erster Raum = Haupteingang
        push(id);
        depth[id] = 0;
        parent[id] = 0;
        current = id;
    } else if (id == peek()) {
        // Verlasse aktuellen Raum
        pop();
        if (top >= 0) current = peek();
        else current = -1;
    } else {
        // Betrete neuen Raum
        push(id);
        int p = peek(); // nach push ist peek der neue Raum; Elternknoten ist current
        parent[id] = current;
        depth[id] = depth[current] + 1;
        children_count[current]++;
        current = id;
    }
}

Schritt 3: Quartiere zählen und Distanzen summieren

Nachdem wir den gesamten Durchlauf verarbeitet haben, durchlaufen wir alle gesehenen Räume (z.B. mit einem besuchten Array) und prüfen, ob children_count[raum] == 0. Wenn ja, ist es ein Quartier. Die Distanz ist depth[raum]. Addiere beides.

int visited[MAX] = {0};
int quarters = 0, total_dist = 0;
// Angenommen, wir haben eine Liste aller IDs (z.B. in einem Array ids[])
for (int i = 0; i < num_ids; i++) {
    int r = ids[i];
    if (!visited[r]) {
        visited[r] = 1;
        if (children_count[r] == 0) {
            quarters++;
            total_dist += depth[r];
        }
    }
}
printf("%d %d\n", quarters, total_dist);

Beispiel aus der Praxis

Nehmen wir die erste Beispiel-Eingabe: 1 3 1 10 4 8 4 10 1 5 1 -1. Der Haupteingang ist 1. Der Stack wächst und schrumpft. Am Ende haben wir die Räume: 1 (Eingang, Tiefe 0, Kinder: 3,10,5 – also 3 Kinder), 3 (Tiefe 1, keine Kinder → Quartier), 10 (Tiefe 1, Kind: 4), 4 (Tiefe 2, Kind: 8), 8 (Tiefe 3, keine Kinder → Quartier), 5 (Tiefe 1, keine Kinder → Quartier). Quartiere: 3,5,8 → 3 Stück. Distanzen: 1+1+3=5. Passt.

Dieses Vorgehen ähnelt dem Zählen von Blättern in einem binären Baum, wie es in vielen Algorithmen-Kursen gelehrt wird. Es ist auch die Basis für Dijkstra oder BFS in ungewichteten Graphen – nützlich für Navigations-Apps oder Routenplaner.

Häufige Fehler vermeiden

• Stack nicht als Array implementiert: Nutze einen Stack, sonst gibt es Punktabzug.
• Keine Kommentare: Erkläre deinen Code – das ist Teil der Benotung.
• Zusätzliche Ausgaben: Kein „Bitte geben Sie...“ – nur die zwei Zahlen ausgeben.
• Falsche Parent-Zuordnung: Achte darauf, dass der Elternknoten der ist, von dem du kommst, nicht der, den du gerade betrittst.

Trends und Analogien

Stell dir vor, du entwickelst eine KI für ein Smart Home: Die Räume sind Knoten, der Haupteingang ist der Hub. Der Algorithmus könnte genutzt werden, um zu entscheiden, welche Räume als „Gästezimmer“ geeignet sind (keine Durchgangszimmer). Oder in der Spieleentwicklung: In einem Rogue-like-Spiel werden Level prozedural generiert – die Baumstruktur hilft, Räume und Gänge zu verbinden.

Ein weiteres Beispiel: Finanzdaten – Aktienkurse folgen manchmal baumartigen Entscheidungen (z.B. bei Binomialbäumen). Auch wenn das hier nicht direkt anwendbar ist, zeigt es die Vielseitigkeit von Bäumen.

Zusammenfassung

Mit einem Stack und einem Baum in C kannst du effizient die Anzahl der Blätter (Quartiere) und deren Tiefe (Distanz) bestimmen. Der Schlüssel liegt im Verfolgen des Pfades während der DFS-ähnlichen Traversierung. Übe dieses Muster – es taucht in vielen Informatik-Projekten und Hausaufgaben wieder auf.

Wenn du mehr über Bäume in C oder Stapel-Algorithmen lernen möchtest, schau dir unsere anderen Tutorials an. Viel Erfolg beim Programmieren!