Binary Tree dan Contoh Program Sederhana Menggunakan Bahasa C

Pada artikel kali ini kita akan membahas secara singkat tentang Tree. Sebelumnya, kita telah mengenal struktur data linear, seperti array, linked list, queue dan juga stack. Tree merupakan sekumpulan node yang saling terhubung secara hirarki/non-linier. Struktur Tree dapat dimanfaatkan untuk menyelesaikan permasalahan terkait dengan tree, seperti algoritma Decision Tree. Pada Tree, kita kenal beberapa istilah yang penting untuk diketahui, yaitu:

1. Root: node yang berada paling atas
2. Node: entitas yang saling berkaitan
3. Edge: penghubung antar node
4. Parent: node yang posisinya berada lebih tinggi dari node yang lain
5. Children: node yang posisinya berada lebih rendah/di bawah node yang lain
6. Leaf: node yang posisinya paling rendah
7. Sibling: node yang berada pada posisi yang sama

Pada sebuah Tree yang memiliki n buah node, maka akan memiliki n-1 buah edge. Pada Tree juga kita dapat mengetahui jumlah edge dari root ke node tertentu yang dikenal dengan istilah Depth of Node. Kita juga dapat mengetahui jumlah edge terpanjang dari node ke leaf, yang dikenal dengan istilah Height of Node. Dan kita juga dapat mengetahui edge terpanjang dari root ke leaf, atau yang sering dikenal dengan istilah Height of Tree.

Dalam bahasan mengenai Tree, kita juga akan mengenal tentan Binary Tree, yaitu tree di mana setiap node memiliki paling banyak 2 buah children. Children tersebut dikenal dengan left child dan right child. Pada binary tree, dikenal juga perfect bianry tree, yaitu semua level pada tree terisi lengkap sampai dengan left child dan right child. Dengan kondisi perfect binary tree ini, kita dapat menghitung node maksimal jika mengetahui height of tree, dengan persamaan 2ⁿ⁺¹-1 dengan n adalah height of tree. Apabila ingin mencari height dari tree jika diketahui jumlah dari node maksimalnya, maka dapat menggunakan persamaan log₂(n+1)-1 dengan n adalah jumlah node maksimal.

Dalam pembentukan binary tree, perlu kita lakukan beberapa hal, yaitu:

1. Menyiapkan node baru: mengalokasikan memory, memasukkan informasi, set pointer kiri dan kanan = NULL
2. Menyisipkan pada posisi yang tepat
   1. Penelusuran -> menentukan posisi yang tepat, info/value yang nilainya lebih besar dari parent akan ditelusuri di sebelah kanan, begitu juga sebaliknya.
   2. Penempatan -> info/value yang nilainya lebih besar dari parent akan ditempatkan di sebalah kanan, begitu juga sebaliknya.

Kita perlu melakukan traversal ke semua node untuk mencetak/menampilkan info/value dari tree tersebut. Kita dapat menggunakan Level order traversal, preOrder traversal, inOrder traversal dan postOrder traversal. Untuk pebahasan lebih jauh tentang ini dapat dibaca di materi saya di sini. Lalu bagaimana implementasinya dalam bahasa pemrograman C? Berikut kode program yang dapat dipakai.

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

// inisialisasi struct

struct data{
    int number;
    struct data *left, *right, *height, *depth; // pointer untuk menampung percabangan kiri dan kanan dan tinggi dan kedalaman
} *root;

// fungsi push -> menambah data baru pada tree
void push(struct data **current, int number){
    // jika pointer current kosong, maka akan membuat blok data baru
    if((*current) == NULL){
        // alokasikan memori
        (*current) = (struct data *)malloc(sizeof (struct data));
        (*current)->number = number;
        (*current)->left = (*current)->right = NULL;
        // jika tidak kosong, maka akan dibandingkan apakah angka yang akan dimasukkan lebih kecil dari root.
        // jika iya, maka belok ke kiri dan lakukan rekursif terus menerus hingga kosong
    } else if(number < (*current)->number){
        push(&(*current)-> left, number);
    } else if(number >= (*current)->number){
        // jika lebih besar, maka belok ke kanan
        push(&(*current)->right, number);
    }
}

// preOrder Binary Tree Traversal --> parent/value, kiri, kanan
void preOrder(struct data **current){
    if((*current) != NULL){
        printf("%d -> ", (*current)->number);
        preOrder(&(*current)->left);
        preOrder(&(*current)->right);
    }
}

// inOrder Binary Tree Traversal --> kiri, parent/value, kanan
void inOrder(struct data **current){
    if((*current) != NULL){
        inOrder(&(*current)->left);
        printf("%d -> ", (*current)->number);
        inOrder(&(*current)->right);
    }
}

// postOrder Binary Tree Traversal --> kiri, kanan, parent/value
void postOrder(struct data **current){
    if((*current) != NULL){
        postOrder(&(*current)->left);
        postOrder(&(*current)->right);
        printf("%d -> ", (*current)->number);
    }
}

int main()
{
    push(&root, 11);
    push(&root, 22);
    push(&root, 13);
    push(&root, 15);
    push(&root, 9);
    inOrder(&root);

    return 0;
}

Penjelasan kode program sudah saya sertakan di sana, silakan dapat disimak dan dicoba sendiri. Untuk lebih memahami, kalian dapat menambahkan beberapa fungsi berikut untuk menambah pemahaman tentang materi tree ini.

1. Buat fungsi untuk menghitung jumlah node
2. Buat fungsi untuk menghitung jumlah leaf, dan nilai dari leaf tersebut
3. Buat fungsi untuk menghitung jumlah edge
4. Buat fungsi untuk menghitung Depth of Node
5. Buat fungsi untuk menghitung Height of Node
6. Buat fungsi untuk menghitung Height of Tree

Pembahasan juga terdapat dalam bentuk video yang dapat dilihat di kanal youtube atau melalui video di bawah ini.

Materi Struktur Data dan Algoritma - Tree

Pembahasan Contoh Penerapan Binary Tree

Demikian artikel pada kesempatan kali ini, semoga bermanfaat.