Pohon dan Graf dalam C

Pohon dan graf adalah struktur data nonlinier yang digunakan untuk merepresentasikan data hierarkis dan data jaringan.

Dalam pelajaran ini, Anda akan mempelajari:

• Bagaimana pohon dan graf disusun.
• Cara mengimplementasikan pohon biner dalam C.
• Cara merepresentasikan graf menggunakan daftar ketetanggaan dan matriks ketetanggaan.

Apa Itu Tree?

Tree adalah struktur data hierarkis yang terdiri dari Node.

Istilah penting:

• Akar - Node teratas.
• Induk dan Anak - Node yang terhubung secara langsung.
• Daun - Node yang tidak memiliki anak.

Contoh: Node Binary Tree

Dalam C, Node binary tree didefinisikan menggunakan struct dengan pointer anak kiri dan kanan.

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

Penelusuran Binary Tree

Metode penelusuran:

• inorder (LNR) - Kiri, Node, Kanan.
• preorder (NLR) - Node, Kiri, Kanan.
• postorder (LRN) - Kiri, Kanan, Node.

Contoh: Penelusuran inorder

Program ini melakukan penelusuran inorder pada binary tree.

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

Apa Itu Graph?

Graph adalah kumpulan Node (verteks) yang terhubung oleh edge.

Graph dapat berupa:

• Berarah - Edge memiliki arah.
• Tidak berarah - Edge tidak memiliki arah.

Representasi Graph

Graph dapat direpresentasikan menggunakan:

• Matriks Ketetanggaan - Array 2D yang merepresentasikan koneksi.
• Daftar Ketetanggaan - Daftar yang setiap Node-nya menunjuk ke tetangganya.

Penelusuran Graph

Metode penelusuran yang umum:

• Penelusuran Breadth-First (BFS) - Mengunjungi semua tetangga sebelum bergerak lebih dalam.
• Penelusuran Depth-First (DFS) - Menjelajah sedalam mungkin sebelum melakukan penelusuran balik.

Ringkasan

Dalam pelajaran ini, Anda telah mempelajari:

• Struktur tree dan graph.
• Cara melakukan penelusuran tree.
• Cara merepresentasikan dan menelusuri graph.

Bagian Struktur Data dalam C ini telah selesai!