Pohon Biner

Motivasi: Berpikir Hierarkis

Sejauh ini, kita selalu menyusun data secara linier (berbaris lurus) seperti gerbong kereta atau antrean kasir. Namun, kenyataan di dunia nyata sering kali tidak berbentuk garis lurus.

Coba perhatikan silsilah keluarga, struktur organisasi perusahaan, susunan bab dalam buku, atau menu-menu di aplikasi komputer. Semuanya memiliki tingkatan atau hierarki: ada yang menjadi Induk (Parent), dan ada yang menjadi Anak (Child).

Untuk memodelkan masalah seperti ini, kita menggunakan struktur data Pohon (Tree). Sesuai namanya, struktur ini membelah dan bercabang, persis seperti akar atau ranting pohon.

Anatomi Pohon Biner

Pohon memiliki banyak jenis, namun yang paling sering digunakan dalam ilmu komputer adalah Pohon Biner (Binary Tree). Pohon biner adalah pohon di mana setiap simpul (node) memiliki maksimal dua buah cabang (kiri dan kanan).

Perhatikan visualisasi Pohon Biner sederhana berikut:

Mari kenali istilah-istilah anatominya:

• Akar (Root): Titik paling atas dari sebuah pohon. Satu pohon hanya memiliki satu akar.
• Daun (Leaf): Simpul paling ujung yang tidak memiliki anak sama sekali (Kiri dan Kanan bernilai NULL).
• Tingkat (Level): Jarak atau panjang langkah dari akar menuju ke suatu simpul. Akar berada di level 1.
• Saudara (Sibling): Simpul-simpul yang memiliki Orang Tua yang sama.
• Pohon Condong (Skewed Tree): Pohon biner yang cabangnya hanya tumbuh ke satu sisi saja (misalnya terus-menerus ke kiri). Bentuk ini menyerupai Linked List biasa.

Paradigma Rekursif pada Pohon

Di sinilah letak tantangannya. Array atau Linked List sangat ramah dengan perulangan (while atau for). Namun, Pohon Biner dibangun dengan sifat Rekursif.

Artinya, setiap kali Anda melihat cabang kiri atau cabang kanan, cabang tersebut juga merupakan sebuah pohon biner yang utuh (Sub-Pohon). Oleh karena itu, hampir semua algoritma yang memanipulasi pohon biner (mencetak, mencari, menghitung) ditulis menggunakan fungsi rekursif.

Dalam merancang fungsi rekursif untuk Pohon, selalu siapkan dua hal:

1. Basis (Titik Berhenti): Apa yang terjadi jika Pohon itu kosong? (P == NULL).
2. Rekurens (Pemanggilan Diri): Lakukan sesuatu pada Akar, lalu panggil fungsi yang sama untuk mengurus P->left dan P->right.

Penelusuran (Traversal)

Bagaimana cara kita membaca isi Pohon Biner? Karena bentuknya bercabang, kita butuh metode penelusuran (Traversal). Ada 3 cara yang paling terkenal:

1. Pre-Order (Akar -> Kiri -> Kanan)

Cetak dulu akarnya, baru telusuri seluruh cabang kirinya sampai habis, kemudian telusuri seluruh cabang kanannya.

void PreOrder(Node *P) {
    if (P != NULL) {
        cout << P->info << " "; // 1. Proses Akarnya dulu
        PreOrder(P->left);      // 2. Lanjutkan ke cabang kiri
        PreOrder(P->right);     // 3. Lanjutkan ke cabang kanan
    }
}

2. In-Order (Kiri -> Akar -> Kanan)

Telusuri dulu cabang kiri sampai mentok, lalu cetak akarnya, barulah telusuri cabang kanannya. Metode ini sangat berguna untuk menampilkan data secara terurut.

void InOrder(Node *P) {
    if (P != NULL) {
        InOrder(P->left);       // 1. Ke cabang kiri dulu
        cout << P->info << " "; // 2. Proses Akarnya di tengah
        InOrder(P->right);      // 3. Baru ke cabang kanan
    }
}

3. Post-Order (Kiri -> Kanan -> Akar)

Selesaikan dulu urusan anak-anaknya (kiri dan kanan) sampai ke ujung daun, barulah proses akarnya paling terakhir.

void PostOrder(Node *P) {
    if (P != NULL) {
        PostOrder(P->left);     // 1. Ke cabang kiri
        PostOrder(P->right);    // 2. Ke cabang kanan
        cout << P->info << " "; // 3. Proses Akar terakhir
    }
}