Traversal Pohon Biner: Preorder, Inorder, Postorder, Rekonstruksi

Traversal preorder mengunjungi akar dulu lalu subpohon kiri dan kanan, inorder mengunjungi kiri, akar, lalu kanan, sedangkan postorder mengunjungi kiri, kanan, baru akar. Untuk pohon 9 simpul di artikel ini, hasilnya preorder A B D E G H C F I, inorder D B G E H A C I F, dan postorder D G H E B I F C A. Setelah tiga traversal itu, kita membalik arahnya: membangun ulang pohon dari pasangan preorder dan inorder, jenis contoh soal yang paling sering keluar di UTS struktur data.

#Apa urutan preorder, inorder, dan postorder?

Ketiganya didefinisikan secara rekursif. Bedanya hanya kapan akar dicatat.

Pohon contohnya: A adalah akar dengan anak kiri B dan anak kanan C. B punya anak kiri D dan anak kanan E. E punya dua anak, G (kiri) dan H (kanan). C hanya punya anak kanan F, dan F hanya punya anak kiri I. Dua simpul dengan satu anak itu sengaja dipasang, karena di situlah jawaban paling sering salah.

Mari cek preorder dengan tangan. Catat A. Masuk ke kiri: catat B, lalu kiri B yaitu D (daun, selesai). Kembali ke kanan B, catat E, lalu G, lalu H. Subpohon kiri A selesai. Masuk ke kanan: catat C. C tidak punya anak kiri, jadi langsung ke kanan, catat F, lalu anak kiri F yaitu I. Hasilnya A B D E G H C F I.

Dalam Python, ketiganya hanya berbeda posisi satu baris:

class Simpul:
    def __init__(self, data, kiri=None, kanan=None):
        self.data, self.kiri, self.kanan = data, kiri, kanan

def preorder(s):
    if s is None:
        return []
    return [s.data] + preorder(s.kiri) + preorder(s.kanan)

def inorder(s):
    if s is None:
        return []
    return inorder(s.kiri) + [s.data] + inorder(s.kanan)

def postorder(s):
    if s is None:
        return []
    return postorder(s.kiri) + postorder(s.kanan) + [s.data]

Kalau cara kerja pemanggilan rekursif seperti ini belum terasa jelas, baca dulu tracing rekursi Python dan call stack.

#Bagaimana trik jalur keliling bekerja?

Untuk soal ujian tulis, ada cara yang lebih cepat dari mengikuti definisi rekursif. Gambar garis yang mengelilingi pohon, mulai dari sisi kiri akar, berjalan berlawanan arah jarum jam dan menempel ke setiap simpul dan cabang. Setiap simpul akan dilewati tiga kali: dari sisi kiri, dari sisi bawah, dan dari sisi kanan.

1. Catat simpul saat garis melewati sisi kirinya: itu preorder.
2. Catat saat melewati sisi bawahnya: itu inorder.
3. Catat saat melewati sisi kanannya: itu postorder.

Ikuti titik merah di gambar sepanjang garis, dan kamu mendapat A B D E G H C F I. Titik hijau memberi D B G E H A C I F. Perhatikan simpul C: titik hijaunya dilewati sebelum garis turun ke F, sehingga C muncul sebelum I dan F di inorder. Itu terjadi karena C tidak punya anak kiri.

#Bagaimana merekonstruksi pohon dari preorder dan inorder?

Soal tipe ini memberi dua barisan dan meminta pohonnya. Kita pakai barisan dari pohon contoh:

• Preorder: A B D E G H C F I
• Inorder: D B G E H A C I F

Kuncinya dua fakta. Elemen pertama preorder selalu akar. Di inorder, semua yang berada di kiri akar adalah subpohon kiri dan semua yang di kanannya adalah subpohon kanan. Jumlah elemen di kiri itu memberi tahu berapa elemen preorder (setelah akar) yang milik subpohon kiri.

Uraian langkahnya:

1. Akar adalah A. Di inorder, ada 5 elemen di kiri A, jadi 5 elemen preorder setelah A (B D E G H) milik subpohon kiri, dan sisanya (C F I) milik subpohon kanan.
2. Ulangi untuk subpohon kiri. Preorder-nya diawali B, jadi B akarnya. Di inorder D B G E H, hanya D di kiri B. Maka D anak kiri B, dan G E H masuk subpohon kanan B.
3. Preorder E G H diawali E. Di inorder G E H, G di kiri dan H di kanan. Selesai untuk sisi kiri.
4. Subpohon kanan A: preorder C F I diawali C. Di inorder C I F, tidak ada apa pun di kiri C. Jadi C tidak punya anak kiri, dan I F adalah subpohon kanannya.
5. Preorder F I diawali F. Di inorder I F, I berada di kiri F. Maka I adalah anak kiri F, bukan anak kanan.

Langkah 4 dan 5 adalah tempat jawaban sering melenceng. Tanpa membaca inorder dengan teliti, banyak yang memasang F sebagai anak kiri C atau I sebagai anak kanan F.

Pasangan inorder dan postorder juga cukup. Bedanya, akar diambil dari elemen terakhir postorder, bukan elemen pertama. Untuk postorder D G H E B I F C A, akarnya A, dan pembagian kiri-kanan dari inorder berlaku sama persis.

#Kenapa preorder dan postorder saja tidak cukup?

Karena keduanya tidak bisa membedakan anak kiri dari anak kanan ketika sebuah simpul hanya punya satu anak. Bandingkan dua pohon berikut:

• Pohon 1: A dengan anak kiri B.
• Pohon 2: A dengan anak kanan B.

Keduanya punya preorder A B dan postorder B A. Hanya inorder yang berbeda: B A untuk pohon 1, A B untuk pohon 2. Inorder adalah satu-satunya traversal yang menaruh akar di antara kiri dan kanan, sehingga posisinya membawa informasi sisi.

Pengecualiannya pohon biner penuh, yaitu pohon yang setiap simpulnya punya nol atau dua anak. Di pohon seperti itu tidak ada simpul dengan anak tunggal, sehingga preorder dan postorder sudah cukup. Pohon contoh kita bukan pohon penuh (C dan F punya satu anak), jadi soal yang hanya memberi preorder dan postorder untuk pohon ini tidak punya jawaban tunggal.

#Apa hubungan traversal dengan pohon ekspresi?

Pohon ekspresi menaruh operator di simpul dalam dan operand di daun. Untuk $(a+b)\times (c-d)$, akarnya *, anak kirinya + dengan daun a dan b, dan anak kanannya - dengan daun c dan d.

Inorder kehilangan kurungnya, sehingga a + b * c - d kalau dibaca biasa berarti $a+(b\times c)-d$, ekspresi yang berbeda. Kalau inorder dipakai untuk mencetak ekspresi, tambahkan kurung setiap kali masuk ke subpohon operator. Postorder tidak punya masalah ini, dan dengan $a=3$, $b=5$, $c=7$, $d=2$ hasilnya $(3+5)\times (7-2)=40$. Cara mendapatkan postfix langsung dari infix memakai stack, tanpa menggambar pohon, ada di konversi infix ke postfix dengan stack.

#Kenapa inorder pada BST selalu terurut?

Di binary search tree (BST), semua nilai di subpohon kiri lebih kecil dari akar dan semua nilai di subpohon kanan lebih besar. Inorder mengunjungi kiri, akar, lalu kanan, jadi otomatis mengeluarkan nilai dari kecil ke besar.

Masukkan 50, 30, 70, 20, 40, 60, 80 secara berurutan ke BST kosong. Hasilnya pohon dengan akar 50, anak 30 dan 70, serta daun 20, 40, 60, 80.

Dua konsekuensi yang sering ditanyakan. Pertama, cara paling sederhana memeriksa apakah sebuah pohon adalah BST adalah menghitung inorder-nya lalu mengecek apakah naik terus. Kedua, BST dengan nilai unik bisa dibangun ulang dari preorder saja, karena inorder-nya pasti barisan yang sama setelah diurutkan.

#Kesalahan yang sering terjadi di soal traversal

• Menganggap postorder adalah kebalikan preorder. Kebalikan preorder pohon contoh adalah I F C H G E D B A, sedangkan postorder sebenarnya D G H E B I F C A. Keduanya berbeda.
• Tertukar dengan level order. Level order (per tingkat, kiri ke kanan) untuk pohon contoh adalah A B C D E F G H I. Itu bukan preorder, walaupun keduanya sama-sama dimulai dari akar.
• Salah menaruh anak tunggal. Di gambar soal, perhatikan apakah garis ke anak tunggal miring ke kiri atau ke kanan. Kalau I dianggap anak kanan F, inorder berubah dari I F menjadi F I.
• Memotong barisan preorder berdasarkan huruf, bukan berdasarkan jumlah. Saat rekonstruksi, jumlah elemen di kiri akar pada inorder adalah satu-satunya patokan untuk memotong preorder.
• Lupa bahwa subpohon kosong tetap dihitung. Pada simpul C, langkah "kunjungi kiri" tetap terjadi, hanya saja tidak menghasilkan apa-apa.

#FAQ

#Berapa kompleksitas waktu traversal pohon biner?

Ketiganya $O\left(n\right)$ karena setiap simpul dikunjungi tepat sekali. Versi Python di atas yang menggabungkan list dengan + sebenarnya bisa lebih lambat untuk pohon yang sangat miring, karena penggabungan list juga memakan waktu. Cara menganalisis hal seperti itu ada di cara menghitung Big O dari kode.

#Bisakah traversal dilakukan tanpa rekursi?

Bisa, dengan stack eksplisit. Untuk inorder, dorong simpul ke stack sambil terus bergerak ke kiri, lalu pop, catat, dan pindah ke anak kanan. Hasilnya sama, hanya kodenya lebih panjang.

#Apa itu level order dan kenapa memakai queue?

Level order mengunjungi pohon tingkat demi tingkat. Simpul yang ditemukan lebih dulu harus diproses lebih dulu, jadi strukturnya queue, bukan stack. Untuk pohon contoh hasilnya A B C D E F G H I.

#Apakah dua pohon berbeda bisa punya inorder yang sama?

Bisa. Inorder D B G E H A C I F juga bisa dihasilkan oleh pohon lain dengan akar berbeda. Karena itu inorder saja tidak cukup untuk rekonstruksi, dan selalu harus dipasangkan dengan preorder atau postorder.

#Bagaimana kalau ada nilai yang sama di dalam pohon?

Rekonstruksi dari preorder dan inorder mengandalkan posisi akar yang unik di inorder. Kalau ada nilai kembar, posisi itu ambigu, sehingga soal rekonstruksi hampir selalu memakai label unik seperti huruf A sampai I.