Dasar-dasar pohon biner

Pohon biner (binary tree) adalah struktur data hierarkis yang setiap node-nya paling banyak memiliki dua anak, dan hampir semua soal pohon pada wawancara teknis berangkat dari sini. Topik ini menetapkan kosakata intinya, mulai dari root, leaf, parent, hingga depth dan height, lalu membangun kelas node dari nol. Tiga penelusuran kedalaman, yaitu preorder, inorder, dan postorder, dijalankan pada satu pohon contoh yang sama dalam Python dan Java lengkap dengan keluaran aslinya. Rekursi yang ditanam pada modul rekursi menjadi bekal utama karena pohon pada dasarnya adalah rekursi yang dibuat terlihat.

Anatomi pohon biner#

Setiap pembahasan pohon memakai kosakata yang sama, sehingga pendefinisianya lebih dahulu menghemat banyak kebingungan. Node teratas disebut root, yaitu satu-satunya node yang tidak memiliki parent. Sebuah node yang tersambung ke atas adalah child dari node induknya, dan dua node dengan induk yang sama saling bersaudara (sibling). Node tanpa anak disebut leaf, sedangkan jarak dari root diukur dengan depth, yaitu banyaknya sisi pada lintasan dari root menuju node tersebut. Height pohon adalah depth node terdalamnya, dan sebuah subtree adalah node mana pun beserta seluruh keturunannya, yang dengan sendirinya juga merupakan pohon yang sah.

Diagram berikut menandai semua istilah itu pada pohon enam node. Node 1 menjadi root, node 2 menjadi parent bagi 4 dan 5 yang saling bersaudara, sementara node 4, 5, dan 6 berperan sebagai leaf. Kotak putus-putus melingkupi satu subtree yang berakar di node 2, dan subtree yang sama akan diperlakukan sebagai pohon tersendiri setiap kali rekursi masuk ke dalamnya.

Kelas node dan pohon contoh#

Cara paling umum merepresentasikan pohon biner di memori adalah objek node sederhana yang menyimpan satu nilai dan dua referensi. Definisi berikut dipakai di seluruh modul ini, baik pada Python maupun padanannya di Java.

# tidak-dijalankan
# kelas node yang dipakai di seluruh modul pohon
class Node:
    def __init__(self, nilai):
        self.nilai = nilai   # nilai yang disimpan node ini
        self.kiri = None     # anak kiri, None bila tidak ada
        self.kanan = None    # anak kanan, None bila tidak ada

Setiap referensi yang bernilai None berarti cabang itu kosong, sehingga pohon kosong pun cukup direpresentasikan dengan satu variabel None. Membangun pohon dilakukan dengan menyambung node satu per satu tanpa struktur bawaan apa pun, dan pola inilah yang dipakai saat menyelesaikan soal pohon pada judge daring. Perhatikan bentuk definisinya yang menyerupai rekursi, yaitu sebuah Node berisi referensi ke Node lain, sehingga struktur yang sama berulang ke bawah sampai mencapai None. Pernyataan bahwa pohon adalah rekursi yang dibuat terlihat kini dapat dibaca langsung dari kodenya, bukan sekadar ungkapan. Kesadaran lain yang membantu adalah memahami bahwa fungsi yang menerima sebuah node sebenarnya menerima subtree yang berakar di node itu, sehingga membaca kode penelusuran pada bagian berikutnya menjadi jauh lebih ringan.

Penelusuran preorder, inorder, dan postorder#

Keluarga penelusuran yang menuruni satu cabang sampai tuntas sebelum berpindah ke cabang lain disebut depth-first search atau DFS. Tiga urutan klasiknya lahir dari posisi pencatatan nilai node terhadap dua pemanggilan rekursif, yaitu preorder bila dicatat sebelum turun, inorder bila dicatat di antara keduanya, dan postorder bila dicatat setelah keduanya. Kasus dasarnya seragam, yaitu pemanggilan pada node None yang langsung kembali tanpa mencatat apa pun. Diagram berikut menampilkan ketiga urutan pada pohon contoh yang sama agar perbedaannya terlihat sekaligus.

"""Tiga penelusuran DFS pada satu pohon biner contoh."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def preorder(node, hasil):
    # urutan: akar, kiri, kanan
    if node is not None:
        hasil.append(node.nilai)
        preorder(node.kiri, hasil)
        preorder(node.kanan, hasil)

def inorder(node, hasil):
    # urutan: kiri, akar, kanan
    if node is not None:
        inorder(node.kiri, hasil)
        hasil.append(node.nilai)
        inorder(node.kanan, hasil)

def postorder(node, hasil):
    # urutan: kiri, kanan, akar
    if node is not None:
        postorder(node.kiri, hasil)
        postorder(node.kanan, hasil)
        hasil.append(node.nilai)

# pohon contoh dibangun manual tanpa struktur bawaan
n = {v: Node(v) for v in [1, 2, 3, 4, 5, 6]}
n[1].kiri, n[1].kanan = n[2], n[3]
n[2].kiri, n[2].kanan = n[4], n[5]
n[3].kanan = n[6]
akar = n[1]

for nama, fungsi in [("preorder ", preorder), ("inorder  ", inorder), ("postorder", postorder)]:
    hasil = []
    fungsi(akar, hasil)
    print(nama, ":", " ".join(str(x) for x in hasil))

preorder  : 1 2 4 5 3 6
inorder   : 4 2 5 1 3 6
postorder : 4 5 2 6 3 1

Ketiga fungsi hanya berbeda pada posisi satu baris hasil.append(node.nilai), sisanya identik. Preorder mencatat 1 lebih dahulu karena akar dikunjungi sebelum turun, sedangkan inorder mencatat 4 sebelum 1 karena subtree kiri harus tuntas lebih dahulu. Postorder menempatkan 1 paling akhir, sebuah ciri yang nantinya mendasari pola jawaban-dari-anak pada soal kedalaman dan diameter. Cara paling aman membaca keluarannya adalah mengikuti definisi, bukan menebak. Setiap kali rekursi masuk ke sebuah subtree, urutan yang sama diterapkan lagi dari awal pada subtree itu.

Varian Java#

public class PenelusuranPohon {
    static class Node {
        int nilai;
        Node kiri, kanan;
        Node(int nilai) { this.nilai = nilai; }
    }

    // urutan: akar, kiri, kanan
    static void preorder(Node node, StringBuilder hasil) {
        if (node != null) {
            hasil.append(node.nilai).append(' ');
            preorder(node.kiri, hasil);
            preorder(node.kanan, hasil);
        }
    }

    // urutan: kiri, akar, kanan
    static void inorder(Node node, StringBuilder hasil) {
        if (node != null) {
            inorder(node.kiri, hasil);
            hasil.append(node.nilai).append(' ');
            inorder(node.kanan, hasil);
        }
    }

    // urutan: kiri, kanan, akar
    static void postorder(Node node, StringBuilder hasil) {
        if (node != null) {
            postorder(node.kiri, hasil);
            postorder(node.kanan, hasil);
            hasil.append(node.nilai).append(' ');
        }
    }

    public static void main(String[] args) {
        Node akar = new Node(1);
        akar.kiri = new Node(2);
        akar.kanan = new Node(3);
        akar.kiri.kiri = new Node(4);
        akar.kiri.kanan = new Node(5);
        akar.kanan.kanan = new Node(6);

        StringBuilder pre = new StringBuilder();
        preorder(akar, pre);
        StringBuilder in = new StringBuilder();
        inorder(akar, in);
        StringBuilder post = new StringBuilder();
        postorder(akar, post);

        System.out.println("preorder  : " + pre.toString().trim());
        System.out.println("inorder   : " + in.toString().trim());
        System.out.println("postorder : " + post.toString().trim());
    }
}

preorder  : 1 2 4 5 3 6
inorder   : 4 2 5 1 3 6
postorder : 4 5 2 6 3 1

Struktur kodenya mirip, tetapi ada beberapa perbedaan yang layak diperhatikan. Node dibuat sebagai kelas bersarang statis di dalam kelas utama sehingga satu berkas tetap berisi satu program yang utuh, dan program dijalankan dengan java PenelusuranPohon.java, bentuk eksekusi satu berkas yang tidak menuntut tahap kompilasi manual. Hasil penelusuran dirangkai ke StringBuilder dan dipotong spasinya dengan trim(), pendekatan yang lebih murah daripada menyambung String berulang kali. Pemeriksaan node != null berperan sebagai kasus dasar, padanan if node is not None pada Python, dan kelupaan di sini memicu NullPointerException. Keluaran ketiga urutan identik dengan versi Python, pengingat bahwa urutan penelusuran adalah sifat algoritmanya, bukan sifat bahasanya.

Kesalahan umum#

1. Menaruh pencatatan nilai di posisi yang salah. Ketiga urutan hanya berbeda satu baris, sehingga kesalahan posisi menghasilkan keluaran yang tampak hampir benar, misalnya inorder yang keluar seperti preorder. Ujilah dengan pohon tiga node yang ketiga urutannya berbeda semua sebelum menguji pohon besar.
2. Melupakan kasus dasar None. Tanpa pemeriksaan None, pemanggilan node.kiri pada node tanpa anak memicu AttributeError di Python atau NullPointerException di Java. Setiap fungsi rekursif pohon wajib dimulai dengan pemeriksaan ini.
3. Mencampur konvensi depth dan height. Depth milik satu node, sedangkan height milik pohon atau subtree, dan keduanya bisa dihitung dalam sisi atau node. Tentukan konvensi di awal jawaban agar selisih satu tidak menjadi masalah saat dibandingkan dengan kunci jawaban.
4. Memakai ulang daftar hasil tanpa dikosongkan. Daftar hasil yang dibuat sekali di luar fungsi dan tidak diinisialisasi ulang akan menumpuk isi dari panggilan sebelumnya. Buat daftar baru di setiap uji coba atau kosongkan dengan hasil.clear().

Ringkasan#

• Pohon biner didefinisikan lewat kosakata root, leaf, parent, child, sibling, depth, height, dan subtree, dan setiap subtree adalah pohon utuh yang lebih kecil.
• Kelas Node menyimpan satu nilai dan dua referensi anak, dengan None sebagai penanda cabang kosong dan pohon kosong.
• Preorder, inorder, dan postorder hanya berbeda posisi pencatatan nilai terhadap dua pemanggilan rekursif, dengan kasus dasar None yang seragam.
• Keluaran ketiga urutan pada pohon contoh sama persis di Python dan Java karena urutan kunjungan adalah sifat algoritma, bukan bahasa.

Referensi#

• Binary tree — Wikipedia — definisi terminologi pohon biner yang menjadi dasar bagian anatomi.
• Tree traversal — Wikipedia — rincian preorder, inorder, dan postorder beserta variasinya.