Drzewa i grafy w języku C

Drzewa i grafy to nieliniowe struktury danych używane do reprezentowania danych hierarchicznych i sieciowych.

W tej lekcji dowiedzą się Państwo:

• Jak są zbudowane drzewa i grafy.
• Jak implementować drzewo binarne w języku C.
• Jak reprezentować grafy za pomocą list sąsiedztwa i macierzy sąsiedztwa.

Czym jest drzewo?

Drzewo to hierarchiczna struktura danych składająca się z węzłów.

Najważniejsze pojęcia:

• Korzeń - Węzeł znajdujący się na najwyższym poziomie.
• Rodzic i potomek - Węzły połączone bezpośrednio.
• Liść - Węzeł, który nie ma potomków.

Przykład: węzeł drzewa binarnego

W języku C węzeł drzewa binarnego definiuje się za pomocą struktury struct zawierającej wskaźniki do lewego i prawego potomka.

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

Przechodzenie drzewa binarnego

Metody przechodzenia:

• Inorder (LNR) - Lewy potomek, węzeł, prawy potomek.
• Preorder (NLR) - Węzeł, lewy potomek, prawy potomek.
• Postorder (LRN) - Lewy potomek, prawy potomek, węzeł.

Przykład: przechodzenie inorder

Ten program wykonuje przechodzenie inorder drzewa binarnego.

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

Czym jest graf?

Graf to zbiór węzłów (wierzchołków) połączonych krawędziami.

Grafy mogą być:

• Skierowane - Krawędzie mają określony kierunek.
• Nieskierowane - Krawędzie nie mają kierunku.

Reprezentacja grafu

Grafy można reprezentować za pomocą:

• Macierzy sąsiedztwa - Tablicy dwuwymiarowej przedstawiającej połączenia.
• Listy sąsiedztwa - Listy, w której każdy węzeł wskazuje swoich sąsiadów.

Przechodzenie grafu

Typowe metody przechodzenia:

• Przeszukiwanie wszerz (BFS) - Odwiedza wszystkich sąsiadów przed przejściem głębiej.
• Przeszukiwanie w głąb (DFS) - Bada graf tak głęboko, jak to możliwe, a następnie cofa się.

Podsumowanie

W tej lekcji nauczyli się Państwo:

• Jak zbudowane są drzewa i grafy.
• Jak wykonywać przechodzenie drzew.
• Jak reprezentować grafy i wykonywać ich przechodzenie.

To kończy sekcję dotyczącą struktur danych w języku C!