Tree

Hash table cepat tetapi tak berurutan; linked list berurutan tetapi linear. Tree (pohon) menawarkan titik tengah yang sangat berharga: struktur hierarkis yang bisa ditelusuri, disusun, dan dipecah secara logis. Tree terdiri dari node yang saling terhubung tanpa membentuk lingkaran — satu node istimewa disebut root menjadi pintu masuk, dan setiap node lain punya tepat satu “induk”. Struktur ini ada di mana-mana dalam komputasi: sistem file berbentuk tree, DOM pada halaman web berbentuk tree, dan struktur data seperti BST, heap, hingga proses kompilasi ekspresi aritmetika semuanya berdiri di atasnya. Chapter ini membangun binary tree manual dan menguasai tiga traversal rekursifnya.

Terminologi Tree #

Sebelum menulis kode, kita perlu satu kosakata yang dipakai berulang-ulang. Tabel berikut merangkum istilah paling penting untuk binary tree — tree yang setiap node-nya maksimal punya dua anak:

Istilah depth dan height kadang ditulis dengan konvensi berbeda (mulai dari 0 atau 1); yang penting konsisten. Implementasi kita menghitung height sebagai jumlah level, sehingga tree berisi satu node punya tinggi 1.

Membangun Binary Tree di C++ #

Seperti linked list, bahan bangunan tree hanyalah struct dan pointer. Bedanya, setiap node binary tree membawa dua pointer: anak kiri dan anak kanan. Program berikut membangun tree berisi enam huruf, menampilkan tiga traversal, menghitung tinggi, lalu membersihkan memori:

// Binary tree manual: terminologi dasar dan tiga traversal rekursif.
#include <iostream>

struct Node {
    char label;
    Node* kiri;
    Node* kanan;
};

Node* buatNode(char label, Node* kiri, Node* kanan) {
    return new Node{label, kiri, kanan};
}

void preOrder(Node* node, bool& pertama) {
    if (node == nullptr) return;
    if (!pertama) std::cout << ' ';
    std::cout << node->label;   // akar, kiri, kanan
    pertama = false;
    preOrder(node->kiri, pertama);
    preOrder(node->kanan, pertama);
}

void inOrder(Node* node, bool& pertama) {
    if (node == nullptr) return;
    inOrder(node->kiri, pertama);
    if (!pertama) std::cout << ' ';
    std::cout << node->label;   // kiri, akar, kanan
    pertama = false;
    inOrder(node->kanan, pertama);
}

void postOrder(Node* node, bool& pertama) {
    if (node == nullptr) return;
    postOrder(node->kiri, pertama);
    postOrder(node->kanan, pertama);
    if (!pertama) std::cout << ' ';
    std::cout << node->label;   // kiri, kanan, akar
    pertama = false;
}

int tinggi(Node* node) {  // tinggi dihitung dari jumlah level
    if (node == nullptr) return 0;
    int kiri = tinggi(node->kiri);
    int kanan = tinggi(node->kanan);
    return 1 + (kiri > kanan ? kiri : kanan);
}

void hapusTree(Node* node) {  // membebaskan memori dengan pola post-order
    if (node == nullptr) return;
    hapusTree(node->kiri);
    hapusTree(node->kanan);
    delete node;
}

int main() {
    // Membangun tree dari daun menuju root
    Node* d = buatNode('D', nullptr, nullptr);
    Node* e = buatNode('E', nullptr, nullptr);
    Node* f = buatNode('F', nullptr, nullptr);
    Node* b = buatNode('B', d, e);
    Node* c = buatNode('C', nullptr, f);
    Node* a = buatNode('A', b, c);  // A adalah root

    bool pertama = true;
    std::cout << "preOrder : ";
    preOrder(a, pertama);
    std::cout << "\ninOrder  : ";
    pertama = true;
    inOrder(a, pertama);
    std::cout << "\npostOrder: ";
    pertama = true;
    postOrder(a, pertama);
    std::cout << "\nTinggi tree: " << tinggi(a)
              << " (root dihitung level 1)\n";

    hapusTree(a);
    return 0;
}

Output yang Dihasilkan:

preOrder : A B D E C F
inOrder  : D B E A C F
postOrder: D E B F C A
Tinggi tree: 3 (root dihitung level 1)

Bedah baris penting:

1. Baris 4-8: struct Node berisi label dan dua pointer kiri, kanan — bentuk ini identik dengan Node linked list, hanya dengan rantai ganda.
2. Baris 57-62 (main): tree dibangun dari daun ke root; D, E, F dibuat lebih dulu, lalu B (anak: D dan E), C (anak kanan: F), dan akhirnya A sebagai root.
3. Baris 14-21 (preOrder): urutan akar → kiri → kanan; fungsi memproses node sendiri sebelum turun ke anak.
4. Baris 23-30 (inOrder): urutan kiri → akar → kanan; seluruh subtree kiri selesai dicetak sebelum node pusat.
5. Baris 32-39 (postOrder): urutan kiri → kanan → akar; node baru dicetak setelah semua keturunannya selesai.
6. Baris 41-45 (tinggi): tinggi dihitung rekursif — 1 ditambah tinggi anak yang lebih dalam; untuk tree kita hasilnya 3 level.
7. Baris 48-53 (hapusTree): membebaskan memori dengan pola post-order — anak kiri dan kanan dihapus dulu, node induk terakhir; menghapus induk lebih dulu berarti kehilangan alamat anak-anaknya.

Struktur yang kita bangun bisa digambarkan seperti ini; perhatikan F adalah anak kanan dari C sehingga C tidak punya anak kiri:

Diagram di atas menegaskan terminologi kita: A adalah root, D-E-F adalah daun, dan depth F adalah 2 (dua edge dari A). Tiga traversal pada tree yang sama menghasilkan tiga urutan berbeda — dan perbedaan itu bermakna, bukan sekadar variasi.

Tiga Traversal, Tiga Kegunaan #

Pre-order (A B D E C F) memproses node sebelum keturunannya — cocok untuk menyalin struktur tree atau menyimpan ekspresi dengan operator di depan. In-order (D B E A C F) mengunjungi subtree kiri, node, lalu subtree kanan; pada tree terurut seperti BST yang akan kita bangun chapter berikutnya, in-order menghasilkan data terurut menaik — properti yang menjadikannya traversal paling terkenal. Post-order (D E B F C A) memproses keturunan sebelum induknya — persis yang dibutuhkan untuk menghitung ukuran subtree atau, seperti hapusTree di atas, membebaskan memori dengan aman.

Ketiga traversal berbagi satu kerangka rekursif yang sama: tangani kasus kosong (nullptr), lalu atur posisi satu baris cetak di antara dua pemanggilan rekursif. Menggeser baris itu ke atas, tengah, atau bawah adalah seluruh perbedaan ketiganya.

Kapan Tree Dipakai #

Tree adalah pilihan tepat ketika data memang hierarkis (struktur organisasi, menu bersarang, DOM) atau ketika kita ingin keputusan logaritmik per langkah — setiap turun satu level membuang separuh ruang pencarian pada tree yang seimbang. STL menyediakan padanannya: std::map dan std::set diimplementasikan sebagai tree seimbang (red-black tree) yang menjamin operasi O(log n) sekaligus menyimpan data terurut, keunggulan yang tidak dimiliki hash table.

Setelah terbiasa dengan tree generik, kita siap menambahkan satu aturan sederhana yang mengubahnya menjadi mesin pencarian O(log n): binary search tree.

Rujukan resmi: std::map dan std::set .