Bäume und Graphen in C

Bäume und Graphen sind nichtlineare Datenstrukturen zur Darstellung hierarchischer und vernetzter Daten.

In dieser Lektion lernen Sie:

• Wie Bäume und Graphen strukturiert sind.
• Wie Sie einen Binärbaum in C implementieren.
• Wie Sie Graphen mithilfe von Adjazenzlisten und -matrizen darstellen.

Was ist ein Baum?

Ein Baum ist eine hierarchische Datenstruktur, die aus Knoten besteht.

Wichtige Begriffe:

• Wurzel – Der oberste Knoten.
• Elternknoten und Kindknoten – Direkt miteinander verbundene Knoten.
• Blatt – Ein Knoten ohne Kindknoten.

Beispiel: Knoten eines Binärbaums

In C wird ein Knoten eines Binärbaums mithilfe einer struct mit Zeigern auf den linken und rechten Kindknoten definiert.

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Durchlaufen eines Binärbaums

Methoden zum Durchlaufen:

• Inorder (LNR) – Links, Knoten, Rechts.
• Preorder (NLR) – Knoten, Links, Rechts.
• Postorder (LRN) – Links, Rechts, Knoten.

Beispiel: Inorder-Durchlauf

Dieses Programm durchläuft einen Binärbaum in Inorder-Reihenfolge.

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

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

Was ist ein Graph?

Ein Graph ist eine Sammlung von Knoten (Vertices), die durch Kanten verbunden sind.

Graphen können sein:

• Gerichtet – Kanten haben eine Richtung.
• Ungerichtet – Kanten haben keine Richtung.

Darstellung von Graphen

Graphen können mithilfe folgender Strukturen dargestellt werden:

• Adjazenzmatrix – Ein zweidimensionales Array, das Verbindungen darstellt.
• Adjazenzliste – Eine Liste, in der jeder Knoten auf seine Nachbarn verweist.

Durchlaufen von Graphen

Gängige Methoden zum Durchlaufen:

• Breitensuche (BFS) – Besucht alle Nachbarn, bevor die Suche in die Tiefe fortgesetzt wird.
• Tiefensuche (DFS) – Erkundet einen Pfad so weit wie möglich, bevor sie zurückgeht.

Zusammenfassung

In dieser Lektion haben Sie gelernt:

• Wie Bäume und Graphen aufgebaut sind.
• Wie Sie Baumdurchläufe durchführen.
• Wie Graphen dargestellt und durchlaufen werden.

Damit ist der Abschnitt „Datenstrukturen in C“ abgeschlossen!