Tree dan Graph: Struktur Data Non-Linear untuk Hierarki dan Jaringan

1
         [10]          ← Root
2
        /    \
3
      [5]    [15]      ← Internal nodes
4
     /   \      \
5
   [3]   [7]   [20]   ← Leaf nodes

1
struct TreeNode {
2
    int data;
3
    struct TreeNode* left;
4
    struct TreeNode* right;
5
};
6

7
struct TreeNode* createNode(int data) {
8
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
9
    node->data = data;
10
    node->left = node->right = NULL;
11
    return node;
12
}

1
void inorder(struct TreeNode* root) {
2
    if (root == NULL) return;
3
    inorder(root->left);
4
    printf("%d ", root->data);
5
    inorder(root->right);
6
}
7
// Output: 3 5 7 10 15 20

1
void preorder(struct TreeNode* root) {
2
    if (root == NULL) return;
3
    printf("%d ", root->data);
4
    preorder(root->left);
5
    preorder(root->right);
6
}
7
// Output: 10 5 3 7 15 20

1
void postorder(struct TreeNode* root) {
2
    if (root == NULL) return;
3
    postorder(root->left);
4
    postorder(root->right);
5
    printf("%d ", root->data);
6
}
7
// Output: 3 7 5 20 15 10

1
        [50]
2
       /    \
3
    [30]    [70]
4
   /    \   /  \
5
 [20]  [40][60][80]

1
struct TreeNode* insert(struct TreeNode* root, int data) {
2
    if (root == NULL) return createNode(data);
3

4
    if (data < root->data)
5
        root->left = insert(root->left, data);
6
    else if (data > root->data)
7
        root->right = insert(root->right, data);
8

9
    return root;
10
}

1
struct TreeNode* search(struct TreeNode* root, int data) {
2
    if (root == NULL || root->data == data)
3
        return root;
4

5
    if (data < root->data)
6
        return search(root->left, data);
7
    return search(root->right, data);
8
}
9
// Kompleksitas: O(log n) average, O(n) worst case

1
struct TreeNode* minNode(struct TreeNode* node) {
2
    while (node->left != NULL)
3
        node = node->left;
4
    return node;
5
}
6

7
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
8
    if (root == NULL) return NULL;
9

10
    if (data < root->data)
11
        root->left = deleteNode(root->left, data);
12
    else if (data > root->data)
13
        root->right = deleteNode(root->right, data);
14
    else {
15
        // Node ditemukan
16
        if (root->left == NULL) {
17
            struct TreeNode* temp = root->right;
18
            free(root);
19
            return temp;
20
        } else if (root->right == NULL) {
21
            struct TreeNode* temp = root->left;
22
            free(root);
23
            return temp;
24
        }
25
        // Node dengan 2 child: ganti dengan inorder successor
26
        struct TreeNode* temp = minNode(root->right);
27
        root->data = temp->data;
28
        root->right = deleteNode(root->right, temp->data);
29
    }
30
    return root;
31
}

1
    A ——— B
2
   / \   / \
3
  C   D—E   F

1
Vertex: A=0, B=1, C=2, D=3
2

3
     A  B  C  D
4
A  [ 0  1  1  0 ]
5
B  [ 1  0  0  1 ]
6
C  [ 1  0  0  1 ]
7
D  [ 0  1  1  0 ]

1
#define V 4
2
int graph[V][V] = {
3
    {0, 1, 1, 0},
4
    {1, 0, 0, 1},
5
    {1, 0, 0, 1},
6
    {0, 1, 1, 0}
7
};
8

9
// Cek edge A-B: graph[0][1] == 1

1
struct AdjNode {
2
    int dest;
3
    struct AdjNode* next;
4
};
5

6
struct Graph {
7
    int numVertices;
8
    struct AdjNode** adjLists;
9
};

1
void dfs(int graph[V][V], int visited[], int vertex) {
2
    visited[vertex] = 1;
3
    printf("%d ", vertex);
4

5
    for (int i = 0; i < V; i++) {
6
        if (graph[vertex][i] == 1 && !visited[i])
7
            dfs(graph, visited, i);
8
    }
9
}
10

11
// Mulai dari vertex 0
12
int visited[V] = {0};
13
dfs(graph, visited, 0);

1
void bfs(int graph[V][V], int start) {
2
    int visited[V] = {0};
3
    int queue[V], front = 0, rear = 0;
4

5
    visited[start] = 1;
6
    queue[rear++] = start;
7

8
    while (front < rear) {
9
        int vertex = queue[front++];
10
        printf("%d ", vertex);
11

12
        for (int i = 0; i < V; i++) {
13
            if (graph[vertex][i] == 1 && !visited[i]) {
14
                visited[i] = 1;
15
                queue[rear++] = i;
16
            }
17
        }
18
    }
19
}