Bomen en grafen

Bomen en grafen zijn niet-lineaire gegevensstructuren die worden gebruikt om hiërarchische gegevens en gegevens in netwerken weer te geven.

In deze les leer je:

• Hoe bomen en grafen zijn opgebouwd.
• Hoe je een binaire boom implementeert in C.
• Hoe je grafen weergeeft met aangrenzendheidslijsten en -matrices.

Een boom is een hiërarchische gegevensstructuur die uit knopen bestaat.

Belangrijke termen:

• Wortel - De bovenste knoop.
• Ouder en kind - Knopen die rechtstreeks met elkaar verbonden zijn.
• Blad - Een knoop zonder kinderen.

In C wordt een knoop van een binaire boom gedefinieerd met een struct met aanwijzers naar het linker- en rechterkind.

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

Doorloopmethoden:

• Inorder (LNR) - Links, knoop, rechts.
• Preorder (NLR) - Knoop, links, rechts.
• Postorder (LRN) - Links, rechts, knoop.

Dit programma doorloopt een binaire boom in inorder-volgorde.

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

Een graaf is een verzameling knopen (hoekpunten) die door kanten met elkaar verbonden zijn.

Grafen kunnen zijn:

• Gericht - Kanten hebben een richting.
• Ongericht - Kanten hebben geen richting.

Grafen kunnen worden weergegeven met:

• Adjacentiematrix - Een tweedimensionale array die verbindingen weergeeft.
• Adjacentielijst - Een lijst waarin elke knoop naar zijn buren verwijst.

Veelgebruikte doorloopmethoden:

• Breedte-eerst zoeken (BFS) - Bezoekt alle buren voordat het dieper gaat.
• Diepte-eerst zoeken (DFS) - Verkent de graaf zo diep mogelijk voordat het teruggaat.

In deze les heb je geleerd:

• Hoe bomen en grafen zijn opgebouwd.
• Hoe je bomen doorloopt.
• Hoe grafen worden weergegeven en doorlopen.

Dit is het einde van het onderdeel Gegevensstructuren in C!